Question

Which graph search method will be better for finding a cycle in an undirected graph: a BTS or a DFS? In detail, describe (create) an algorithm for finding a cycle in any undirected graph, explaining why the algorithm assures to find a cycle if there exists one.

Answer 1

DFS is better for finding cycle in an undirected graph, because

1. DFS is easier to implement
2. Once DFS finds a cycle, the stack will contain the nodes forming the cycle. The same is not true for BFS, so you need to do extra work if you want to also print the found cycle. This makes DFS a lot more convenient.
3. using BFS, you have to explicitly maintaining the history of visited nodes using proper data structures.

DFS is a clear choice.

To detect if there is any cycle in the undirected graph or not, we will use the DFS traversal for the given graph. For every visited vertex v, when we have found any adjacent vertex u, such that u is already visited, and u is not the parent of vertex v. Then one cycle is detected.

We will assume that there are no parallel edges for any pair of vertices.

Input and Output:
Adjacency matrix
   
    0 1 0 0 0
    1 0 1 1 0
    0 1 0 0 1
    0 1 0 0 1
    0 0 1 1 0

Output:
The graph has cycle.

Algorithm

dfs(vertex, visited, parent)

Input: The start vertex, the visited set, and the parent node of the vertex.

Output: True a cycle is found.Begin

add vertex in the visited set

for all vertex v which is adjacent with vertex, do

if v = parent, then

return true

if v is not in the visited set, then

return true

if dfs(v, visited, vertex) is true, then

return true

   done

return false

End hasCycle(graph)

Input: The given graph.

Output: True when a cycle has found.Begin

for all vertex v in the graph, do

if v is not in the visited set, then

go for next iteration

if dfs(v, visited, φ) is true, then //parent of v is null

return true

return false

done

End

Given an undirected graph, how to check if there is a cycle in the graph?

Example,

Input: n = 4, e = 4
Output: Yes
Explanation:
0 1, 1 2, 2 3, 0 2
Diagram:

The diagram clearly shows a cycle 0 to 2 to 1 to 0

Input:n = 4, e = 3
0 1, 1 2, 2 3
Output:No
Explanation:
Diagram:

The diagram clearly shows no cycle

Run a DFS from every unvisited node. Depth First Traversal can be used to detect a 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. A back edge is an edge that is joining a node to itself (self-loop) or one of its ancestor in the tree produced by DFS.
To find the back edge to any of its ancestor keep a visited array and if there is a back edge to any visited node then there is a loop and return true.

Algorithm:

1. Create the graph using the given number of edges and vertices.
2. Create a recursive function that that current index or vertex, visited and recursion stack.
3. Mark the current node as visited and also mark the index in recursion stack.
4. Find all the vertices which are not visited and are adjacent to the current node. Recursively call the function for those vertices, If the recursive function returns true return true.
5. If the adjacent vertices are already marked in the recursion stack then return true.
6. Create a wrapper class, that calls the recursive function for all the vertices and if any function returns true, return true.
7. Else if for all vertices the function returns false return false.

// 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
class Graph
{
   private int V; // No. of vertices
   private LinkedList<Integer> adj[]; // Adjacency List Represntation

   // 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++)
           if (!visited[u]) // Don't recur for u if already visited
               if (isCyclicUtil(u, visited, -1))
                   return true;

       return false;
   }

   // Driver method to test above methods
   public static void main(String args[])
   {
       // Create a graph given in the above diagram
       Graph g1 = new Graph(5);
       g1.addEdge(1, 0);
       g1.addEdge(0, 2);
       g1.addEdge(2, 1);
       g1.addEdge(0, 3);
       g1.addEdge(3, 4);
       if (g1.isCyclic())
           System.out.println("Graph contains cycle");
       else
           System.out.println("Graph doesn't contains cycle");

       Graph g2 = new Graph(3);
       g2.addEdge(0, 1);
       g2.addEdge(1, 2);
       if (g2.isCyclic())
           System.out.println("Graph contains cycle");
       else
           System.out.println("Graph doesn't contains cycle");
   }
}

Output:

Graph contains cycle
Graph doesn't contain cycle

Complexity Analysis:

• Time Complexity: O(V+E).
  The program does a simple DFS Traversal of the graph which is represented using adjacency list. So the time complexity is O(V+E).