What Is a Graph Cycle? Detection Methods Every Interview Tests

You want to run topological sort on a dependency graph. It produces a wrong result. No error, no stack trace, just quietly incorrect output shipped to prod. Or you call Bellman-Ford and it tells you no shortest path exists when you know for a fact there is one. Or your course-scheduling algorithm loops forever and your laptop fan starts making that noise.

All three failures trace back to the same root cause: a cycle. And if you're interviewing at a company that actually tests graph problems (which is... most of them), you need to be able to detect one on the spot.

Whether a graph contains a cycle determines which algorithms are valid to run on it. This isn't a minor detail. Topological sort is undefined on graphs with cycles. Dijkstra becomes unreliable when negative-weight cycles exist. Half the graph problems on LeetCode are cycle detection in disguise. The other half are also cycle detection, just better disguised.

A Cycle Is a Path That Loops Back

A graph cycle is a sequence of vertices where you start at some vertex, follow edges, and return to that same vertex without reusing any edge. The key word is "return." The path closes on itself.

The simplest cycle: three vertices A, B, and C where A connects to B, B connects to C, and C connects back to A.

A -- B
|    |
+----C

More concrete: course prerequisites. Course A requires B, B requires C, C requires A. No student can ever enroll in course A. There is no valid starting point. That's a cycle, and it makes the system unsolvable. Your university registrar has probably shipped this bug at least once.

A self-loop (a vertex with an edge to itself) also counts as a cycle in most graph problems. Worth checking the problem constraints before assuming otherwise, because it will be in the test cases.

Direction Changes Everything

This is the distinction that causes the most bugs. The two types require entirely different detection logic, and confusing them will fail you silently.

In an undirected graph, every edge is bidirectional. Walking from A to B and back to A via the same edge is not a cycle. That's just an edge. For an actual cycle you need at least three distinct vertices with a path that returns to the start through a different route.

In a directed graph, edges point one way. A cycle means there is a directed path from vertex V that eventually leads back to V. Two paths that both happen to converge on the same vertex is not a cycle. Direction matters.

Undirected cycle:        Directed cycle:
A -- B -- C              A -> B -> C
|_________|              ^         |
(requires 3+ nodes)      |_________|

Two nodes pointing at each other is a directed cycle. In an undirected graph, that's just one edge. Confusing these two types is the most common graph cycle bug, and it produces false positives that are genuinely hard to debug.

Detecting Cycles in an Undirected Graph

Run DFS and track which vertex you came from (the parent). If you reach a vertex that is already visited and it is not your immediate parent, you found a back edge, which means a cycle exists.

def has_cycle_undirected(n: int, edges: list[list[int]]) -> bool:
    graph: list[list[int]] = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = [False] * n

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

    for i in range(n):
        if not visited[i] and dfs(i, -1):
            return True
    return False

The elif neighbor != parent check is the critical line. Without it, every edge looks like a back edge because DFS immediately sees the vertex it just came from as "visited." Your cycle detector detects every graph as cyclic. Fun.

Union-Find is often cleaner for undirected cycle detection. Process each edge and try to union the two endpoints. If they are already in the same connected component, adding this edge creates a cycle.

def has_cycle_uf(n: int, edges: list[list[int]]) -> bool:
    parent = list(range(n))

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for u, v in edges:
        pu, pv = find(u), find(v)
        if pu == pv:
            return True
        parent[pu] = pv
    return False

Union-Find is particularly clean when you receive edges one at a time and need to detect the moment a cycle forms. It also tends to impress interviewers more than DFS, which helps.

Detecting Cycles in a Directed Graph

The parent-tracking trick from undirected graphs fails here. In a directed graph, two separate DFS paths can both pass through the same vertex without forming a cycle. The signal you need is not "visited before" but "currently in the active DFS path." This is where most candidates go wrong.

The standard approach is three-color marking: white (never visited), gray (currently in the DFS stack), black (fully processed). A back edge is an edge to a gray vertex. That means you have a cycle.

def has_cycle_directed(n: int, edges: list[list[int]]) -> bool:
    graph: list[list[int]] = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)

    # 0 = white, 1 = gray, 2 = black
    color = [0] * n

    def dfs(node: int) -> bool:
        color[node] = 1
        for neighbor in graph[node]:
            if color[neighbor] == 1:
                return True
            if color[neighbor] == 0 and dfs(neighbor):
                return True
        color[node] = 2
        return False

    return any(color[i] == 0 and dfs(i) for i in range(n))

Same logic in TypeScript, since this pattern shows up in frontend interview problems too:

function hasCycleDirected(n: number, edges: number[][]): boolean {
    const graph: number[][] = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
    }

    const color = new Array(n).fill(0); // 0=white, 1=gray, 2=black

    function dfs(node: number): boolean {
        color[node] = 1;
        for (const neighbor of graph[node]) {
            if (color[neighbor] === 1) return true;
            if (color[neighbor] === 0 && dfs(neighbor)) return true;
        }
        color[node] = 2;
        return false;
    }

    return color.some((c, i) => c === 0 && dfs(i));
}

