Union-Find Data Structure

Kruskal's algorithm needs a data structure that dynamically maintains information about the connected components of a graph.

• If any two endpoints of the edge are already connected, then adding the edge will create a cycle.

A data structure that does this is called the dynamic connectivity structure. In this structure, the set $V$ of vertices of the graph is fixed, but the set $E$ can of edges can change.

• Edges may only be added to the graph (incremental connectivity), may only be deleted (decremental connectivity), or either added or deleted (fully dynamic connectivity).

After each addition/deletion, it will adapt itself to answer questions like "is there a path between $x$ and $y$?".

Consider a graph, we can now ask

connected(A,G) 

Note: "is connected to" is an equivalence relation

• reflexive: p is connected to p
• symmetric: if p is connected to q, then q is connected to p
• transitive: if p is ocnnected to q and q is connected to r, then p is connected to r.

Union-Find

The Union-Find data strucutre (or disjoint-set or merge-find set) catagorizes objects into discjoint (non-overllaping) sets. It facilitates checking if two objects belong to the same set.

• Provides near-constant time operations to add new sets, merge existing sets, and determine whether elements are in the same set.

Application: check whether one node can be reached from another (e.g., in Kruskal's algorithm) to avoid forming cycles.

Operations Core

makeSet(x)   // create and return singleton set with x as element.
find(x)      // return some representation of the set to which x belongs.
union(x,y)   // merge the sets containing x and y.

Other

connected(x,y)  // return true if x & y are in the same set.
count()         // return number of (disjoint) sets.

Implementation: Quick Find

Assign an ID to each vertex to record its membership. P and Q are connected only if they have teh same ID. connected(p,q) checks if they have the same ID. O(1) union(p,q) merges the components containing p and q, and changes all entries whose id equals ID[p] to ID[p]. Worst case O(N).

It is common to store vertices in an array and use array indices to refer to each vertex.

Complexity if building the MST with N singleton set of objects: takes at least (N-1) union commands, leading to O(N^2) runtime.

Implementation: Quick Union

Assign each vertex (object) an ID. These IDs link one node to another to form a "parent/child" relationship as in a tree structure. connected(p,q): checks if p and q have the same root union(p,q): merges components containing p and q, and sets the root of the component containing q to be a direct child of the root of the component containing p.

Both connected and union need to find the root of the components containing their arguments:

// chase parent pointers until root
private int root(int x) {
	while (x!= id[x]) {
		x = id[x];
	}
	return x;
}

• runtime corresponds to the height of the tree structure containng the x object, so the worst case is O(N).
• Improve performance by keeping the tree flat.

Improvment: Weighting

The union by size heuristic: We can improve quick-union by avoiding tall trees.

• Keep track of the size of each component
• balance trees by linking the small tree below the large one.

In this scheme, the depth of any node x shoud be at most lgN.

• The size of tree containing x can double at most lgN times because if you start with one node and double it lgN times, you willg et N. There is only N nodes in the tree.

Note: an alternative strategy is union by rank which attaches the tree with the smaller 'rank' to the root of the tree having a higher rank. Rank is determined by the height of its subtree.

Improvement: Path Compression.

The path compression heuristic: After computing the root of p, set the ID of each examined node to point to that root.

• If all the vertices directly point to the root, the tree becomes shallower.

Runtime

If implemented with union-by-size and path compression:

• tree is practically flat
• operations work in O(lg*n)
  • lg*N is the number of times one needs to apply lg to N to get a value less than or equal to 1.

Kruskal's Runtime

The next min-weight edge will be kept in a min-heap priority queue. Check if adding an edge (v-w) creates a cycle by using union-find.

Build PQ: occurs once and costs O(M) Extract Min: occurs O(M) times and costs O(lgM) Union: occurs O(N) times and costs O(lg*N) ConnectedL occurs O(M) times and costs O(lg*N*)