Detect cycle in an undirected graph using BFS

Read

Discuss

Given an undirected graph, how to check if there is a cycle in the graph? For example, the following graph has a cycle of 1-0-2-1.

cycleGraph

We have discussed cycle detection for the directed graph. We have also discussed a union-find algorithm for cycle detection in undirected graphs.. The time complexity of the union-find algorithm is O(ELogV). Like directed graphs, we can use DFS to detect a cycle in an undirected graph in O(V+E) time. We have discussed DFS based solution for cycle detection in an undirected graph.

In this article, the BFS based solution is discussed. We do a BFS traversal of the given graph. For every visited vertex ‘v’, if there is an adjacent ‘u’ such that u is already visited and u is not a parent of v, then there is a cycle in the graph. If we don’t find such an adjacent for any vertex, we say that there is no cycle.

We use a parent array to keep track of the parent vertex for a vertex so that we do not consider the visited parent as a cycle.

Implementation:

C++

// C++ program to detect cycle 
// in an undirected graph
// using BFS.
#include <bits/stdc++.h>
using namespace std;
 
void addEdge(vector<int> adj[], int u, int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}
 
bool isCyclicConnected(vector<int> adj[], int s,
                        int V, vector<bool>& visited)
{
    // Set parent vertex for every vertex as -1.
    vector<int> parent(V, -1);
 
    // Create a queue for BFS
    queue<int> q;
 
    // Mark the current node as 
    // visited and enqueue it
    visited[s] = true;
    q.push(s);
 
    while (!q.empty()) {
 
        // Dequeue a vertex from queue and print it
        int u = q.front();
        q.pop();
 
        // Get all adjacent vertices of the dequeued
        // vertex u. If a adjacent has not been visited,
        // then mark it visited and enqueue it. We also
        // mark parent so that parent is not considered
        // for cycle.
        for (auto v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
                parent[v] = u;
            }
            else if (parent[u] != v)
                return true;
        }
    }
    return false;
}
 
bool isCyclicDisconnected(vector<int> adj[], int V)
{
    // Mark all the vertices as not visited
    vector<bool> visited(V, false);
 
    for (int i = 0; i < V; i++)
        if (!visited[i] && isCyclicConnected(adj, i,
                                         V, visited))
            return true;
    return false;
}
 