An alternative is Kahn's algorithm (BFS-based topological sort). If after processing all zero-in-degree nodes you haven't processed every vertex, the unprocessed ones form cycles.

from collections import deque

def has_cycle_kahn(n: int, edges: list[list[int]]) -> bool:
    graph: list[list[int]] = [[] for _ in range(n)]
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1

    queue = deque(i for i in range(n) if in_degree[i] == 0)
    processed = 0

    while queue:
        node = queue.popleft()
        processed += 1
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return processed != n

Kahn's avoids deep recursion and is easier to reason about for large graphs. It's also what you reach for when you want to actually produce the topological ordering at the same time, not just detect whether one exists.

O(V + E). That's It.

All DFS-based approaches run in O(V + E) time. Each vertex is visited once and each edge is examined once. Nothing clever going on.

Space is O(V) for the recursion stack plus O(V + E) for the adjacency list. On graphs with deep DFS paths, stack overflow is a real concern in Python (default recursion limit is 1,000, which is not a lot when your graph has 10,000 nodes). Switch to iterative DFS or Kahn's in those cases.

Union-Find runs in O(E * α(V)) time, where α is the inverse Ackermann function. Effectively O(E) in practice. Space is O(V) for the parent array.

For large graphs, Kahn's iterative BFS is usually the safer choice in an interview. "I'm using Kahn's to avoid potential recursion depth issues" is the kind of thing that gets written down in your feedback.

Graph Cycle Detection in Coding Interviews

Topological sort fails on cyclic graphs. Any problem involving task dependencies, build orders, course prerequisites, or event sequencing implicitly requires a DAG. The question "does a valid ordering exist?" is cycle detection. LeetCode 207 (Course Schedule) is the canonical version. LeetCode 210 (Course Schedule II) asks you to also produce the ordering. Both reduce to: detect a cycle, then run topological sort if none found. For a full treatment of topological sort, see the topological sort interview guide. For the definition of a DAG, see what is a directed acyclic graph.

Negative-weight cycles break shortest path algorithms. A negative-weight cycle lets you loop forever and keep decreasing your total path cost. Bellman-Ford can detect these: if you can still relax an edge after V-1 iterations, a negative-weight cycle exists. See negative weight cycles for the full breakdown.

Linked list cycle detection is the same problem. A linked list is a directed graph where each node has exactly one outgoing edge. Floyd's fast-and-slow pointer algorithm is cycle detection on this restricted graph. The proof of correctness relies on the same mathematical properties as DFS back-edge detection, just with O(1) space instead of O(n). See Floyd's cycle detection algorithm.

Redundant Connection (LeetCode 684). Given edges that form a tree plus one extra, find the redundant edge. Solution: Union-Find, find the first edge that connects two already-connected vertices.

Graph Valid Tree (LeetCode 261). A connected graph with n nodes and exactly n-1 edges that contains no cycle is a tree. Both conditions are checkable with the techniques above.

A large category of interview problems reduces to "is this graph a DAG or not." Recognizing the mapping saves you from building a more complex solution than the problem needs. It also saves you from spending the first 10 minutes building a union-find when the problem secretly wanted DFS.

Two Bugs That Cost People Offers

Bug 1: Using visited instead of in_stack for directed graphs. In a directed graph, seeing an already-visited node during DFS does not mean you found a cycle. Two separate paths can both reach the same node. A cycle requires that node to be currently in your active path. Using a simple boolean visited fires false positives on cross edges and forward edges.

# Wrong for directed graphs
if visited[neighbor]:
    return True  # fires on cross edges too

# Correct
if color[neighbor] == 1:  # gray = currently in stack
    return True

Bug 2: Forgetting the parent check for undirected graphs. Skip neighbor != parent and the edge you just traversed immediately looks like a back edge. Every single edge triggers a false positive. Your function returns True on a graph with two nodes and one edge. Your interviewer writes something down.

Both bugs produce code that compiles, runs, and returns wrong answers. Consistently. The worst kind of wrong. If your cycle detection returns True on a graph you know is acyclic, check these two before you start doubting the laws of graph theory.

If you want to practice explaining this under time pressure while an interviewer stares at you, SpaceComplexity runs voice-based mock DSA interviews with rubric-based feedback on exactly this kind of problem.

What to Remember

A cycle is a path that starts and ends at the same vertex without reusing edges
Undirected cycles require 3+ distinct vertices; directed cycles can be two nodes pointing at each other
Undirected detection: DFS with parent tracking, or Union-Find
Directed detection: DFS with three-color marking (white/gray/black), or Kahn's BFS
Both DFS approaches run in O(V+E) time, O(V) space
Cycles invalidate topological sort, break shortest paths with negative-weight cycles, and appear in linked list and connectivity problems
The bug: wrong algorithm for the graph type