For a connected weighted undirected graph, Kruskal's algorithm begins with each vertex as a separate component and no selected edges. Sort all edges into nondecreasing weight order. Inspect them in that order and add an edge exactly when its endpoints lie in different current components. Merge those components after an addition; stop once edges have been accepted. A disjoint-set data structure implements the component tests and merges.
The accepted edges always form a forest, because an edge whose endpoints were already connected is rejected. To prove optimality, use the invariant that some minimum spanning tree contains every accepted edge. It holds initially. Suppose the next accepted edge is , and let be a minimum spanning tree extending the current forest. If , nothing changes. Otherwise adding to makes a unique graph cycle. The graph path from to in must cross the graph cut between the current component of and the remaining vertices, so that graph cycle contains an edge crossing this graph cut. No accepted edge crosses it. Furthermore : any strictly lighter crossing edge would already have been processed and accepted, since its endpoints could not then have been connected without also being connected now.
Replace by . The resulting spanning tree still contains all previously accepted edges and has cost at most that of , so it too is a minimum spanning tree. This is the exchange argument establishing the invariant. At termination the selected edges themselves form a spanning tree, henceEqual weights cause no difficulty; they may give several optima. On a disconnected graph, processing all edges instead returns a minimum spanning forest. Sorting costs , with near-linear additional cost using an efficient disjoint-set data structure.
Articles by others on the same topic
There are currently no matching articles.