Data Structures and Algorithms

DSA Interview Questions

How to Detect a Cycle in an Undirected Graph

Introduction

In graph theory, identifying cycles is a common and crucial task. A cycle in an undirected graph occurs when a path starts and ends at the same vertex without retracing any edge. This tutorial explains how to determine whether a given undirected graph contains a cycle.

Problem Statement

Given an undirected graph defined by a number of vertices V and a list of edges, the goal is to check for the presence of any cycle in the graph.

Example 1
Input:

				
					 V = 4

				
					 edges = [[0, 1], [0, 2], [1, 2], [2, 3]]

Output:

				
					 true

Explanation:
The connections in the graph form a cycle:

				
					 0 → 2 → 1 → 0.

This closed loop indicates the presence of a cycle.

Example 2

Input:

				
					 V = 4
 edges = [[0, 1], [1, 2], [2, 3]]

Output:
false

Explanation:
This graph represents a straight path without any repeated vertices or edges, so no cycle is formed.

Consider our Master DSA, Web Dev & System Design program for end-to-end learning.

Detect Cycle in an Undirected Graph Using BFS and DFS

Using Breadth-First Search (BFS) — Time: O(V + E), Space: O(V)

Breadth-First Search is a powerful technique for detecting cycles in an undirected graph. By exploring nodes level by level, BFS ensures the shortest path to each vertex and provides a reliable method to uncover cycles using minimal memory.

In this approach, we utilize:

A visited array to keep track of visited vertices.
A queue to perform level-order traversal.

During traversal:

Each node is dequeued and its unvisited neighbors are enqueued.
If we come across a node that is already visited and not the immediate parent, this indicates a cycle, as the node is accessible through multiple paths.

This level-wise traversal prevents redundant recursive calls and is particularly beneficial in handling large graphs more efficiently than DFS.

Note: You can refer to the complete implementation guide here: Detect Cycle in an Undirected Graph using BFS.

Using Depth-First Search (DFS) — Time: O(V + E), Space: O(V)

Depth-First Search is another effective method to detect cycles in undirected graphs. It explores as far as possible along each branch before backtracking, which can help reveal cycles in deeper layers of the graph.

However, unlike BFS, DFS requires an additional check:

Since the graph is undirected, an edge from u to v is also from v to u.
To prevent falsely detecting a cycle, we track the parent node during traversal.
A cycle exists only if a visited neighbor is not the parent of the current node.

Steps to Implement the DFS Approach:

Iterate through all nodes in the graph.
Maintain a visited[] array to mark visited vertices.
For every unvisited node, initiate a DFS call with its parent set to -1.
Inside DFS:

Mark the current node as visited.
Traverse all adjacent nodes:
If a neighbor is unvisited, recursively apply DFS on it.
If a neighbor is already visited and not the parent, a cycle is detected.

5. If no such condition is met during traversal, return false.

This strategy ensures accurate cycle detection in undirected graphs while maintaining optimal time and space complexity.

DFS-Based Cycle Detection: Code Implementation

Below is the implementation of the DFS approach for cycle detection in an undirected graph.

				
					// A C++ Program to detect cycle in an undirected graph
#include <bits/stdc++.h>
using namespace std;

bool isCycleUtil(int v, vector<vector<int>> &adj, vector<bool> &visited, int parent)
{
    // Mark the current node as visited
    visited[v] = true;

    // Recur for all the vertices adjacent to this vertex
    for (int i : adj[v])
    {
        // If an adjacent vertex is not visited, then recur for that adjacent
        if (!visited[i])
        {
            if (isCycleUtil(i, adj, visited, v))
                return true;
        }
        // If an adjacent vertex is visited and is not parent of current vertex,
        // then there exists a cycle in the graph.
        else if (i != parent)
            return true;
    }

    return false;
}
vector<vector<int>> constructadj(int V, vector<vector<int>> &edges){
    
    vector<vector<int>> adj(V);
    for (auto it : edges)
    {
        adj[it[0]].push_back(it[1]);
        adj[it[1]].push_back(it[0]);
    }
    
    return adj;
}
// Returns true if the graph contains a cycle, else false.
bool isCycle(int V, vector<vector<int>> &edges)
{
    
    vector<vector<int>> adj = constructadj(V,edges);
    // Mark all the vertices as not visited
    vector<bool> visited(V, false);

    for (int u = 0; u < V; u++)
    {
        if (!visited[u])
        {
            if (isCycleUtil(u, adj, visited, -1))
                return true;
        }
    }

    return false;
}

