Kruskal's algorithm for finding the minimum spanning tree
loop buildings forest
s, connecting them with the minimum weight
edge possible. Start with an empty graph, find the minimum weight edge which connects different components
of your current forest and add that edge to the graph. Repeat until the graph is connected. This is actually done using Tarjan
's disjoint set data structure
, using two of its functions: `are these two nodes in the same set' and `union the sets containing these two nodes.'
- Initialize the disjoint set data structure such that every node is in a set by itself.
- Go through the edges e in increasing weight.
- If the endpoints of e are in different sets, add the edge to the spanning tree, and union the sets containing the endpoints.
Sorting the edges takes O(n log n) time, while the rest of the algorithm
takes almost linear time (there's an inverse Ackermann function in there). In practice, the edges are normally put into a heap, but that doesn't affect the run-time.