LESSON 112 · DEEPER PYTHON30 min

Detect Directed Graph Cycles with DFS

Detect whether a directed adjacency-list graph contains a cycle.

Before you start: Dictionaries · Functions · Understand Recursion and the Call Stack

Example check: Worked and guided code samples are checked against CPython 3.13. Practice uses Pyodide 0.29.5 (Python 3.13) in your browser. How we check lessons

WATCH

Video lesson: Detect Directed Graph Cycles with DFS

The preview is stored on this site. YouTube loads only when you press Play. Watch on YouTube

Jump to a chapter

Read the video transcript

Select a timestamp to watch that moment on YouTube.

00:00
Two branches of a dependency graph both lead to D. Does that make a cycle? Run the one-set detector and watch it falsely report True. The broken DFS keeps just a visited set. It finishes D through one branch, then reaches D from another branch and treats that repeat as a cycle. Its True output would reject a legal task graph. Reaching a completed node is different from returning to a node still active in the current chain. Draw the diamond described by the source: A points to B and C, and both B and C point to D. The first recursive branch visits D and returns. When the second branch sees D, the one-set algorithm calls it a cycle because D is
00:42
already marked visited. But there is no arrow leaving D that leads back to A, B, or C. The True output is a false alarm caused by confusing past work with the current recursive path. The diagnosis prints the shared target D twice and shows that D has no outgoing edges. The path A to C to D cannot return to A. Label nodes active while DFS explores their descendants, and finished after it returns. Only an edge to an active node proves a directed cycle. At a DFS call boundary, a node is active from entry until all its outgoing calls finish.
01:23
A neighbor in that active collection points back into the path we are still exploring. A neighbor in the done collection belongs to a completed branch. In the diagnosis output D is shared but has no outgoing edges, so it cannot produce a return path. Printing the shared target twice is the clue; it proves only two references to D, not a directed loop. The active set is local to an unfinished DFS chain, though one collection can be shared through recursive calls. Suppose the search finishes the entire A component, then begins a disconnected E component. Active must be empty between those roots, while done retains completed nodes.
02:05
That is why the algorithm can discover a cycle in a component not reachable from the first chosen starting node. Color the diamond by hand. A enters gray, then B and D enter gray in turn. D has no outgoing edge, so it becomes black before B finishes. Later A explores C and sees an edge to black D. Black means the entire D branch already returned; there is no path from D back into the active call chain. A single visited mark cannot represent that distinction. The gray-versus-black question must be asked at the moment an edge is inspected. The fixed detector maintains active and done sets.
02:46
It moves a node from active to done after exploring neighbors and prints False for the diamond graph. Starting DFS from every graph key covers components disconnected from A; recursive visits also reach referenced neighbors. Read the state transition in the repaired function. On entry, place the node in active. If an outgoing neighbor is already active, report a cycle at once. When the neighbor is done, skip it; that subgraph was checked already. On normal return, remove the node from active and place it in done. The diamond finishes with False because D is done before the second branch reaches it.
03:26
The outer loop starts at graph keys; recursive calls also visit neighbor-only vertices. Now change the graph to A points to B, B points to C, and C points back to A. While exploring C, A is still active, so that last edge proves a directed cycle. It differs from the diamond's second arrival at D, because D had already finished there. For an iterative version, a stack entry needs both a node and a position among its remaining neighbors. Otherwise the program cannot know when to remove the node from active after its descendants have been checked. The verifier prints True for a self-loop and False for an empty graph.
04:07
Deep recursive DFS can hit Python's recursion limit, so an iterative color- state algorithm is safer for unbounded input. The rule shown here is for directed dependencies; undirected traversal must ignore its immediate parent edge. A self-edge from X to X points at the node currently on the call stack, so the first printed result is True. An empty dictionary has no edges and prints False. Those boundaries test opposite sides of the definition. A two-node loop would also be detected when traversal returns to its active ancestor. Recursive code is readable for small lesson graphs; an untrusted chain
04:48
thousands of nodes deep may hit the recursion limit, so use an explicit stack there. In an iterative implementation, a stack entry needs an enter or exit state so we know when to move a node from active to done. Merely pushing all neighbors and adding them to visited recreates the original mistake. A dependency planner can reject a graph once a back edge is found; if it also needs to display the actual cycle, keep parent links to reconstruct it. A disconnected cycle gives another regression case. Let A point only to B, while a separate pair E and F point to each other. Starting DFS only at A reports no cycle, but scanning every graph component reaches
05:31
E and detects the return from F. This case tests the outer loop, whereas the visible self-loop tests the inner back-edge rule. Keep both tests because either omission can make a detector look correct on a single connected classroom graph.