int main()
{
    int V = 5;
    vector<vector<int>> edges = {{0, 1}, {0, 2}, {0, 3}, {1, 2}, {3, 4}};

    if (isCycle(V, edges))
    {
        cout << "true" << endl;
    }
    else
    {
        cout << "false" << endl;
    }

    return 0;
}

				
					import java.util.*;

{
    // Helper function to check cycle using DFS
    static boolean isCycleUtil(int v, List<Integer>[] adj,
                               boolean[] visited,
                               int parent)
    {
        visited[v] = true;
        // If an adjacent vertex is not visited,
        // then recur for that adjacent
        for (int i : adj[v]) {
            if (!visited[i]) {
                if (isCycleUtil(i, adj, visited, v))
                    return true;
            }
            // If an adjacent vertex is visited and
            // is not parent of current vertex,
            // then there exists a cycle in the graph.
            else if (i != parent) {
                return true;
            }
        }
        return false;
    }
    static  List<Integer>[] constructadj(int V, int [][] edges){
        
        List<Integer>[] adj = new ArrayList[V];

        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
        
        return adj;
    } 
    // Function to check if graph contains a cycle
    static boolean isCycle(int V, int[][] edges)
    {
        List<Integer> [] adj = constructadj(V,edges);
        
        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }

        boolean[] visited = new boolean[V];
        // Call the recursive helper function
        // to detect cycle in different DFS trees
        for (int u = 0; u < V; u++) {
            if (!visited[u]) {
                if (isCycleUtil(u, adj, visited, -1))
                    return true;
            }
        }
        return false;
    }

    public static void main(String[] args)
    {
        int V = 5;
        int[][] edges = {
            {0, 1}, {0, 2}, {0, 3}, {1, 2}, {3, 4}
        };

        if (isCycle(V, edges)) {
            System.out.println("true");
        }
        else {
            System.out.println("false");
        }
    }
}

				
					// Helper function to check cycle using DFS
function isCycleUtil(v, adj, visited, parent)
{
    visited[v] = true;

    for (let i of adj[v]) {
        if (!visited[i]) {
            if (isCycleUtil(i, adj, visited, v)) {
                return true;
            }
        }
        else if (i !== parent) {
            return true;
        }
    }
    return false;
}

function constructadj(V, edges){
    let adj = Array.from({length : V}, () => []);

    // Build the adjacency list
    for (let edge of edges) {
        let [u, v] = edge;
        adj[u].push(v);
        adj[v].push(u);
    }
    return adj;
}
// Function to check if graph contains a cycle
function isCycle(V, edges)
{
    let adj = constructadj(V,edges);

    let visited = new Array(V).fill(false);

    // Check each node
    for (let u = 0; u < V; u++) {
        if (!visited[u]) {
            if (isCycleUtil(u, adj, visited, -1)) {
                return true;
            }
        }
    }
    return false;
}

// Driver Code
const V = 5;
const edges =
    [[0, 1], [0, 2], [0, 3], [1, 2], [3, 4]];

if (isCycle(V, edges)) {
    console.log("true");
}
else {
    console.log("false");
}

				
					# Helper function to check cycle using DFS
def isCycleUtil(v, adj, visited, parent):
    visited[v] = True

    for i in adj[v]:
        if not visited[i]:
            if isCycleUtil(i, adj, visited, v):
                return True
        elif i != parent:
            return True
    return False

def constructadj(V, edges):
    adj = [[] for _ in range(V)]  # Initialize adjacency list

    for edge in edges:
        u, v = edge
        adj[u].append(v)
        adj[v].append(u)
    
    return adj

# Function to check if graph contains a cycle
def isCycle(V, edges):
    
    adj = constructadj(V,edges)
    visited = [False] * V

    for u in range(V):
        if not visited[u]:
            if isCycleUtil(u, adj, visited, -1):
                return True
    return False


# Driver Code
if __name__ == "__main__":
    V = 5
    edges = [(0, 1), (0, 2), (0, 3), (1, 2), (3, 4)]

    if isCycle(V, edges):
        print("true")
    else:
        print("false")

Output

true

Time Complexity:

O(V + E) — The DFS algorithm visits every vertex once (O(V)) and explores each edge exactly once (O(E)).

Auxiliary Space:

