Quick Find

  • Trace the Quick Find implementation strategy for Union-Find.
  • Identify the runtime of Union-Find operations under Quick Find implementation.

The main idea behind this approach is to assign an ID to each vertex (object) to record its "membership"; $p$ and $q$ are connected if and only if they have the same ID.

  • connected(p,q): check if $p$ and $q$ have the same ID.
  • union(p,q): to merge components containing $p$ and $q$, change all entries whose ID equals ID[q] to ID[p].

It is common to store vertices (or their references) in an array and use array indices to refer to each vertex.

Demo

Exercise What is the complexity of core operations under "Quick Find" implementation?

Solution
  • find/connected involves checking ID[p]==ID[q] so it is $\Omicron(1)$.
  • union is expensive, in the worst-case, it is $\Omicron(N)$ where $N$ is the number of vertices (objects).

If we start with a $N$ singleton set of objects, to build the MST, it takes at least $(N-1)$ union commands, leading to $\Omicron(N^2)$ runtime.