Detect Cycle in Undirected Graph

Detect Cycle in Undirected Graph

  August 29, 2017    

---

Explanation:

Here we are going with DFS traversal and checking if a node is visited again and it is not parent of current node then it is a cycle.


Code:

class hackerranksolutionc
{
    boolean DFS(boolean visited[],int i,int parent,LinkedList<Integer>[] alist)
    {
        visited[i]=true;
        int node;
        Iterator<Integer> itr=alist[i].listIterator();
        while(itr.hasNext())
        {
            node=itr.next();
            if(!visited[node])
            {if(DFS(visited,node,i,alist))
            return true;}
            else if(parent!=node)
            return true;
            
        }
        return false;
    }
    Boolean isCyclic(int V,LinkedList<Integer>[] alist)
    {
       boolean visited[]=new boolean[V];
      // Arrays.fill(visited,false);
       for(int i=0;i<V;++i)
       {
           if(!visited[i])
           if(DFS(visited,i,-1,alist))
           return true;
       }
       return false;
    }
}