instagram

Find cycle/loop in the graph – Find and Union

To identify loop in the graph, We are going to use Find and Union technic. 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 algorithm below.

Output :

Share