Card 02/ 09
Trace Kruskal's Algorithm With Union-Find
Sort the edges by weight, take each one that joins two separate trees, and skip any that would close a cycle.
Kruskal's algorithm builds a minimum spanning tree by taking the edges from lightest to heaviest and keeping each one that joins two vertices not yet connected. This card traces it on the topic's graph and shows the one test it needs: whether an edge's two ends are already in the same tree.
The chosen edges start as a forest, one tree per vertex, and every edge taken joins two of those trees into one. An edge whose ends are already in one tree would close a cycle, so it is skipped. Union-find, from Data Structures, answers the test quickly: find returns a name for a vertex's tree, so two vertices share a tree when find returns the same name for both, and union merges two trees. The algorithm stops once it has V − 1 edges, because a spanning tree has no more.
The topic's graph has six vertices and the undirected edges A-B 4, A-C 1, B-C 2, B-D 5, C-D 8, C-E 9, D-E 3, D-F 7 and E-F 6.
Sort the edges by weight and work out the total weight of the tree before reading on.
17, from A-C 1, B-C 2, D-E 3, B-D 5 and E-F 6. The table below gives the reason for every decision.
| Edge | Weight | Taken | Reason |
|---|---|---|---|
| A-C | 1 | Yes | Joins A and C |
| B-C | 2 | Yes | Joins B to the tree A C |
| D-E | 3 | Yes | Joins D and E |
| A-B | 4 | No | A and B are both in the tree A B C, so it would close a cycle |
| B-D | 5 | Yes | Joins the tree A B C to the tree D E |
| E-F | 6 | Yes | Joins F; that makes five edges, V − 1 for six vertices, so the tree is complete |
| D-F | 7 | Not reached | The algorithm has already stopped |
| C-D | 8 | Not reached | The algorithm has already stopped |
| C-E | 9 | Not reached | The algorithm has already stopped |
Each edge taken is safe by the cut property. When Kruskal's algorithm takes an edge, cut the graph so that one of the trees it joins is on one side and every other vertex is on the other. Every lighter edge has already been looked at: those taken now lie inside a tree, and those skipped had both ends in one tree, so none of them crosses this cut. The edge being taken is the lightest that crosses it. B-D 5, for instance, is the lightest edge leaving A B C, the same cut as on Minimum Spanning Trees and the Cut Property.
The skip is the only place the algorithm says no, and union-find is what makes it cheap. Without it, deciding whether A and B are already connected means searching the edges chosen; with it, two find calls compare the names of their trees. D-F, C-D and C-E are never examined, because five edges already connect all six vertices.
The finished tree is drawn below.
Sorting the E edges costs O(E log E), and each union-find operation costs almost nothing, so the sort sets the running time. Reach for Kruskal's algorithm when the edges arrive as a list, such as the costs of every possible cable run, since the list is exactly what it sorts.
← → move through sections and cards