Cycle detection looks like a one-liner: run a depth-first search and if you ever see a node twice, there’s a cycle. That works for undirected graphs, mostly. For directed graphs it’s wrong, and the reason is worth understanding properly, because the same distinction underlies topological sorting, deadlock detection, build systems and the Course Schedule problem.
Seeing a node twice is not a cycle
Take four tasks where A depends on B and C, and both of those depend on D. Draw it and you get a diamond: two paths from A down to D, but no way to get from any task back to itself. No cycle.
Here’s the tempting version, which treats any revisit as a cycle:
def has_cycle_naive(graph):
visited = set()
def dfs(u):
if u in visited:
return True # wrong: "seen before" is not "on the current path"
visited.add(u)
return any(dfs(v) for v in graph.get(u, []))
return any(dfs(u) for u in graph if u not in visited)
diamond = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print("naive, diamond:", has_cycle_naive(diamond))naive, diamond: TrueDFS goes A → B → D, finishes D, backs up, then tries A → C → D. D is already visited, so the naive check cries cycle. But D was finished long ago; it isn’t an ancestor of C. Reaching it again just means two routes lead to the same place, which is perfectly normal in a dependency graph.
What actually signals a cycle is reaching a node that’s still being explored, one whose DFS call hasn’t returned yet. That node is an ancestor of where you are now, so the edge you just followed leads back up your own path. Graph theory calls that a back edge, and a directed graph has a cycle exactly when a DFS finds one.
White, gray and black
To tell “finished” apart from “in progress”, give every node one of three colours:
- White: not visited yet.
- Gray: DFS has entered the node and hasn’t left. It’s on the current path.
- Black: DFS has explored everything reachable from the node and left.
An edge into a gray node is a back edge, so it’s a cycle. An edge into a black node is harmless: everything reachable from that node was already explored without finding a cycle back to the current path (otherwise we’d have stopped). An edge into a white node means keep exploring.
The version below also returns the cycle itself, which is far more useful in practice than True. A build tool that says “circular dependency” without naming the files is no fun to debug. Keeping the current path in a list makes it easy: when you hit a gray node v, the cycle is the slice of the path from v to the end.
WHITE, GRAY, BLACK = 0, 1, 2
def find_cycle(graph):
color = {u: WHITE for u in graph}
stack = [] # the current DFS path, in order
def dfs(u):
color[u] = GRAY
stack.append(u)
for v in graph.get(u, []):
if color.get(v, WHITE) == GRAY: # back edge: v is an ancestor on the path
return stack[stack.index(v):] + [v]
if color.get(v, WHITE) == WHITE:
found = dfs(v)
if found:
return found
stack.pop()
color[u] = BLACK # fully explored; can never be part of a new cycle
return None
for u in graph:
if color[u] == WHITE:
found = dfs(u)
if found:
return found
return NoneNow a module graph for a small service, where config has accidentally started importing auth:
deps = {
"app": ["auth", "billing"],
"auth": ["db"],
"billing": ["db", "auth"],
"db": ["config"],
"config": ["auth"],
}3-state, diamond: None
3-state, deps: ['auth', 'db', 'config', 'auth']
3-state, deps without config->auth: NoneThe diamond is correctly cycle-free. In the module graph, DFS goes app → auth → db → config, all gray, then sees config → auth while auth is still gray. The path slice from auth gives auth → db → config → auth, which is precisely the import loop to break. Remove that edge and the same graph comes back clean, even though db and auth are each reachable by more than one route.
Notice the order of operations at the end of dfs: pop from the path, then mark black. If you mark nodes black on entry, or forget the black state and reset to white on exit, you either miss cycles or re-explore the same subgraph many times. Resetting to white turns an O(V + E) algorithm into an exponential one on graphs with lots of shared descendants.
Undirected graphs need less
In an undirected graph every edge goes both ways, so the gray/black distinction collapses. What you need instead is to ignore the edge you just arrived on. Walking from 0 to 1 and immediately seeing 0 from 1 isn’t a cycle; it’s the same edge.
def undirected_has_cycle(n, edges):
adj = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
visited = [False] * n
def dfs(u, parent):
visited[u] = True
for v in adj[u]:
if v == parent:
continue # the edge we just came along, not a cycle
if visited[v] or dfs(v, u):
return True
return False
return any(not visited[u] and dfs(u, -1) for u in range(n))False True TrueThose are a tree (edges 0-1, 1-2, 1-3), a triangle, and two parallel edges between 0 and 1. The third reports a cycle because node 0 sees node 1 a second time through the other edge. In a multigraph that’s a real cycle of length two; if the input promises a simple graph, it never arises. For undirected connectivity questions, union-find is often simpler still: an edge whose endpoints are already connected closes a cycle.
When recursion runs out
Recursive DFS uses one stack frame per node on the current path, so a long chain of dependencies means deep recursion. CPython’s default limit is 1,000 frames. A 5,000-node chain is enough to break the recursive version:
RecursionError: maximum recursion depth exceededYou can raise the limit with sys.setrecursionlimit, but that only moves the problem to the next, larger input, and a JavaScript engine has a similar fixed stack budget you can’t change from inside the program. The reliable fix is an explicit stack. The trick that keeps three-state colouring intact is to store each node together with an iterator over its neighbours, so you know when you’ve finished a node and can mark it black:
def has_cycle_iterative(graph):
color = {u: WHITE for u in graph}
for start in graph:
if color[start] != WHITE:
continue
color[start] = GRAY
stack = [(start, iter(graph[start]))]
while stack:
u, neighbours = stack[-1]
v = next(neighbours, None)
if v is None: # all neighbours done: leave u
color[u] = BLACK
stack.pop()
elif color[v] == GRAY:
return True
elif color[v] == WHITE:
color[v] = GRAY
stack.append((v, iter(graph[v])))
return Falseiterative, 100k chain: False
iterative, 100k ring: TrueA 100,000-node chain is fine, and closing it into a ring is detected. A simpler “push all neighbours at once” iterative DFS doesn’t work here, because it has no moment that corresponds to leaving a node, so it can’t tell gray from black.
Either version visits each node once and each edge once: O(V + E) time. Space is O(V) for the colours plus the stack, which in the worst case (a chain) holds every node.
Interview practice: Course Schedule
There are numCourses courses labelled 0 to numCourses - 1. Each pair [a, b] in prerequisites means you must take b before a. Return whether it’s possible to finish every course. Explain the graph you build, which algorithm you run, and why.
Answer
Build a directed graph with an edge b → a for each pair, meaning “b unlocks a”. Every course must appear as a node, including ones with no prerequisites, or isolated courses would be missing from the colour map. You can finish all courses exactly when that graph has no directed cycle: a cycle means each course in it waits on another course in it, so none can be taken first.
def can_finish(num_courses, prerequisites):
graph = {c: [] for c in range(num_courses)}
for course, pre in prerequisites:
graph[pre].append(course) # edge: pre must come before course
return not has_cycle_iterative(graph)
print(can_finish(2, [[1, 0]]), can_finish(2, [[1, 0], [0, 1]]),
can_finish(4, [[1, 0], [2, 1], [3, 2], [1, 3]]), can_finish(3, []))True False False TrueThe third case has a cycle 1 → 2 → 3 → 1 that doesn’t include course 0, which is a good test because it checks that DFS starts from every white node, not just node 0. Time is O(V + E) and space O(V + E) for the adjacency list. The point to say out loud is why a single visited set is wrong here: shared prerequisites (two courses that both need course 0) would be reported as cycles. The equally valid alternative is Kahn’s algorithm, which removes courses with no remaining prerequisites and checks whether every course was removed; the topological sort note works through it.