Kruskal's algorithm

Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component).

It works as follows:

• create a forest (a set of trees), where each vertex in the graph is a separate tree
• create a set containing all the edges in the graph
• while the set is nonempty
  • remove an edge with minimum weight from the set
  • if that edge connects two different trees, then add it to the forest, combining two trees into a single tree
  • otherwise discard that edge

With the use of a suitable data structure, Kruskal's algorithm can be shown to run in O (m log m) time, where m is the number of edges in the graph.

Proof

Let P be a connected, weighted graph. At every iteration of Kruskal's algorithm, an edge must be found that connects a vertex in a subgraph to a vertex outside the subgraph. Since P is connected, there will always be a path to every vertex. The output Y of Kruskal's algorithm is a tree, because the edge and vertex added to Y are connected to other vertices and edges of Y and at no iteration is a circuit created since each edge added connects two vertices in two disconnected sets. Also, Y includes all vertices from P because Y is a tree with n vertices, same as P. Therefore, Y is a spanning tree for P.

Let Y₁ be any minimal spanning tree for P. If Y = Y₁, QED. If not, there is an edge in Y that is not in Y₁. Let e be the first edge that was added when Y was constructed. Let V be the set of vertices of Y - e. Then one endpoint of e is in Y and another is not. Since Y₁ is a spanning tree of P, there is a path in Y₁ joining the two endpoints. As one travels along the path, one must encounter an edge f joining a vertex in V to one that is not in V. Now, at the iteration when e was added to Y, f could also have been added and it would be added instead of e if its weight was less than e. Since f was not added, we conclude that w(f) >= w(e).

Let Y₁ and Y₂ be similar graphs except for one edge. If Y₂ includes f and Y₁ includes e, and w(f) >= w(e), we see that Y₂ >= Y₁. If we continue with all edges, we will eventually find a graph Y_h identical to Y with edge weight less than or equal to, all Ys that preceded it. Therefore, Y is a minimal spanning tree.

Other algorithms for this problem include Prim's algorithm, and Boruvka's algorithm.