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.