Cycle Detection in Undirected Graphs with DFS

1. The Challenge of Undirected Cycles

In a DFS traversal, the fundamental sign of a cycle is encountering a node that has already been visited. However, in an undirected graph, this simple rule has a catch.

Consider an edge between nodes A and B. When your DFS moves from A to B, node A is marked as visited. From B, one of its neighbors is A. Since the edge is undirected, you can immediately travel back to A. A is already visited, but A -> B -> A is not what we consider a cycle; it's just traversing an edge back and forth.

So, how do we distinguish a true cycle from simply returning to the node we just came from?

The solution is to keep track of the parent of the current node in the DFS traversal. The "parent" is the node from which we arrived at the current node.

The rule for detecting a cycle then becomes:

During a DFS traversal, if we encounter a neighbor that is already visited and is not the immediate parent of the current node, we have found a cycle.

This parent tracking is the key modification to the standard DFS algorithm for this problem. The article "Detect Cycle in a Graph" explains this distinction clearly.

2. The DFS Algorithm with Parent Tracking

Let's see this logic in action. The core idea is to augment our recursive DFS function to accept two arguments: the current node and its parent.

To get a complete picture of the algorithm, including a step-by-step dry run, watch the following video.

As the video demonstrates, the algorithm can be summarized as follows:

1. Initialize a visited array (or set) for all vertices.
2. Create a main function that iterates through all vertices from 0 to V-1. This handles disconnected graphs (graphs with multiple components).
3. If a vertex i has not been visited, start a DFS from it. The initial call will be dfs(i, -1), as the starting node has no parent.
4. The recursive dfs(node, parent) function does the following:
   • Mark node as visited.
   • For each neighbor of node:
     • If neighbor has not been visited, recursively call dfs(neighbor, node). If that call returns true (meaning a cycle was found deeper in the traversal), immediately propagate true up the call stack.
     • If neighbor has been visited, check if neighbor != parent. If this is true, you've found a back edge. Return true.
   • If the loop completes without finding a cycle, return false.

3. Python Implementation and Complexity

Your background in Python and your goal of preparing for interviews make it crucial to have a clean, standard implementation ready. The following resource provides exactly that.

Here's the Python implementation, which directly mirrors the logic we've discussed:

class Solution:
    # V: number of vertices
    # adj: adjacency list
    def isCycle(self, V, adj):
        visited = [False] * V

        # Loop to handle disconnected components
        for i in range(V):
            if not visited[i]:
                # If DFS from this node finds a cycle, return True
                if self.dfs(i, -1, adj, visited):
                    return True
        
        # If no component has a cycle
        return False

    def dfs(self, node, parent, adj, visited):
        visited[node] = True
        
        for neighbor in adj[node]:
            # If neighbor is not visited, recurse
            if not visited[neighbor]:
                if self.dfs(neighbor, node, adj, visited):
                    return True
            # If neighbor is visited and is NOT the parent
            elif neighbor != parent:
                # Cycle detected
                return True
        
        # No cycle found from this path
        return False

Complexity Analysis

Understanding the performance of your algorithms is non-negotiable in an interview setting.

• Time Complexity: $O(V+E)$

  • Where $V$ is the number of vertices and $E$ is the number of edges.
  • The DFS traversal visits every vertex and every edge exactly once across all components. The outer loop ensures we cover disconnected parts of the graph, but the total work is still proportional to the total number of vertices and edges.

• Space Complexity: $O(V)$

  • visited array: This takes $O(V)$ space.
  • Recursion Stack: In the worst-case scenario (a long, path-like graph), the depth of the recursion can be up to $V$. Therefore, the call stack requires $O(V)$ space.
  • The total space complexity is dominated by these factors, resulting in $O(V)$.

The "take U forward" video also provides a good summary of this analysis.

4. Application: Validating a Tree

A very common interview problem that builds directly on this concept is "Graph Valid Tree" (LeetCode 261). A graph is a valid tree if and only if two conditions are met:

1. The graph contains no cycles.
2. The graph is fully connected (i.e., it has exactly V-1 edges and all nodes are reachable from a single source).

You now know how to solve the first part of this problem.

Conclusion

In this lesson, you've added a crucial graph algorithm to your interview arsenal. Detecting cycles is a fundamental problem, and the DFS-based approach for undirected graphs is the standard, efficient solution.

Key Takeaways:

• A simple "is visited?" check is not enough to detect cycles in an undirected graph because of bidirectional edges.
• The correct approach is to use DFS while tracking the parent of each node in the traversal path.
• A cycle is detected when you encounter a visited neighbor that is not the node's immediate parent.
• To handle disconnected graphs, a loop in the main function must attempt a DFS from every unvisited vertex.
• The algorithm runs in $O(V+E)$ time and requires $O(V)$ space.

Preview of the Next Lesson:

What about cycles in directed graphs? The parent trick won't work there, because an edge A -> B doesn't imply an edge B -> A. An edge from a node to a previously visited node could be a cross-edge to a different branch, not necessarily a back-edge forming a cycle. In the next lesson, we will explore how to detect cycles in directed graphs using DFS, which requires a more nuanced three-state tracking system (visiting, visited, unvisited).