Kruskal’s Algorithm

Kruskal’s Algorithm uses a greedy strategy to build a minimum and maximum Spanning Trees.

Kruskal’s algorithm is a greedy approach to finding the minimum spanning tree (MST) of a connected, weighted graph.

From CS341

GreedyMST(G)
1. A <- []
2. sort edges by increasing weight
3. for k = 1,...,m do
4.     if e_k does not create a cycle in A then
5.         append e_k to A

• If there is a cycle, then it is not a tree, and so can’t be an optimal solution (assuming that edges have positive weights)
• We want to show that the result will be a tree, and so equivalently we have to show that it is connected and that there are no cycles.