Cycle Detection: Undirected and Directed
26 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Course prerequisites that depend on each other, tasks that wait for one another, a network with a loop: all are cycles. The test differs for undirected and directed graphs, and mixing them up is a classic mistake.
Cycles in an undirected graph
A cycle is a path of at least one edge that starts and ends at the same node without using the same edge twice. A graph with no cycle is called acyclic.
A cycle is a path that comes back to where it started. In an undirected graph every edge can be walked backwards, so the edge you just used does not count. Remember the parent of each node, and a seen neighbour that is not the parent closes a cycle.
def search(graph, seen, start): stack = [(start, -1)] while stack: node, parent = stack.pop() for nxt in graph[node]: if nxt == parent: continue if nxt in seen: return True seen.add(nxt) stack.append((nxt, node)) return FalseExample 1 · Cycle in an undirected graph
def build(n, edges, directed=False): graph = [[] for _ in range(n)] for a, b in edges: graph[a].append(b) if not directed: graph[b].append(a) return graph
def has_cycle_undirected(n, graph): seen = set() for start in range(n): if start in seen: continue seen.add(start) stack = [(start, -1)] while stack: node, parent = stack.pop() for nxt in graph[node]: if nxt == parent: continue if nxt in seen: return True seen.add(nxt) stack.append((nxt, node)) return False
triangle = build(4, [(0, 1), (1, 2), (2, 0), (2, 3)])line = build(4, [(0, 1), (1, 2), (2, 3)])print(has_cycle_undirected(4, triangle))print(has_cycle_undirected(4, line))True False
What this code does
- In the first graph, nodes 0, 1 and 2 form a loop, so the search meets a seen node that is not the parent.
- The second graph is a plain chain: the only seen neighbour is always the parent, so there is no cycle.
Example 2 · Counting shortcut: edges against nodes
def build(n, edges, directed=False): graph = [[] for _ in range(n)] for a, b in edges: graph[a].append(b) if not directed: graph[b].append(a) return graph
def components(n, graph): seen, count = set(), 0 for start in range(n): if start in seen: continue count += 1 seen.add(start) stack = [start] while stack: for nxt in graph[stack.pop()]: if nxt not in seen: seen.add(nxt) stack.append(nxt) return count
edges = [(0, 1), (1, 2), (3, 4)]n = 5c = components(n, build(n, edges))print(len(edges) > n - c)edges.append((4, 3))print(len(edges) > n - c)False True
What this code does
- A forest with c components has exactly n minus c edges. Any extra edge must close a cycle.
- The repeated edge (4, 3) is a second link between the same two nodes, which is a cycle of length 2.
Run this from every unseen start node, with seen holding the start. The time is O(n + m).
Cycles in a directed graph
A directed cycle is a path that follows edge directions and returns to its starting node. A directed graph with no such cycle is a directed acyclic graph, or DAG.
Here a seen node is not enough: two paths may reach the same node without any cycle. A cycle exists only when an edge leads back to a node on the current path. Give each node a state: new, on the current path, or finished.
def has_cycle_directed(n, graph): state = [0] * n # 0 new, 1 on path, 2 done
def visit(node): state[node] = 1 for nxt in graph[node]: if state[nxt] == 1: return True if state[nxt] == 0 and visit(nxt): return True state[node] = 2 return False
return any(state[v] == 0 and visit(v) for v in range(n))Example 3 · Cycle in a directed graph
def build(n, edges, directed=False): graph = [[] for _ in range(n)] for a, b in edges: graph[a].append(b) if not directed: graph[b].append(a) return graph
def has_cycle_directed(n, graph): state = [0] * n # 0 new, 1 on the current path, 2 finished
def visit(node): state[node] = 1 for nxt in graph[node]: if state[nxt] == 1: return True if state[nxt] == 0 and visit(nxt): return True state[node] = 2 return False
return any(state[v] == 0 and visit(v) for v in range(n))
loop = build(3, [(0, 1), (1, 2), (2, 0)], directed=True)chain = build(3, [(0, 1), (1, 2)], directed=True)print(has_cycle_directed(3, loop))print(has_cycle_directed(3, chain))True False
What this code does
- In the first graph the edge 2 to 0 points back to node 0, which is still on the path.
- The second graph only goes forward, so no node is reached again from itself.
Example 4 · Why one seen set is not enough
def build(n, edges, directed=False): graph = [[] for _ in range(n)] for a, b in edges: graph[a].append(b) if not directed: graph[b].append(a) return graph
def has_cycle_directed(n, graph): state = [0] * n # 0 new, 1 on the current path, 2 finished
def visit(node): state[node] = 1 for nxt in graph[node]: if state[nxt] == 1: return True if state[nxt] == 0 and visit(nxt): return True state[node] = 2 return False
return any(state[v] == 0 and visit(v) for v in range(n))
diamond = build(4, [(0, 1), (0, 2), (1, 3), (2, 3)], directed=True)
def wrong(graph, n): seen = set()
def visit(node): if node in seen: return True seen.add(node) return any(visit(nxt) for nxt in graph[node])
return visit(0)
print(wrong(diamond, 4))print(has_cycle_directed(4, diamond))True False
What this code does
- Node 3 is reached from both 1 and 2. A plain seen set calls that a cycle, which is wrong, since no path returns to its start.
- Three states tell the difference: node 3 is finished (state 2) when the second path arrives.
An edge to a node in state 1 goes back along the current path, so it closes a cycle. A node in state 2 is finished and safe. This version is recursive, so a very long path needs the iterative form.
Another way: remove what has no incoming edge
A topological order lists the nodes of a directed graph so that every edge goes from an earlier node to a later one. It exists exactly when the graph has no directed cycle.
Count the edges that enter each node. A node with none can be taken first. Remove it, lower the counts of its neighbours, and repeat. If every node gets removed there is no cycle; nodes left over are on or behind a cycle.
indeg = [0] * nfor node in range(n): for nxt in graph[node]: indeg[nxt] += 1queue = deque(v for v in range(n) if indeg[v] == 0)order = []while queue: node = queue.popleft() order.append(node) for nxt in graph[node]: indeg[nxt] -= 1 if indeg[nxt] == 0: queue.append(nxt)Example 5 · Topological order and cycle check
def build(n, edges, directed=False): graph = [[] for _ in range(n)] for a, b in edges: graph[a].append(b) if not directed: graph[b].append(a) return graph
from collections import deque
def topo_order(n, graph): indeg = [0] * n for node in range(n): for nxt in graph[node]: indeg[nxt] += 1 queue = deque(v for v in range(n) if indeg[v] == 0) order = [] while queue: node = queue.popleft() order.append(node) for nxt in graph[node]: indeg[nxt] -= 1 if indeg[nxt] == 0: queue.append(nxt) return order
tasks = build(5, [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)], directed=True)print(topo_order(5, tasks))bad = build(3, [(0, 1), (1, 2), (2, 1)], directed=True)print(len(topo_order(3, bad)) == 3)[0, 1, 2, 3, 4] False
What this code does
- The order puts each task after everything it needs.
- The edges 1 to 2 and 2 to 1 keep the counts above zero, so only node 0 is removed and the check prints False.
If len(order) == n, the graph has no cycle. Task schedules with prerequisites use exactly this check. The time is O(n + m).
Next step
Check your understanding
10 quick questions