Detecting Cycles in a Graph

A cycle in a graph is a path that starts and ends at the same vertex without reusing any edge along the way. Detecting whether one exists is a core building block in real systems: it’s how a build tool knows two packages can’t depend on each other circularly, how a course-scheduling system checks that prerequisites are satisfiable, and how deadlock detectors spot processes waiting on each other forever. The technique you use depends entirely on whether the graph’s edges are directed or undirected — mixing them up is one of the most common graph-interview mistakes.

Overview: How Cycle Detection Works

Whether a cycle can exist depends on one property of the graph: are its edges directed (one-way, like “task A must run before task B”) or undirected (two-way, like “city A has a road to city B”)? The two cases need genuinely different algorithms.

Undirected graphs: watch out for the parent

In an undirected graph, every edge is stored twice in an adjacency list — once in each direction — because (u, v) and (v, u) are the same edge. A plain depth-first search (DFS) will always immediately “see” the edge back to the node it just came from, and a naive check would mistake that for a cycle. The fix is to track each node’s parent in the DFS tree and ignore the edge that leads directly back to it. If DFS reaches a node that is already visited and is not the immediate parent, that’s a genuine back edge — a cycle.

Directed graphs: visited isn’t enough

In a directed graph the parent trick doesn’t apply, because reaching an already-visited node isn’t automatically suspicious — two different paths can legitimately converge on the same node without forming a cycle (think of a diamond-shaped dependency graph). What matters isn’t whether a node has been visited before; it’s whether it’s still on the current DFS path, i.e. an ancestor of the node you’re standing on. The standard technique gives every node one of three states: white (unvisited), gray (on the current recursion stack, an ancestor), and black (fully explored, popped off the stack). If DFS follows an edge into a gray node, that edge points back to an ancestor — a cycle. An edge into a black node is safe: a valid convergence, not a cycle.

A third approach, Union-Find (disjoint-set), works only for undirected graphs but is extremely fast for streaming edges one at a time. It starts with every vertex in its own set; for each edge (u, v), if u and v are already in the same set, adding this edge would close a cycle, so you can stop immediately. Otherwise you merge (union) their sets and continue. This is the same building block used in Kruskal’s minimum-spanning-tree algorithm. For directed graphs, a related idea is Kahn’s algorithm: repeatedly remove vertices with no incoming edges; if all V vertices can be removed this way, the graph is a DAG, and any vertices left over must lie on a cycle.

How you store the graph matters too. An adjacency list is the right default for the sparse graphs most real problems produce, using O(V + E) space and letting you iterate a vertex’s neighbors in time proportional to its degree. An adjacency matrix only pays off for dense graphs or when you need O(1) edge-existence lookups, at the cost of O(V^2) space regardless of how many edges actually exist.

Time and Space Complexity

All of these techniques touch every vertex and edge a constant number of times, so their time complexity is linear in the size of the graph. Where they differ is in bookkeeping and how they handle streaming input.

Technique	Time	Space	Works on
DFS with parent tracking	O(V + E)	O(V)	Undirected graphs
DFS with white/gray/black coloring	O(V + E)	O(V)	Directed graphs
Union-Find (disjoint set)	O(E) (path compression + union by rank)	O(V)	Undirected graphs, streaming edges
Kahn’s algorithm (topological sort)	O(V + E)	O(V)	Directed graphs

The DFS approaches use O(V) space for the visited set (or color array) plus the recursion stack, which in the worst case — a graph that’s one long chain — can also grow O(V) deep. That matters in Python specifically: the default recursion limit is around 1000 frames, so a naive recursive DFS on a graph with thousands of vertices chained together can raise a RecursionError; an iterative DFS with an explicit stack avoids the limit entirely. Union-Find’s near-linear time comes from two optimizations: path compression (every node visited during find gets re-pointed straight to the root) and union by rank (the shorter tree is always attached under the taller one). Together they make each operation run in essentially constant amortized time — technically the inverse Ackermann function of V, a function that grows so slowly it’s less than 5 for any input size that could ever exist in practice, so it’s treated as a constant.

Examples

Example 1: Cycle detection in an undirected graph (DFS + parent tracking)

This builds a small graph with a triangle (0-1-2, a cycle) plus a separate, harmless edge (3-4):

from collections import defaultdict


def has_cycle_undirected(graph: dict[int, list[int]], num_vertices: int) -> bool:
    visited: set[int] = set()

    def dfs(node: int, parent: int) -> bool:
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True
        return False

    for vertex in range(num_vertices):
        if vertex not in visited:
            if dfs(vertex, -1):
                return True
    return False