THE IDEA

Understand the concept

A task dependency graph may have two branches that both point to the same completed task. That shared dependency is legal; a cycle means a path eventually returns to a node still active on the current DFS path. Detecting cycles correctly helps reject impossible dependency schedules.

A single visited set is insufficient for directed cycle detection. When the second branch reaches a node that the first branch already finished, naive code can call it a cycle even though no active path loops back. The graph A to B to D and A to C to D is a counterexample.

Trace the depth-first call stack and label nodes as active while their outgoing edges are being explored, then finished when the call returns. An edge to active means a back edge and a cycle. An edge to finished is just a repeated reference to work already explored. Maintain active and done sets. Entering a node adds it to active; after all descendants return without a cycle, move it to done. On a neighbor already active return True; on a done neighbor continue. Start DFS from every graph key to cover disconnected components; recursive visits also reach referenced neighbors.

A self-loop such as X to X is a cycle; an empty graph is not. The final run checks both. A deep graph can exceed Python's recursion limit, so an iterative color-state traversal is better when input depth is unbounded. This detector is for directed edges. For an undirected graph, the immediate edge back to a parent needs special treatment. Document graph representation and depth limits before using this recursive version on untrusted large graphs.

A task dependency graph may have two branches that both point to the same completed task.
A single visited set is insufficient for directed cycle detection.
Maintain active and done sets.
A self-loop such as X to X is a cycle; an empty graph is not.

WORKED EXAMPLES

See it step by step

Read the code, predict the output, then compare it with the result.

01. Shared target is not a cycle

PYTHON

graph={'A':['B','C'],'B':['D'],'C':['D'],'D':[]}
print(graph['B'][0] == graph['C'][0])
print('D' in graph['D'])

EXPECTED OUTPUT

True
False

Both branches reference D, but D has no edge back to an active ancestor.

02. A self-loop is a cycle

PYTHON

graph={'X':['X']}
print('X' in graph['X'])

EXPECTED OUTPUT

True

An edge from X to itself returns to a node still active on the path.

03. Model active and done states

PYTHON

active={'A','C'}; done={'B','D'}
print('D' in active, 'D' in done)
print('A' in active)

EXPECTED OUTPUT

False True
True

A finished node can be encountered again safely; an active ancestor indicates a back edge.

GO DEEPER

A closer look

Follow the reasoning, inspect each result, then try the suggested changes in the console below.

01 / 03

Observe the first result

A task dependency graph may have two branches that both point to the same completed task. That shared dependency is legal; a cycle means a path eventually returns to a node still active on the current DFS path. Detecting cycles correctly helps reject impossible dependency schedules.

Both branches reference D, but D has no edge back to an active ancestor. Trace the depth-first call stack and label nodes as active while their outgoing edges are being explored, then finished when the call returns. An edge to active means a back edge and a cycle. An edge to finished is just a repeated reference to work already explored.

PYTHON

graph={'A':['B','C'],'B':['D'],'C':['D'],'D':[]}
print(graph['B'][0] == graph['C'][0])
print('D' in graph['D'])

EXPECTED OUTPUT

True
False

Follow the reasoning

