Kruskal's algorithm

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Kruskal's algorithm is a greedy algorithm to find a minimum spanning tree in a weighted, undirected graph. Joseph Kruskal first described it in 1956:

Perform the following step as many times as possible: Among the edges (..) not yet chosen, choose the shortest edge, which does not form any loops with those edges already chosen
—Kruskal, 1956[1]

In this case, the shortest edge is the one with the lowest weight.

Example[change | edit source]

Download the example data.

Image Description
Kruskal Algorithm 1.svg AD and CE are the shortest edges, with length 5, and AD has been arbitrarily chosen, so it is highlighted.
Kruskal Algorithm 2.svg CE is now the shortest edge that does not form a cycle, with length 5, so it is highlighted as the second edge.
Kruskal Algorithm 3.svg The next edge, DF with length 6, is highlighted using much the same method.
Kruskal Algorithm 4.svg The next-shortest edges are AB and BE, both with length 7. AB is chosen arbitrarily, and is highlighted. The edge BD has been highlighted in red, because there already exists a path (in green) between B and D, so it would form a cycle (ABD) if it were chosen.
Kruskal Algorithm 5.svg The process continues to highlight the next-smallest edge, BE with length 7. Many more edges are highlighted in red at this stage: BC because it would form the loop BCE, DE because it would form the loop DEBA, and FE because it would form FEBAD.
Kruskal Algorithm 6.svg Finally, the process finishes with the edge EG of length 9, and the minimum spanning tree is found.

References[change | edit source]

  1. Joseph. B. Kruskal (Feb 1956). "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem" (pdf). Proceedings of the American Mathematical Society 7 (1): 48-50. http://penguin.ewu.edu/class/cscd320/Topic/Graph/Kruskal/PAMS_1956.pdf.