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 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 $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 set of objects, to build the MST, it takes at least $(N-1)$ union commands, leading to $O(N^2)$ runtime.