Course contentsShow
← Computer Science
Lesson 713 of 2,87217. Graph Traversal AlgorithmsFree lesson

Cycle Detection with DFS

Detect cycles in directed and undirected graphs using DFS and edge classification.

Cycle Detection with DFS

What you'll learn: How to use Depth-First Search to detect cycles in both directed and undirected graphs by classifying the edges you encounter.

The Core Idea

When DFS traverses a graph, it discovers different types of edges based on where they lead. By recognizing certain edge patterns, you can detect whether a cycle exists without explicitly tracing the entire loop.

Think of it like exploring a mansion: if you walk down a hallway and suddenly find a door that leads back to a room you're currently inside (not just one you visited earlier), you've discovered a loop in the building's layout.

How It Works

For undirected graphs, a cycle exists if during DFS you encounter an edge leading to an already-visited node that isn't your immediate parent. Since edges go both ways, you need to ignore the edge you just came from.

For directed graphs, a cycle exists if you encounter a back edge—an edge pointing to a node that's currently in your DFS recursion stack (still being explored). This indicates you've circled back to an ancestor in the DFS tree.

Implementation Pattern

# Undirected graph cycle detection
def has_cycle_undirected(graph):
    visited = set()
    
    def dfs(node, parent):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:  # Back to non-parent = cycle
                return True
        return False
    
    return any(dfs(node, -1) for node in graph if node not in visited)

The key difference for directed graphs: track nodes in the current path (recursion stack) separately from globally visited nodes.

Key Takeaway: Cycle detection with DFS relies on edge classification—finding back edges in directed graphs or non-parent edges to visited nodes in undirected graphs signals a cycle.