Introduction

A directed graph is acyclic when no path follows edge directions and comes back to its starting vertex. That check matters in build systems, dependency resolution, task scheduling, and database migrations, because a cycle means at least one dependency can never be satisfied first.

Detecting Cycles with Depth-First Search

The most direct approach is depth-first search with three states for each node: unvisited, visiting, and visited. A node becomes visiting when recursion enters it and becomes visited after all outgoing edges have been processed. If the traversal reaches another visiting node, the graph has a back edge and therefore a cycle.

This method works well when the graph is stored as an adjacency list and you want an answer in linear time. Its cost is O(V + E), where V is the number of vertices and E is the number of edges.

1from collections import defaultdict
2
3
4def is_acyclic(graph: dict[str, list[str]]) -> bool:
5    state = {node: 0 for node in graph}  # 0 = unvisited, 1 = visiting, 2 = visited
6
7    def dfs(node: str) -> bool:
8        if state[node] == 1:
9            return False
10        if state[node] == 2:
11            return True
12
13        state[node] = 1
14        for neighbor in graph[node]:
15            if neighbor not in state:
16                state[neighbor] = 0
17                graph.setdefault(neighbor, [])
18            if not dfs(neighbor):
19                return False
20        state[node] = 2
21        return True
22
23    for node in list(graph):
24        if state[node] == 0 and not dfs(node):
25            return False
26    return True
27
28
29acyclic_graph = {
30    "build": ["test", "lint"],
31    "test": ["package"],
32    "lint": [],
33    "package": []
34}
35
36cyclic_graph = {
37    "A": ["B"],
38    "B": ["C"],
39    "C": ["A"]
40}
41
42print(is_acyclic(acyclic_graph))
43print(is_acyclic(cyclic_graph))

The output is True for the first graph and False for the second one. The important detail is the distinction between a node already finished and a node currently on the recursion path.

Using Kahn's Algorithm

Kahn's algorithm checks acyclicity through topological sorting. It counts incoming edges for every vertex, repeatedly removes nodes whose indegree is zero, and tracks how many nodes were processed. If every node is removed, the graph is acyclic. If some nodes remain, those leftover nodes are part of a cycle or depend on one.

This approach is also O(V + E) and is often easier to reason about when you already need a topological order.

1from collections import deque
2
3
4def is_acyclic_kahn(graph: dict[str, list[str]]) -> bool:
5    indegree = {node: 0 for node in graph}
6
7    for node, neighbors in graph.items():
8        for neighbor in neighbors:
9            indegree.setdefault(neighbor, 0)
10            indegree[neighbor] += 1
11
12    queue = deque([node for node, degree in indegree.items() if degree == 0])
13    processed = 0
14
15    while queue:
16        node = queue.popleft()
17        processed += 1
18        for neighbor in graph.get(node, []):
19            indegree[neighbor] -= 1
20            if indegree[neighbor] == 0:
21                queue.append(neighbor)
22
23    return processed == len(indegree)

Kahn's algorithm is iterative, so it avoids recursion depth issues on very deep graphs. It also naturally exposes which nodes can be executed first in a scheduling problem.

Which Method Should You Use?

Use DFS when you only need a yes or no answer and already have a recursive graph traversal in place. Use Kahn's algorithm when you also want a topological ordering or want to stay away from recursion limits.

In practice, both methods are standard and correct. The real decision is about the rest of the code around them. For example, a compiler pipeline might prefer Kahn's algorithm because the sorted result is useful, while a graph validation utility might prefer the more compact DFS solution.

Common Pitfalls

A common bug is using a single visited set and treating any repeated node as a cycle. That is incorrect in directed graphs because revisiting a fully processed node is safe. You need a separate notion of the current recursion path, such as the visiting state.

Another mistake is forgetting nodes that appear only as neighbors. If your graph builder creates keys only for source vertices, indegree counting and traversal can miss sink nodes. Make sure every referenced vertex exists in the internal representation.

With DFS, very deep graphs can hit recursion limits in Python. If that is a concern, either raise the recursion limit carefully or use Kahn's algorithm instead.

Summary

• A directed graph is acyclic when no directed path returns to its starting node.
• DFS detects cycles by finding a back edge to a node currently marked visiting.
• Kahn's algorithm detects cycles when a full topological ordering cannot be produced.
• Both approaches run in linear time relative to vertices and edges.
• Correct graph initialization matters as much as the algorithm itself.