def build_undirected_graph(edges: list[tuple[int, int]]) -> dict[int, list[int]]:
    graph: dict[int, list[int]] = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    return graph


edges = [(0, 1), (1, 2), (2, 0), (3, 4)]
graph = build_undirected_graph(edges)
num_vertices = 5

print("Has cycle:", has_cycle_undirected(graph, num_vertices))

Output:

Has cycle: True

Tracing it by hand: DFS starts at vertex 0 with no parent (-1), moves to 1, then to 2. From 2, neighbor 0 is already in visited — but since 0 is not 2‘s parent (2‘s parent is 1), this is a genuine back edge, and the function returns True up the call stack. Vertices 3 and 4 are never reached because the function short-circuits as soon as a cycle is found.

Example 2: Cycle detection in a directed graph (three-color DFS)

For directed graphs, track each vertex with three states: white (unvisited), gray (on the current call stack), black (finished). This checks two graphs: one with a real directed cycle, and a diamond-shaped DAG where two paths legitimately converge without forming a cycle:

from collections import defaultdict


def has_cycle_directed(graph: dict[int, list[int]], num_vertices: int) -> bool:
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * num_vertices

    def dfs(node: int) -> bool:
        color[node] = GRAY
        for neighbor in graph[node]:
            if color[neighbor] == GRAY:
                return True
            if color[neighbor] == WHITE and dfs(neighbor):
                return True
        color[node] = BLACK
        return False

    for vertex in range(num_vertices):
        if color[vertex] == WHITE:
            if dfs(vertex):
                return True
    return False


def build_directed_graph(edges: list[tuple[int, int]]) -> dict[int, list[int]]:
    graph: dict[int, list[int]] = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
    return graph


cyclic_edges = [(0, 1), (1, 2), (2, 0), (3, 4)]
cyclic_graph = build_directed_graph(cyclic_edges)
print("Cyclic graph has cycle:", has_cycle_directed(cyclic_graph, 5))

acyclic_edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
acyclic_graph = build_directed_graph(acyclic_edges)
print("Diamond DAG has cycle:", has_cycle_directed(acyclic_graph, 4))

Output:

Cyclic graph has cycle: True
Diamond DAG has cycle: False

In the cyclic graph, DFS colors 0, 1, and 2 gray in turn, and from 2 it sees neighbor 0 still gray — still on the stack — so it reports a cycle immediately. In the diamond DAG, DFS colors 0, 1, and 3 gray; 3 has no outgoing edges, so it turns black. Back at 0, the second neighbor 2 is explored: it looks at neighbor 3, which is already black (finished, not on the stack), so it’s recognized as a safe convergence rather than a cycle.

Example 3: Cycle detection in an undirected graph (Union-Find)

Union-Find processes edges one at a time. Each vertex starts as its own tiny set; unioning two vertices already in the same set means the new edge would close a loop:

class UnionFind:
    def __init__(self, size: int) -> None:
        self.parent = list(range(size))
        self.rank = [0] * size

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False
        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_y] = root_x
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1
        return True


def has_cycle_union_find(edges: list[tuple[int, int]], num_vertices: int) -> bool:
    disjoint_set = UnionFind(num_vertices)
    for u, v in edges:
        if not disjoint_set.union(u, v):
            return True
    return False


edges = [(0, 1), (1, 2), (2, 0), (3, 4)]
num_vertices = 5

print("Has cycle:", has_cycle_union_find(edges, num_vertices))

Output:

Has cycle: True

Start with each of the 5 vertices as its own set. union(0, 1) merges them. union(1, 2) finds 1‘s root and merges 2 in too, so {0, 1, 2} are one set. union(2, 0) then finds that both already share a root, returns False without merging — and that False is exactly what signals a cycle, so has_cycle_union_find returns True without even needing to look at the unrelated edge (3, 4).

How It Works, Step by Step

Let’s trace has_cycle_undirected on the graph from Example 1 — vertices 0 through 4, edges (0,1), (1,2), (2,0), (3,4).

