4.6. Implementing Kruskal's Algorithm: The Union-Find Data Structure

• The basic idea behind the algorithm is that the graph in question has a fixed population of nodes
• And the graphs grows over time by inserting edges between certain pairs of nodes.
• Goal: Maintain a set of connected components of the graph being processed throughout the whole operation
• With this algorithm, we develop a data structure called the Union-Find structure
• The Union-Find data structure stores a representation of the components in a way that supports fast searching and updating
• This data structure is used to efficiently implement Kruskal's Algorithm
  

As each edge e = (u,w) is considered

Find the connected components containing v and w.

If these components are different:

Then there is no path from v to w, so e should be added to the structure

Elif they're the same:

Then there's a path from v to w, so e should be omitted.

• Operations:
  • Find(u) : returns name of set containing u
    • It can be used to find if two nodes u and v are in the same set by simply checking if Find(u) = Finf(v)
    • Goal implementation: O(log n)
  • Union(A, B) : merges sets A and B into one set
    • Goal implementation: O(log n)
• The sets obtained will be the connected components of the graph
• So, for a given node u, Find(u) returns the name of the component containing u
• To add an edge (u,v) we first test if Find(u) = Find(v)
• If Find(u) ≠ Find(v), then Union(Find(u), Find(v)) merges the two components into one
• The Union-Find data structure maintains components of a graph only when we add edges, not when we delete them