Question

Please show me the pseudo code.

This pseudo code is used for detect whether a given undirected graph contains a cycle: a sequence of nodes that starts and ends in the same node without traversing the same edge twice.

Answer 1

We use the find-union algorithm to detect a cycle in an undirected graph.

We initially set the parent array to -1 for all nodes.

And array indexing starts from 1, so array is 1,2......,n

find(parent[],i) //function to find root of node i using the parent array

{

if(parent[i]==-1) //if we reach a node which does not have a parent

return i; //we return the node as the root

else

return find(parent,parent[i]); //else we find the root of the parent of the node

}

union(parent[],x,y) //function to join two nodes x and y with different parents

{

xParent=find(parent,x); //finding root of x

yParent=find(parent,y); //finding root of y

if(xParent!=yParent) //if they both do not have same root

parent[xParent]=yParent; //we set root of root of x to be root of y

}

findCycle(a[][],n) //function to return if Graph has a cycle, a[][] is the adjacency matrix and n is the number of nodes in the graph

{

parent[]= array of size n with all elements set to -1;

for i = 1 to n-1

{

for j = i to n

{

if(a[i][j]==1) //if there is an edge between nodes i and j

{

//we find the roots of i and j

x=find(parent,i);

y=find(parent,j);

if (x==y) //if they have same roots, a cycle is formed

return true;

else

union(parent,x,y);

}

}

}

return false; //if program reaches this point, no cycle was detected

}