Chapter 4.6: Kruskal's Algorithm

The Union-Find structure stores a representation of the components of a graph in a way that supports rapid searching and updating. We will use this to implement Kruskal's Algorithm.

The Union-Find structure allows us to maintain disjoint sets (such as the components of a graph) in the following sense: given a node u the operation Find(u) will return the name of the set containing u. This can be used to test if two nodes are in the same set; just check if Find(u)=Find(j). We can also use Union(A,B) to take two sets A and B and merge them into a single set.

We can use the Union-Find data structure to implement Kruskal's Algorithm. First, sort the edges by cost. This takes O(mlogn) time since we have at most one edge between any pair of nodes. Next, we use the Union-Find data structure to maintain the connected components of (V,T) as edges are added. As each edge is considered we compute Find on either end of the edge to see if they are equal (i.e. the nodes are in the same component). We use Union to merge the two components if the algorithm decides to include the edge in the tree. At most, we do 2m Find operations and n-1 Union operations. Overall, the running time is O(mlogn).

I'd rate this section a 6. It was a lot of information and since we haven't gotten to spend as much time on this stuff in class (because of snow) it is harder to understand.