Kruskal's Algorithm

There are several algorithms for finding minimal spanning trees, one of which is Kruskal's algorithm. The algorithm is executed as follows.

Kruskal's algorithm

• Set an empty set A={} and F = E where E is the set of all edges.

• Choose an edge e in F of minimum weight, and check whether adding e to A creates a cycle.

  • If it does, remove e from F
  • If it doesn't, move e from F to A

• If F={} stop and output the minimal spanning tree (V,A).

Kruskal's algorithm is a good example of a greedy algorithm, in which we make a series of decisions, each doing what seems best at the time. The local decisions are which edge to add to the spanning tree formed. In each case, we pick the edge with the least label that does not violate the definition of a spanning tree by completing a cycle. Often the overall effect of a locally optimal solution is not globally optimal. However Kruskal's algorithm is a case is where this is not true.

Show that the running time of Kruskal's Algorithm is $O(m \log n )$ on a graph with $n$ nodes and $m$ is the larger of either the nodes or edges.

Let us assume the graph is represented by adjacency lists, so we can find all edges in $O(m)$ time.

We must first sort the edges by label, which takes $O(m \log m )$ time, if we use merge sort. Next, we consider the edges, taking $O(m \log n)$ time to do all the merges and finds. It appears that the total time for Kruskal's algorithm is thus $$O(m( \log n + \log m ) )$$

Notice however that $m \leq n^2$ because there are only $\frac{n(n-1)}{2}$ pairs of nodes. Thus, $\log m \leq 2\log n$ and $m(\log n + \log m) \leq 3m \log n$. Since the constants can be neglected we conclude that indeed takes $$O(m \log n )$$ time.