// Driver program to test methods of graph class
int main()
{
    int V = 4;
    vector<int> adj[V];
    addEdge(adj, 0, 1);
    addEdge(adj, 1, 2);
    addEdge(adj, 2, 0);
    addEdge(adj, 2, 3);
 
    if (isCyclicDisconnected(adj, V))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

Java

// Java program to detect cycle in
//  an undirected graph using BFS.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
 
class cycle
{
     
  public static void main(String arg[]) 
  {
 
    int V = 4;
    @SuppressWarnings("unchecked")
    ArrayList <Integer> adj[] = new ArrayList[V];
    for(int i = 0; i < 4; i++)
      adj[i] = new ArrayList<Integer>();
 
    addEdge(adj, 0, 1);
    addEdge(adj, 1, 2);
    addEdge(adj, 2, 0);
    addEdge(adj, 2, 3);
 
    if (isCyclicDisconnected(adj, V))
      System.out.println("Yes");
    else
      System.out.println("No");
  }
 
  static void addEdge(ArrayList<Integer> adj[], int u, int v)
  {
    adj[u].add(v);
    adj[v].add(u);
  }
 
  static boolean isCyclicConnected(
                             ArrayList<Integer> adj[], int s,
                                    int V, boolean visited[]) 
  {
 
    // Set parent vertex for every vertex as -1.
    int parent[] = new int[V];
    Arrays.fill(parent, -1);
 
    // Create a queue for BFS
    Queue<Integer> q = new LinkedList<>();
 
    // Mark the current node as
    // visited and enqueue it
    visited[s] = true;
    q.add(s);
 
    while (!q.isEmpty()) 
    {
 
      // Dequeue a vertex from 
      // queue and print it
      int u = q.poll();
 
 
      // Get all adjacent vertices 
      // of the dequeued vertex u.
      // If a adjacent has not been 
      // visited, then mark it visited
      // and enqueue it. We also mark parent
      // so that parent is not considered
      // for cycle.
      for (int i = 0; i < adj[u].size(); i++)
      {
        int v = adj[u].get(i);
        if (!visited[v]) 
        {
          visited[v] = true;
          q.add(v);
          parent[v] = u;
        }
        else if (parent[u] != v)
          return true;
      }
    }
    return false;
  }
 
 
  static boolean isCyclicDisconnected(
                       ArrayList<Integer> adj[], int V)
  {
 
    // Mark all the vertices as not visited
    boolean visited[] = new boolean[V];
    Arrays.fill(visited,false);
 
    for (int i = 0; i < V; i++)
      if (!visited[i] && 
          isCyclicConnected(adj, i, V, visited))
        return true;
    return false;
  }
}
 
// This code is contributed by mayukh Sengupta

Python3

# Python3 program to detect cycle in 
# an undirected graph using BFS.
from collections import deque
 
def addEdge(adj: list, u, v):
    adj[u].append(v)
    adj[v].append(u)
 
def isCyclicConnected(adj: list, s, V, 
                      visited: list):
 
    # Set parent vertex for every vertex as -1.
    parent = [-1] * V
 
    # Create a queue for BFS
    q = deque()
 
    # Mark the current node as 
    # visited and enqueue it
    visited[s] = True
    q.append(s)
 
    while q != []:
 
        # Dequeue a vertex from queue and print it
        u = q.pop()
 
        # Get all adjacent vertices of the dequeued
        # vertex u. If a adjacent has not been visited,
        # then mark it visited and enqueue it. We also
        # mark parent so that parent is not considered
        # for cycle.
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                q.append(v)
                parent[v] = u
            elif parent[u] != v:
                return True
 
    return False
 
def isCyclicDisconnected(adj: list, V):
 
    # Mark all the vertices as not visited
    visited = [False] * V
 
    for i in range(V):
        if not visited[i] and \
               isCyclicConnected(adj, i, V, visited):
            return True
    return False
 
# Driver Code
if __name__ == "__main__":
    V = 4
    adj = [[] for i in range(V)]
    addEdge(adj, 0, 1)
    addEdge(adj, 1, 2)
    addEdge(adj, 2, 0)
    addEdge(adj, 2, 3)
 
    if isCyclicDisconnected(adj, V):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by
# sanjeev2552

C#

// A C# program to detect cycle in
// an undirected graph using BFS.
using System;
using System.Collections.Generic;
 
class GFG
{
    public static void Main(String []arg) 
    {
        int V = 4;
        List<int> []adj = new List<int>[V];
        for (int i = 0; i < 4; i++) 
        {
            adj[i] = new List<int>();
        }
 
        addEdge(adj, 0, 1);
        addEdge(adj, 1, 2);
        addEdge(adj, 2, 0);
        addEdge(adj, 2, 3);
 
        if (isCyclicDisconnected(adj, V)) 
        {
            Console.WriteLine("Yes");
        } 
        else
        {
            Console.WriteLine("No");
        }
    }
 
    static void addEdge(List<int> []adj, int u, int v) 
    {
        adj[u].Add(v);
        adj[v].Add(u);
    }
 
    static bool isCyclicConnected(List<int> []adj, int s, 
                                    int V, bool []visited) 
    {
 
        // Set parent vertex for every vertex as -1.
        int []parent = new int[V];
        for (int i = 0; i < V; i++)
        parent[i] = -1;
 
        // Create a queue for BFS
        Queue<int> q = new Queue<int>();
 
        // Mark the current node as
        // visited and enqueue it
        visited[s] = true;
        q.Enqueue(s);
 
        while (q.Count != 0) 
        {
 
            // Dequeue a vertex from 
            // queue and print it
            int u = q.Dequeue();
 
            // Get all adjacent vertices 
            // of the dequeued vertex u.
            // If a adjacent has not been 
            // visited, then mark it visited
            // and enqueue it. We also mark parent
            // so that parent is not considered
            // for cycle.
            for (int i = 0; i < adj[u].Count; i++)
            {
                int v = adj[u][i];
                if (!visited[v]) 
                {
                    visited[v] = true;
                    q.Enqueue(v);
                    parent[v] = u;
                }
                else if (parent[u] != v)
                {
                    return true;
                }
            }
        }
        return false;
    }
 
    static bool isCyclicDisconnected(List<int> []adj, int V)
    {
 
        // Mark all the vertices as not visited
        bool []visited = new bool[V];
 
        for (int i = 0; i < V; i++) 
        {
            if (!visited[i] && 
                isCyclicConnected(adj, i, V, visited))
            {
                return true;
            }
        }
        return false;
    }
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
 
// A JavaScript program to detect cycle in
// an undirected graph using BFS.
var V = 4;
var adj = Array.from(Array(V), ()=>Array());
 
addEdge(adj, 0, 1);
addEdge(adj, 1, 2);
addEdge(adj, 2, 0);
addEdge(adj, 2, 3);
if (isCyclicDisconnected(adj, V)) 
{
    document.write("Yes");
} 
else
{
    document.write("No");
}
 
function addEdge(adj, u, v) 
{
    adj[u].push(v);
    adj[v].push(u);
}
function isCyclicConnected(adj, s, V, visited) 
{
    // Set parent vertex for every vertex as -1.
    var parent = Array(V).fill(-1);
     
    // Create a queue for BFS
    var q = [];
    // Mark the current node as
    // visited and enqueue it
    visited[s] = true;
    q.push(s);
    while (q.length != 0) 
    {
        // Dequeue a vertex from 
        // queue and print it
        var u = q.shift();
        // Get all adjacent vertices 
        // of the dequeued vertex u.
        // If a adjacent has not been 
        // visited, then mark it visited
        // and enqueue it. We also mark parent
        // so that parent is not considered
        // for cycle.
        for (var i = 0; i < adj[u].length; i++)
        {
            var v = adj[u][i];
            if (!visited[v]) 
            {
                visited[v] = true;
                q.push(v);
                parent[v] = u;
            }
            else if (parent[u] != v)
            {
                return true;
            }
        }
    }
    return false;
}
function isCyclicDisconnected(adj, V)
{
    // Mark all the vertices as not visited
    var visited = Array(V).fill(false);
    for (var i = 0; i < V; i++) 
    {
        if (!visited[i] && 
            isCyclicConnected(adj, i, V, visited))
        {
            return true;
        }
    }
    return false;
}
 
</script>

Output

Yes

Time Complexity: The program does a simple BFS Traversal of the graph and the graph is represented using an adjacency list. So the time complexity is O(V+E)
Space Complexity: O(V) for visited vector.

Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!

Last Updated : 22 Jun, 2023