Predict the first sample's printed value and type.
Run it, then compare with the expected output.

02 / 03

Change the rule deliberately

A single visited set is insufficient for directed cycle detection. When the second branch reaches a node that the first branch already finished, naive code can call it a cycle even though no active path loops back. The graph A to B to D and A to C to D is a counterexample.

An edge from X to itself returns to a node still active on the path. Maintain active and done sets. Entering a node adds it to active; after all descendants return without a cycle, move it to done. On a neighbor already active return True; on a done neighbor continue. Start DFS from every graph key to cover disconnected components; recursive visits also reach referenced neighbors. On entry add node to active; on normal exit remove it and add to done. Check active before descending; skip done nodes.

PYTHON

graph={'X':['X']}
print('X' in graph['X'])

EXPECTED OUTPUT

True

Follow the reasoning

Identify the line that changes the rule.
Run the corrected sample with the same input.

03 / 03

Verify the boundary

Trace the depth-first call stack and label nodes as active while their outgoing edges are being explored, then finished when the call returns. An edge to active means a back edge and a cycle. An edge to finished is just a repeated reference to work already explored. Maintain active and done sets. Entering a node adds it to active; after all descendants return without a cycle, move it to done. On a neighbor already active return True; on a done neighbor continue. Start DFS from every graph key to cover disconnected components; recursive visits also reach referenced neighbors.

A finished node can be encountered again safely; an active ancestor indicates a back edge. A self-loop such as X to X is a cycle; an empty graph is not. The final run checks both. A deep graph can exceed Python's recursion limit, so an iterative color-state traversal is better when input depth is unbounded. This detector is for directed edges. For an undirected graph, the immediate edge back to a parent needs special treatment. Document graph representation and depth limits before using this recursive version on untrusted large graphs.

PYTHON

active={'A','C'}; done={'B','D'}
print('D' in active, 'D' in done)
print('A' in active)

EXPECTED OUTPUT

False True
True

Follow the reasoning

Try the documented edge case.
Explain why the output satisfies the function contract.

HANDS-ON

Try it in Python

Edit the example and run it. Python starts in your browser the first time you click Run.

Python console

Ready to run

def has_cycle(graph):
    visited = set()
    def visit(node):
        if node in visited: return True
        visited.add(node)
        return any(visit(nxt) for nxt in graph.get(node, []))
    return any(visit(node) for node in graph)

print(has_cycle({'A':['B','C'], 'B':['D'], 'C':['D'], 'D':[]}))

Need input()? Add one value per line

Input lines

Ctrl / ⌘ + Enter to run

OUTPUT

Your output appears here.

Your turnReplace the single visited set with active and done states so a shared finished node is not a cycle. Return True for an actual directed cycle or self-loop and False for an acyclic graph.

Need a hint?

On entry add node to active; on normal exit remove it and add to done. Check active before descending; skip done nodes.

Complete the task and select Check task to verify your code.

DEBUG BETTER

Typical mistakes

Everyone meets these errors. See what causes them and how to fix them.

The visible failure

COMMON MISTAKE

if neighbor in visited: return True

FIX

if neighbor in active: return True; if neighbor in done: continue

What happens: A single visited set is insufficient for directed cycle detection.
Maintain active and done sets. Entering a node adds it to active; after all descendants return without a cycle, move it to done. On a neighbor already active return True; on a done neighbor continue. Start DFS from every graph key to cover disconnected components; recursive visits also reach referenced neighbors.

Missing the edge condition

COMMON MISTAKE

search only graph.keys() without referenced nodes

FIX

include nodes appearing in adjacency values too

What happens: A self-loop such as X to X is a cycle; an empty graph is not.
This detector is for directed edges. For an undirected graph, the immediate edge back to a parent needs special treatment. Document graph representation and depth limits before using this recursive version on untrusted large graphs.

Browse this lesson’s problem fixes

VERIFY THE STORY

Sources and further reading

Python recursion limit