Graph Cycle Detection: Directed and Undirected Graphs Explained

You open a graph question in a placement online assessment, build an adjacency list, run standard DFS, and hit a TLE or Wrong Answer because you treated a directed graph like an undirected one. Graph cycle detection requires matching the direction of your edges to the right algorithm: Union-Find for undirected graphs and Kahn's algorithm for directed graphs.

Undirected Graphs: Skip DFS and Use Union-Find

In undirected graphs, an edge between node 0 and node 1 means you can walk back and forth. If you use basic DFS without keeping track of the parent node, node 1 will look back at node 0 and false-alarm a cycle. Passing a parent parameter in DFS solves this, but Union-Find (Disjoint Set Union) is better when the input is an edge list like [[0, 1], [1, 2], [2, 0]].

With Union-Find, you initialize a parent array where parent[i] = i. Process each edge (u, v). Find the root representative of u and v. If find(u) == find(v), you found a cycle. If not, call union(u, v).

Here is the exact hand trace for 3 nodes and edge list [[0, 1], [1, 2], [2, 0]]:

Initial state: parent = [0, 1, 2].

Process edge (0, 1): find(0) returns 0, find(1) returns 1. Roots are different. Set parent[1] = 0. Process edge (1, 2): find(1) returns 0, find(2) returns 2. Roots are different. Set parent[2] = 0. Process edge (2, 0): find(2) returns 0, find(0) returns 0. Roots match. Both nodes already connect to 0. A cycle exists.

This approach takes O(E * alpha(V)) time and avoids building an explicit adjacency list.

Directed Graphs: Use Kahn's Algorithm

Parent tracking fails completely in directed graphs. In a directed structure with edges 0 -> 1, 0 -> 2, and 1 -> 2, node 2 is reachable through two paths, but there is no loop. That is a Directed Acyclic Graph, not a cycle.

DFS for directed graphs requires three states: unvisited (0), visiting (1), and visited (2). A cycle exists if DFS reaches a node currently in state 1.

Kahn's algorithm using BFS and in-degrees is cleaner to implement under interview pressure.

Count the in-degree of every node. Push all nodes with in-degree 0 into a queue. Pop a node, increment a visited_count by 1, and decrement the in-degree of its neighbors. Whenever a neighbor's in-degree drops to 0, push it to the queue.

If visited_count equals total nodes V when the queue empties, the graph has no cycles. If visited_count is less than V, a cycle blocked the remaining nodes from reaching in-degree 0.

Spotting Hidden Cycle Problems

Interviewers rarely label these questions directly. They wrap graph structures in real-world descriptions.

Course Schedule (LeetCode 207) gives you prerequisite pairs. If course 1 needs course 0, and course 0 needs course 1, you cannot complete your degree. That is directed cycle detection.

Redundant Connection (LeetCode 684) gives N edges for N nodes in an undirected graph. One edge forms a cycle. Returning the edge that creates the loop is undirected cycle detection using Union-Find.

Find Eventual Safe States (LeetCode 802) asks for nodes that do not lead into a directed cycle.

Graph Cycle Decision Guide

Undirected edge list input: Use Union-Find with path compression. Directed graph checking validity or order: Use Kahn's algorithm with an in-degree array. Directed graph checking active recursive paths: Use DFS with a three-state array (0 unvisited, 1 visiting, 2 visited). Grid traversal: Treat adjacent cells as undirected edges while tracking visited positions.

Practicing Graph Pattern Recognition

When solving graph problems on DSA Tracker or LeetCode, write the direction of the edges at the top of your scratchpad before writing any code. Open Course Schedule today and implement it using Kahn's algorithm to lock in the pattern.

Keep going with the step-by-step visualizer and practice problems.

Further reading: Breadth-first search on Wikipedia.