1. Start the outer loop at vertex 0. It isn’t visited, so call dfs(0, parent=-1).
2. Inside dfs(0, -1): mark 0 visited. Its neighbors are [1, 2]. Neighbor 1 is unvisited, so recurse: dfs(1, parent=0).
3. Inside dfs(1, 0): mark 1 visited. Its neighbors are [0, 2]. Neighbor 0 is visited but is exactly 1‘s parent, so it’s ignored. Neighbor 2 is unvisited, so recurse: dfs(2, parent=1).
4. Inside dfs(2, 1): mark 2 visited. Its neighbors are [1, 0]. Neighbor 1 is visited and is 2‘s parent, so it’s ignored. Neighbor 0 is visited and is not 2‘s parent — a real back edge, so dfs(2, 1) returns True immediately.
5. That True propagates back up: dfs(1, 0) returns True, then dfs(0, -1) returns True, and the outer function returns True without ever looking at vertices 3 and 4.

If edge (2, 0) hadn’t existed, step 4 would find no unvisited-and-non-parent neighbors, dfs(2, 1) would return False, the search would unwind cleanly, and the outer loop would start a fresh DFS from vertex 3, explore 4, and return False overall.

Common Mistakes

Mistake 1: Forgetting to exclude the parent in an undirected graph

Because every undirected edge is stored in both directions, a DFS that only checks “have I seen this neighbor before?” will always immediately re-discover the node it just came from, wrongly reporting a cycle — even for a single edge, which is just a two-node tree.

from collections import defaultdict


def has_cycle_wrong(graph: dict[int, list[int]], num_vertices: int) -> bool:
    visited = set()

    def dfs(node: int) -> bool:
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            else:
                return True  # BUG: also fires on the edge back to the parent
        return False

    for vertex in range(num_vertices):
        if vertex not in visited:
            if dfs(vertex):
                return True
    return False


def build_undirected_graph(edges: list[tuple[int, int]]) -> dict[int, list[int]]:
    graph: dict[int, list[int]] = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    return graph


edges = [(0, 1)]
graph = build_undirected_graph(edges)

print("Has cycle:", has_cycle_wrong(graph, 2))

Output:

Has cycle: True

A single edge between two vertices can never be a cycle. The bug is the bare else: return True, which fires on the edge leading straight back to the parent, not just on genuine back edges. The fix is to pass the parent down through the recursion and only report a cycle when the revisited neighbor is not the parent — exactly the dfs(node, parent) pattern Example 1 uses above.

Mistake 2: Using a plain visited set for a directed graph

Undirected-style cycle detection (“have I visited this node before?”) gives false positives on directed graphs, because two different paths are allowed to converge on the same node without that being a cycle. The diamond graph 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3 is a valid DAG, but a visited-only check treats the second arrival at 3 as a cycle:

from collections import defaultdict


def has_cycle_wrong(graph: dict[int, list[int]], num_vertices: int) -> bool:
    visited = set()

    def dfs(node: int) -> bool:
        if node in visited:
            return True  # BUG: revisiting a node isn't the same as a cycle
        visited.add(node)
        for neighbor in graph[node]:
            if dfs(neighbor):
                return True
        return False

    for vertex in range(num_vertices):
        if vertex not in visited:
            if dfs(vertex):
                return True
    return False


def build_directed_graph(edges: list[tuple[int, int]]) -> dict[int, list[int]]:
    graph: dict[int, list[int]] = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
    return graph


acyclic_edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
acyclic_graph = build_directed_graph(acyclic_edges)

print("Diamond DAG has cycle:", has_cycle_wrong(acyclic_graph, 4))

Output:

Diamond DAG has cycle: True

That’s wrong — a diamond dependency shape (two modules that both depend on a shared third one) is extremely common and isn’t circular. The problem is that visited only ever grows; it never distinguishes “still being explored” from “fully finished.” The fix is the three-color scheme from Example 2, which only flags an edge into a node that’s still gray, not one that’s already black:

from collections import defaultdict


def has_cycle_correct(graph: dict[int, list[int]], num_vertices: int) -> bool:
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * num_vertices

    def dfs(node: int) -> bool:
        color[node] = GRAY
        for neighbor in graph[node]:
            if color[neighbor] == GRAY:
                return True
            if color[neighbor] == WHITE and dfs(neighbor):
                return True
        color[node] = BLACK
        return False

    for vertex in range(num_vertices):
        if color[vertex] == WHITE:
            if dfs(vertex):
                return True
    return False


def build_directed_graph(edges: list[tuple[int, int]]) -> dict[int, list[int]]:
    graph: dict[int, list[int]] = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
    return graph


acyclic_edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
acyclic_graph = build_directed_graph(acyclic_edges)

print("Diamond DAG has cycle:", has_cycle_correct(acyclic_graph, 4))

Output:

Diamond DAG has cycle: False

Mistake 3: A mutable default argument leaking state between calls

