COMP1927 - Cycle/Path Detection

We can do cycle and path detection in a couple of different ways. We can simply DFS from one node to another and see if a path exists, or we can use a union find.

Union Find

Union Find uses a number of sets, and checks whether elements are in the same set to see if they are linked or not.

We can do this very simply by allocating each node a 'parent'.

We define the 'uppermost parent' as the stopping point for following parents of parents up the linking. The uppermost parent is reached when a node's parent is its parent.

E. g.
Parents: A B C D
Nodes: A A A B

So A's parents is itself, and is hence the uppermost parent for A, B, C and D.

Algorithm

  1. Set each node's parent to be itself.
  2. Whenever you check if two nodes are connected, recurse up the parents away until you find the two uttermost parents. If they're the same, they're connected.
  3. To connect two nodes, set the uttermost parent of node 1 to be node 2.