Detect cycle in an undirected graph using BFS

Last Updated : 22 Jun, 2023

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.

Suggest improvement

Traversal of a Graph in lexicographical order using BFS

Detect Cycle in a Directed Graph using BFS

Share your thoughts in the comments

BFS in different language

Variations of BFS implementations

Easy problems on BFS

Intermediate problems on BFS

Hard Problems on BFS