Cycle Detection in Undirected Graphs (BFS/DFS)

1. The Intuition: Why Parent Tracking is Key

In an undirected graph, if there's an edge from node u to v, the adjacency list for v will contain u. When you traverse from u to v, and then look at v's neighbors, you'll immediately see u again. If you just check "is this neighbor visited?", you'd incorrectly flag this as a cycle.

The solution is to ask a more specific question: "Have I found a visited neighbor that is not the node I just came from (my parent)?" If the answer is yes, you've found a back edge that completes a cycle.

In the graph on the left, traversing from 1 to 2, we see neighbor 0 is visited. Since 0 is the parent of 1, this is not a cycle. In the graph on the right, traversing from 2 to 3, we see neighbor 1 is visited. Since 1 is NOT the parent of 3 (2 is), we have found a cycle.

2. Cycle Detection with Breadth-First Search (BFS)

The core idea of using BFS for cycle detection is to see if a traversal from two different directions "collides" on a node.

When performing BFS, we explore the graph layer by layer. If we are at a node u and encounter a neighbor v that has already been visited (and is not u's immediate parent), it means that v was reached via another path of the same or shorter length. This convergence of paths signifies a cycle.

To implement this, we'll modify our standard BFS:

• The queue will store pairs of (node, parent).
• When we explore a node's neighbors, we check for the cycle condition described above.

This video from "take U forward" provides an excellent walkthrough of this exact logic.

BFS Implementation

After watching the video, the logic should be clear. Here is a complete Java implementation. A key part is the main isCycle function, which iterates through all vertices. This ensures our code works correctly even if the graph has multiple disconnected components—a crucial detail for robust solutions.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class Pair {
    int node;
    int parent;

    public Pair(int node, int parent) {
        this.node = node;
        this.parent = parent;
    }
}

public class CycleDetectionBFS {

    // Helper function to check for a cycle starting from a given source node
    private static boolean checkForCycle(int src, int V, ArrayList<ArrayList<Integer>> adj, boolean[] visited) {
        Queue<Pair> q = new LinkedList<>();
        visited[src] = true;
        q.add(new Pair(src, -1)); // Start with parent -1

        while (!q.isEmpty()) {
            int node = q.peek().node;
            int parent = q.peek().parent;
            q.poll();

            for (int adjacentNode : adj.get(node)) {
                if (!visited[adjacentNode]) {
                    visited[adjacentNode] = true;
                    q.add(new Pair(adjacentNode, node));
                } 
                // If the adjacent node is visited and is not the parent,
                // then a cycle exists.
                else if (adjacentNode != parent) {
                    return true;
                }
            }
        }
        return false;
    }

    // Main function to detect cycle in an undirected graph
    public static boolean isCycle(int V, ArrayList<ArrayList<Integer>> adj) {
        boolean[] visited = new boolean[V];
        // Loop through all vertices to handle disconnected components
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                if (checkForCycle(i, V, adj, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        // Graph with a cycle: 1-2-4-1
        int V = 5;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
        adj.get(0).add(1);
        adj.get(1).add(0);
        
        adj.get(1).add(2);
        adj.get(2).add(1);

        adj.get(2).add(4);
        adj.get(4).add(2);

        adj.get(1).add(4);
        adj.get(4).add(1);

        adj.get(0).add(3);
        adj.get(3).add(0);

        if (isCycle(V, adj)) {
            System.out.println("Cycle detected using BFS.");
        } else {
            System.out.println("No cycle detected using BFS.");
        }
    }
}

3. Cycle Detection with Depth-First Search (DFS)

The logic for DFS is similar but manifests differently due to its recursive nature. During a DFS traversal, if we encounter a neighbor that is already visited and is not our immediate parent, it means we have found a "back edge" to a node that is currently in our recursion stack (an ancestor in the DFS tree). This back edge confirms a cycle.

The implementation involves passing the parent node down through the recursive calls.

Let's watch the DFS counterpart video from the same channel to see this in action.

DFS Implementation

The recursive DFS solution is often considered more concise. We'll follow the structure from the video and the provided resources to create our Java implementation. Once again, we need a main loop to handle disconnected graphs.

Here's the full code, which you can run and test.

import java.util.ArrayList;

public class CycleDetectionDFS {

    // Recursive helper function for DFS
    private static boolean dfs(int node, int parent, boolean[] visited, ArrayList<ArrayList<Integer>> adj) {
        visited[node] = true;

        for (int adjacentNode : adj.get(node)) {
            if (!visited[adjacentNode]) {
                // If a recursive call finds a cycle, propagate the result up
                if (dfs(adjacentNode, node, visited, adj)) {
                    return true;
                }
            } 
            // If the adjacent node is visited and is not the parent, a cycle is found
            else if (adjacentNode != parent) {
                return true;
            }
        }
        return false;
    }

    // Main function to detect cycle in an undirected graph
    public static boolean isCycle(int V, ArrayList<ArrayList<Integer>> adj) {
        boolean[] visited = new boolean[V];
        // Loop through all vertices to handle disconnected graphs
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                if (dfs(i, -1, visited, adj)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        // Graph with a cycle: 1-2-4-1
        int V = 5;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
        adj.get(0).add(1);
        adj.get(1).add(0);
        
        adj.get(1).add(2);
        adj.get(2).add(1);

        adj.get(2).add(4);
        adj.get(4).add(2);

        adj.get(1).add(4);
        adj.get(4).add(1);

        adj.get(0).add(3);
        adj.get(3).add(0);

        if (isCycle(V, adj)) {
            System.out.println("Cycle detected using DFS.");
        } else {
            System.out.println("No cycle detected using DFS.");
        }
    }
}

4. Complexity Analysis

One of the great things about these solutions is that their performance is identical and directly tied to the traversal itself.

• Time Complexity: O(V + E)
  • This is the standard time complexity for both BFS and DFS. We visit each vertex (V) and traverse each edge (E) at most once (or twice in an undirected graph, which is still proportional to E).
• Space Complexity: O(V)
  • We use a visited array of size V.
  • For BFS, the queue can hold up to O(V) nodes in the worst case (for a star graph, for example).
  • For DFS, the recursion stack can go up to O(V) deep in the worst case (for a path graph).

Conclusion

Congratulations! You've successfully applied graph traversal algorithms to solve a significant problem. This is a big step towards preparing for technical interviews, where such questions are very common.

Key Takeaways:

• A cycle in an undirected graph is found by detecting a back edge to a node that is already visited but is not the immediate parent.
• The BFS approach uses a queue of (node, parent) pairs to track this relationship.
• The DFS approach passes the parent as a parameter in its recursive calls.
• For both methods, it's essential to have a main loop that iterates through all vertices to correctly handle disconnected graphs.
• Both algorithms run in O(V + E) time and use O(V) auxiliary space.

Preview of the Next Lesson:
Our focus so far has been on undirected graphs. What happens when the edges have a direction? In our next lesson, we will tackle detecting a cycle in a directed graph. You'll find that the parent-checking trick no longer works, and we'll need a new strategy to distinguish between a valid path and a cycle.