Quick Find

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 the 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 references to them) 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 $O(1)$.
  • union is expensive, in the worst-case, it is $O(N)$ where $N$ is the number of vertices (objects).

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