Kruskal's algorithm for finding the
minimum spanning tree loop buildings
forests, 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.'
In pseudocode:
- 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.