O(V) — Space is required for the visited array and the recursive call stack during DFS traversal.

Note: The adjacency list is not included in the auxiliary space calculation, as it is part of the input representation of the graph.

For deeper insights, explore our comprehensive Master DSA, Web Dev & System Design program.

FAQs

What distinguishes cycle detection in undirected vs. directed graphs?

In undirected graphs, a back-edge to any visited node that isn’t the immediate parent indicates a cycle. In directed graphs, cycle detection often uses DFS with recursion stack tracking or Kahn’s algorithm (topological sort) to spot back-edges respecting edge direction.

Can I use BFS instead of DFS for cycle detection?

Yes. BFS tracks parent nodes similarly: when encountering a visited neighbor that is not the parent during level-order traversal, a cycle is detected. BFS may be preferable when you also need shortest-path information.

How do I handle disconnected graphs?

Iterate through all vertices; for each unvisited vertex, initiate BFS or DFS. This ensures each connected component is checked for cycles independently.

DSA, High & Low Level System Designs

85+ Live Classes & Recordings
24*7 Live Doubt Support
400+ DSA Practice Questions
Comprehensive Notes
HackerRank Tests & Quizzes
Topic-wise Quizzes
Case Studies
Access to Global Peer Community

Buy for 60% OFF
₹25,000.00 ₹9,999.00

Accelerate your Path to a Product based Career

Boost your career or get hired at top product-based companies by joining our expertly crafted courses. Gain practical skills and real-world knowledge to help you succeed.

Reach Out Now

If you have any queries, please fill out this form. We will surely reach out to you.

Contact Email

Reach us at the following email address.

[email protected]

Phone Number

You can reach us by phone as well.

+91-97737 28034

Our Location

Rohini, Sector-3, Delhi-110085

How to Detect a Cycle in an Undirected Graph

Introduction

Problem Statement

Example 1Input:

Output:

Explanation:The connections in the graph form a cycle:

This closed loop indicates the presence of a cycle.

Example 2

Input:

Detect Cycle in an Undirected Graph Using BFS and DFS

Using Breadth-First Search (BFS) — Time: O(V + E), Space: O(V)

Using Depth-First Search (DFS) — Time: O(V + E), Space: O(V)

Steps to Implement the DFS Approach:

DFS-Based Cycle Detection: Code Implementation

Output

Time Complexity:

Auxiliary Space:

FAQs

What distinguishes cycle detection in undirected vs. directed graphs?

Can I use BFS instead of DFS for cycle detection?

How do I handle disconnected graphs?

DSA, High & Low Level System Designs

Buy for 60% OFF ₹25,000.00 ₹9,999.00

Accelerate your Path to a Product based Career

Essentials of Machine Learning and Artificial Intelligence

Buy for 65% OFF ₹20,000.00 ₹6,999.00

Fast-Track to Full Spectrum Software Engineering

Buy for 57% OFF ₹35,000.00 ₹14,999.00

DSA, High & Low Level System Designs

Buy for 60% OFF ₹25,000.00 ₹9,999.00

Low & High Level System Design

Buy for 65% OFF ₹20,000.00 ₹6,999.00

Mastering Mern Stack (WEB DEVELOPMENT)

Buy for 60% OFF ₹15,000.00 ₹5,999.00

10 Day Google Interview Preparation Bootcamp

Reach Out Now

Contact Email

Phone Number

Our Location

Quick Links

Quick Links

Social Media

Master Your Interviews with Our Free Roadmap!

Hi Instagram Fam! Get a FREE Cheat Sheet on System Design.

Hi LinkedIn Fam! Get a FREE Cheat Sheet on System Design

Loved Our YouTube Videos? Get a FREE Cheat Sheet on System Design.

Example 1
Input:

Explanation:
The connections in the graph form a cycle:

Buy for 60% OFF
₹25,000.00 ₹9,999.00

Buy for 65% OFF
₹20,000.00 ₹6,999.00

Buy for 57% OFF
₹35,000.00 ₹14,999.00

Buy for 60% OFF
₹25,000.00 ₹9,999.00

Buy for 65% OFF
₹20,000.00 ₹6,999.00

Buy for 60% OFF
₹15,000.00 ₹5,999.00

Hi Instagram Fam!
Get a FREE Cheat Sheet on System Design.

Hi LinkedIn Fam!
Get a FREE Cheat Sheet on System Design