Encyclopedia > Kruskal's algorithm

  Article Content

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 Y1 be any minimal spanning tree for P. If Y = Y1, QED. If not, there is an edge in Y that is not in Y1. 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 Y1 is a spanning tree of P, there is a path in Y1 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 Y1 and Y2 be similar graphs except for one edge. If Y2 includes f and Y1 includes e, and w(f) >= w(e), we see that Y2 >= Y1. If we continue with all edges, we will eventually find a graph Yh 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.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Wheatley Heights, New York

... 7.9% who are 65 years of age or older. The median age is 35 years. For every 100 females there are 95.1 males. For every 100 females age 18 and over, there are 89.3 ...

 
 
 
This page was created in 78.7 ms