instagram

Find cycle/loop in the graph – Find and Union with Path Compression

To identify loop in the graph, We are going to use Find and Union technic with Path Compression. We are going to create subject of each vertex and we will represent one element of that subset as a parent, So next time we will take two vertex will check the parent of each, if both has same parent then loop found.

See Utility for graph to get Graph and Node class

Lets see below two graphs,

Find same algorithm without using path compression

Find algorithm below.

Output of above algorithm

Share