Detecting Cycles in Undirected Graphs

Welcome to the next lesson in our module on graph traversal. In our previous session, you learned a powerful technique: treating a 2D grid as an implicit graph and using Depth-First Search (DFS) to count its connected components, like islands in an ocean. This involved a standard DFS traversal augmented with a visited set to avoid reprocessing nodes.

Today, we'll build directly on that foundation. We will use DFS to solve another fundamental graph problem: detecting the presence of a cycle in an undirected graph. You'll discover that a small but crucial modification to the DFS algorithm we've already learned is all that's needed. By the end of this lesson, you will be able to implement a "parent-aware" traversal to reliably determine if an undirected graph contains a cycle.

The Challenge of Undirected Cycles

First, let's be clear about what a cycle is. In an undirected graph, a cycle is a path that starts at a vertex, visits one or more other vertices, and returns to the starting vertex without using the same edge twice.

Our first instinct might be to use the DFS approach from our last lesson. During the traversal, if we encounter a neighbor that's already in our visited set, have we found a cycle?

Let's consider a simple graph: A --- B.

1. We start DFS at A, mark it as visited.
2. We move to its neighbor, B.
3. From B, we look at its neighbors. One of them is A.
4. We check A. It's already in our visited set.

Does this mean we found a cycle? No. Because the graph is undirected, the edge between A and B is a two-way street. Moving from B back to A is simply traversing the same edge in reverse. This is just backtracking, not a cycle.

This reveals the core challenge: we need a way to distinguish between backtracking to the node we just came from and finding a "back edge" to an ancestor further up in the DFS path, which does indicate a cycle.

The Parent-Aware Traversal

The solution is to make our DFS "parent-aware." During the traversal, we need to keep track of not only the current node we are visiting but also the node we came from—its parent in the DFS tree.

The new logic becomes:
When exploring from a currentNode, for each neighbor:

• If the neighbor is the parentNode, we ignore it and continue. This prevents us from immediately backtracking and falsely detecting a cycle.
• If the neighbor is not the parentNode but is already visited, we have found a genuine cycle.
• Otherwise, the neighbor is unvisited, and we continue the traversal by making a recursive call: dfs(neighbor, currentNode).

The article from Algo.monster, "Detect Cycles in 2D Grid," provides an excellent explanation of this intuition, even though it's in the context of a grid. The logic is identical.

As you've just read, failing to account for the parent leads to an immediate false positive. By simply adding a parent parameter to our DFS function, we can elegantly solve this.

A Walkthrough with Parent-Aware DFS

Let's see this algorithm in action. The following video from the "take U forward" channel provides a detailed dry run of parent-aware DFS for cycle detection. It clearly shows the state of the visited array and the parent being passed at each recursive call.

Implementing in TypeScript

Now, let's translate this logic into a TypeScript implementation. Just like with counting connected components, our main function will iterate through all vertices to handle graphs that may have multiple disconnected components. It will call a recursive helper function on any unvisited vertex.

The helper function, isCyclicUtil, will perform the parent-aware DFS.

/**
 * Detects if a cycle exists in an undirected graph.
 * @param numNodes The total number of nodes in the graph (labeled 0 to numNodes-1).
 * @param adjacencyList The graph represented as an adjacency list.
 * @returns true if a cycle exists, false otherwise.
 */
function hasCycle(numNodes: number, adjacencyList: number[][]): boolean {
    const visited: boolean[] = new Array(numNodes).fill(false);

    // The recursive helper function
    // Returns true if a cycle is detected in the component starting from `node`.
    function isCyclicUtil(node: number, parent: number): boolean {
        visited[node] = true;

        for (const neighbor of adjacencyList[node]) {
            // If the neighbor is the parent, skip it.
            if (neighbor === parent) {
                continue;
            }

            // If the neighbor is visited and not the parent, we found a cycle.
            if (visited[neighbor]) {
                return true;
            }

            // Recurse for the unvisited neighbor.
            // If the recursive call finds a cycle, propagate the result.
            if (isCyclicUtil(neighbor, node)) {
                return true;
            }
        }

        // No cycle found from this path.
        return false;
    }

    // Iterate through all nodes to handle disconnected components.
    for (let i = 0; i < numNodes; i++) {
        if (!visited[i]) {
            // Start DFS from an unvisited node.
            // The initial parent is -1 (or any value that can't be a node).
            if (isCyclicUtil(i, -1)) {
                return true;
            }
        }
    }

    return false;
}

// Example Usage:
// A graph with a cycle 0-1-2-0
const adjListWithCycle = [
    [1, 2],
    [0, 2],
    [0, 1]
];
console.log(hasCycle(3, adjListWithCycle)); // Output: true

// A simple line graph with no cycle
const adjListWithoutCycle = [
    [1],
    [0, 2],
    [1]
];
console.log(hasCycle(3, adjListWithoutCycle)); // Output: false

This implementation pattern should feel familiar, as it closely mirrors the structure we used for counting islands. The primary difference is the added parent parameter and the specific logic for what to do when we encounter an already visited node.

Complexity Analysis

Your experience in development naturally leads to considering performance. The complexity of this algorithm is straightforward and efficient.

• Time Complexity: $O(V+E)$, where $V$ is the number of vertices and $E$ is the number of edges. This is because, in the worst case, the DFS traversal visits every vertex and every edge exactly once across all its calls.
• Space Complexity: $O(V)$. This space is consumed by two things:
  1. The visited array, which requires $O(V)$ space.
  2. The recursion call stack. In the worst case of a long, unbranched path (a "line" graph), the recursion depth can be up to $V$, so the stack space is $O(V)$.

Conclusion

In this lesson, you've adapted your knowledge of DFS to solve a new and important problem. By introducing a single piece of state—the parent node—you've made the traversal "smarter" and capable of distinguishing true cycles from simple backtracking in undirected graphs.

Key Takeaways:

• The Problem: Standard DFS is not enough for cycle detection in undirected graphs because every edge can be traversed in two directions, leading to false positives.
• The Solution: A "parent-aware" DFS, which keeps track of the node from which the current node was reached.
• The Core Logic: A cycle is detected if and only if the DFS encounters a neighbor that is already visited but is not the immediate parent.
• The Pattern: The overall structure involves a main loop to handle disconnected components and a recursive helper function that performs the traversal, a pattern you've now seen twice.

This concept of augmenting a traversal with more state is a powerful theme in graph algorithms. In our next lesson, we will tackle cycle detection in directed graphs. You will see that the parent-aware approach is insufficient there, and we'll need to introduce a three-state system (unvisited, visiting, visited) to handle the complexities of one-way edges.