Thursday 13 November 2014

Detecting Cycle in Directed Graph - DFS

Back EdgeA back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS

Depth First Traversal can be used to detect cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. 

Keep track of the vertices already visited by DFS Traversal. While traversing further, if we visit any of the vertex that is already visited then there is a back edge and hence there is cycle in the graph.


public void solve(int testNumber, CycleDirInputReader in, PrintWriter out) {
        //Read inputs and write the main function.
        int v = in.nextInt();
        int e = in.nextInt();
        ArrayList<Integer>[] alist = new ArrayList[v];
        for(int i=0;i<v;i++) alist[i] = new ArrayList<Integer>();
        while(e-->0) {
            int n1 = in.nextInt();
            int n2 = in.nextInt();
            alist[n1].add(n2);
            //alist[n2].add(n1);
        }
        boolean[] visited = new boolean[v];
        boolean[] explored = new boolean[v];

        if(hasCycleUtil(v,alist,visited,explored)) {
            System.out.println("Contains Cycle");
        }
        else
            System.out.println("Nocycle");
    }

    public boolean hasCycleUtil(int v,ArrayList<Integer>[] alist,boolean[] visited,boolean[] explored) {
        for(int i=0;i<v;i++) {
            if(!visited[i]) {
                if(hasCycle(i,alist,visited,explored)) return true;
            }
        }
        return false;
    }

    public boolean hasCycle(int v,ArrayList<Integer>[] alist,boolean[] visited,boolean[] explored) {
        visited[v] = true;
        explored[v] = true;

        for(int i=0;i<alist[v].size();i++) {
            int n = alist[v].get(i);
            if(!visited[n]) {
                if(hasCycle(n,alist,visited,explored)) return true;
            }
            else if(explored[n]) return true;
        }

        explored[v] = false;
        return false;
    }
}

No comments:

Post a Comment