It’s tempting to make visited a default parameter instead of a local variable. In Python, default argument values are created exactly once, when the function is defined, not once per call — so a mutable default like set() is silently shared and accumulates across every call:

from collections import defaultdict


def has_cycle_undirected(graph: dict[int, list[int]], num_vertices: int, visited: set[int] = set()) -> bool:
    # BUG: the default set() is created once, when the function is defined,
    # and then reused (and mutated) by every call that doesn't pass visited explicitly.
    def dfs(node: int, parent: int) -> bool:
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True
        return False

    for vertex in range(num_vertices):
        if vertex not in visited:
            if dfs(vertex, -1):
                return True
    return False


def build_undirected_graph(edges: list[tuple[int, int]]) -> dict[int, list[int]]:
    graph: dict[int, list[int]] = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    return graph


tree_edges = [(0, 1), (1, 2)]
tree_graph = build_undirected_graph(tree_edges)
print("First call (tree, no cycle):", has_cycle_undirected(tree_graph, 3))

cyclic_edges = [(0, 1), (1, 2), (2, 0)]
cyclic_graph = build_undirected_graph(cyclic_edges)
print("Second call (triangle, should be a cycle):", has_cycle_undirected(cyclic_graph, 3))

Output:

First call (tree, no cycle): False
Second call (triangle, should be a cycle): False

The second graph is a triangle on vertices 0, 1, 2 — a textbook cycle — but the function reports False. Because the same visited set object survived from the first call, vertices 0, 1, and 2 already look “visited” before the second call’s loop even starts, so dfs is never invoked at all. The fix is to build visited fresh inside the function body on every call instead of handing it in as a default parameter — exactly what Example 1’s has_cycle_undirected does above, where visited: set[int] = set() is the first line inside the function, not part of the signature.

Best Practices

• Match the algorithm to the edge type: parent-tracking DFS or Union-Find for undirected graphs, colored DFS or Kahn’s algorithm for directed graphs. Applying the undirected trick to a directed graph (or vice versa) silently produces wrong answers, not an error.
• Reach for Union-Find when edges arrive incrementally (building a minimum spanning tree with Kruskal’s algorithm, or answering many “are these connected?” queries), since it checks each new edge in near-constant amortized time without a full traversal.
• Reach for Kahn’s algorithm when you need more than a yes/no answer — it produces a valid topological order for a DAG, and the vertices left over when it stalls are exactly the ones on a cycle.
• Always loop over every vertex as a potential DFS root, not just vertex 0, so disconnected components are handled correctly — a graph can be cycle-free in one component and cyclic in another.
• For very large or deep graphs, prefer an iterative DFS with an explicit stack over recursive DFS to avoid hitting Python’s recursion limit.
• Never use a mutable object (list, set, dict) as a default argument value; initialize it fresh inside the function body so state can’t leak between calls.

Practice Exercises

1. Extend has_cycle_directed so it returns the actual list of vertices forming one cycle (or an empty list if none exists), instead of just True/False. Hint: keep a list representing the current DFS path, and when you hit a gray node, slice the path from that node onward.
2. Given n nodes labeled 0 to n - 1 and a list of undirected edges, write is_valid_tree(n, edges) that returns True only if the edges form a single connected tree with no cycles. Hint: a graph with n nodes is a tree only if it has exactly n – 1 edges AND is fully connected with no cycle — edge count alone isn’t enough.
3. Given a list of (course, prerequisite) pairs, write can_finish(num_courses, prerequisites) that returns True if every course can be taken given the prerequisites, and False if they contain a cycle. Expected output: can_finish(2, [(1, 0)]) is True; can_finish(2, [(1, 0), (0, 1)]) is False.

Summary

• A cycle lets you leave a vertex and return to it by following edges without reusing one; whether it exists depends critically on whether the graph is directed or undirected.
• Undirected graphs: use DFS with parent tracking, or Union-Find. A revisited neighbor is only a cycle if it isn’t the immediate parent.
• Directed graphs: use DFS with white/gray/black coloring, or Kahn’s algorithm. A revisited neighbor is only a cycle if it’s still on the current call stack (gray), not merely visited before (black).
• DFS-based detection runs in O(V + E) time and O(V) space; Union-Find processes each edge in near-constant amortized time (O(E) total with path compression and union by rank); Kahn’s algorithm runs in O(V + E) time.
• Common bugs: forgetting the parent check on undirected graphs, using a single visited set on directed graphs, and using a mutable default argument that silently shares state across calls.