Question

Write a program in java that detects if there is a cycle in an undirected graph using DFS

Two lines of input:

1. Two integers V for the number of vertices and E for the number of edges respectively.

2. List of integers that shows how the graph is connected.

Ex input:

4 4

01020323

Output:

Graph contains cycle

Ex input:

5 4

01020314

Output:

Graph doesn't contains cycle

Answer 1

The solution

// A Java Program to detect cycle in an undirected graph 

import java.io.*; 
import java.util.*; 
// This class represents a 
// directed graph using adjacency list 
// representation 
public class Graph 
{ 
        
        // No. of vertices 
        private int V; 
        
        // Adjacency List Represntation 
        private LinkedList<Integer> adj[]; 

        // Constructor 
        Graph(int v) 
        { 
                V = v; 
                adj = new LinkedList[v]; 
                for(int i=0; i<v; ++i) 
                        adj[i] = new LinkedList(); 
        } 

        // Function to add an edge 
        // into the graph 
        void addEdge(int v,int w) 
        { 
                adj[v].add(w); 
                adj[w].add(v); 
        } 

        // A recursive function that 
        // uses visited[] and parent to detect 
        // cycle in subgraph reachable 
        // from vertex v. 
        Boolean isCyclicUtil(int v, Boolean visited[], int parent) 
        { 
                // Mark the current node as visited 
                visited[v] = true; 
                Integer i; 

                // Recur for all the vertices 
                // adjacent to this vertex 
                Iterator<Integer> it = adj[v].iterator(); 
                while (it.hasNext()) 
                { 
                        i = it.next(); 

                        // If an adjacent is not 
                        // visited, then recur for that 
                        // adjacent 
                        if (!visited[i]) 
                        { 
                                if (isCyclicUtil(i, visited, v)) 
                                        return true; 
                        } 

                        // If an adjacent is visited 
                        // and not parent of current 
                        // vertex, then there is a cycle. 
                        else if (i != parent) 
                                return true; 
                } 
                return false; 
        } 

        // Returns true if the graph 
        // contains a cycle, else false. 
        Boolean isCyclic() 
        { 
                
                // Mark all the vertices as 
                // not visited and not part of 
                // recursion stack 
                Boolean visited[] = new Boolean[V]; 
                for (int i = 0; i < V; i++) 
                        visited[i] = false; 

                // Call the recursive helper 
                // function to detect cycle in 
                // different DFS trees 
                for (int u = 0; u < V; u++) 
                { 
                
                        // Don't recur for u if already visited 
                        if (!visited[u]) 
                                if (isCyclicUtil(u, visited, -1)) 
                                        return true; 
                } 

                return false; 
        } 


        // Driver method to test above methods 
        public static void main(String args[]) 
        {
        
        // Declare the object and initialize with 
        // predefined standard input object 
        Scanner sc = new Scanner(System.in);
        
        // Enter vertices and edges count values:  
        int V = sc.nextInt();
        int E = sc.nextInt();
       
        Graph g = new Graph(V);
        
        // Now start entering pair of vertices between which to make an edge
        for (int i = 0; i < E; i++)
        {
            int j = sc.nextInt();
            int k = sc.nextInt();
            g.addEdge(j, k);   
        } 
                
                if (g.isCyclic()) 
                        System.out.println("Graph contains cycle"); 
                else
                        System.out.println("Graph doesn't contains cycle"); 

        } 
}