DSA Graphs

Cycle Detection

Four transactions wait on each other at a lock table. Nothing progresses. You need a directed cycle certificate, not a vague “this graph looks loopy.”

Pick the detector from the graph contract: undirected parent DFS/BFS, directed , Kahn leftover, or undirected on an edge stream.

Algorithm journey

Directed or undirected?

The cycle certificate changes.

Parent exemption vs gray ancestor.

Scan every component

One start misses other cyclic parts.

Return a witness

Parents / Kahn remainder for debugging.

What actually happens

Naive idea: “If I ever see a visited vertex, there is a cycle.” Breaks on directed graphs: an edge to a finished (black) vertex is not a cycle. Also breaks undirected if you forget to exempt the parent edge.

Better idea: state the certificate. Undirected non-parent visit, or directed edge to a . Kahn proves a cycle when fewer than V nodes leave the zero-indegree queue.

The improved design still fails on parallel undirected edges if you only store a parent vertex (not an edge id), or if you start from one vertex in a disconnected graph.

Invariant

During directed DFS, gray vertices are exactly the active path. A gray back edge proves a directed cycle. During undirected traversal, every visited non-parent neighbor proves an undirected cycle.

How to choose a cycle detector

1. Undirected adjacency? DFS/BFS + parent, or DSU on an edge list.

2. Directed? Three-color DFS, or Kahn if you also want a topo order.

3. Need the actual cycle? Keep parents; walk from the back-edge endpoints.

Quantitative check

All standard detectors are O(V+E) (DSU nearly O(E α(V))). At V=10⁵, E=5·10⁵, one linear scan is fine; the bug is almost always the wrong certificate, not the asymptotics.

Try it yourself

Use the graph builder below. Try to connect 3 or 4 nodes in a circle (e.g., A→B→C→A). That's a cycle!

ℹ️ Ready to build a Graph!

Cycle certificate lab

Step until the highlighted edge supplies a proof. Toggle orientation to see why a directed back edge needs the gray recursion path, while an undirected traversal must exempt the parent edge.

Interactive invariant lab

Graph state, not just graph shape

Switch semantics and algorithms, then step through the frontier, discovery state, and edge-level proof obligation.

Step 1 of 11

Enter A; color it gray

A is now on the active recursion path.

Frontier / path: A
Processed: ∅

Invariant

Gray vertices are exactly the current DFS path. An edge to gray is a back edge and therefore proves a directed cycle.

Trace position: 1 / 11

ActiveFrontierProcessedOn recursion path (gray)

Pick the detector from the graph contract

Graph / input	Technique	Cycle certificate	Cost
Undirected adjacency list	DFS/BFS + parent	Visited neighbor through a non-parent edge	O(V + E)
Directed adjacency list	Three-color DFS	Edge to a gray (active) ancestor	O(V + E)
Directed scheduling graph	Kahn's algorithm	Processed count < V	O(V + E)
Stream of undirected edges	Disjoint Set Union	Endpoints already share a representative	O(E α(V))

Do not reuse the rule across orientations: a directed edge to any visited vertex is not necessarily a cycle; it is a cycle only when that vertex is still active (gray).

1. Undirected Graph (DFS)

Logic: If we see a visited neighbor that is NOT our direct parent, it means we found a "back door" to a node we've already seen. That's a cycle.

Python

python

def has_cycle_undirected(adj):
    visited = [False] * len(adj)

    def dfs(u, parent):
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                if dfs(v, u):
                    return True
            elif v != parent:
                return True
        return False

    # Required for disconnected graphs and isolated vertices.
    return any(
        not visited[start] and dfs(start, -1)
        for start in range(len(adj))
    )

Java

java

import java.util.*;

final class UndirectedCycleDetector {
    static boolean hasCycle(List<List<Integer>> adj) {
        boolean[] visited = new boolean[adj.size()];
        for (int start = 0; start < adj.size(); start++) {
            if (!visited[start] && dfs(start, -1, adj, visited)) {
                return true;
            }
        }
        return false;
    }

    private static boolean dfs(
            int u, int parent,
            List<List<Integer>> adj, boolean[] visited) {
        visited[u] = true;
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                if (dfs(v, u, adj, visited)) return true;
            } else if (v != parent) {
                return true;
            }
        }
        return false;
    }
}

2. Directed Graph (Three Colors)

Logic: We need to track nodes currently in the current recursion path. If we hit a node that is already in the current path, we found a cycle.

Python

python

def has_cycle_directed(adj):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * len(adj)

    def dfs(u):
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY:   # edge to active ancestor
                return True
            if color[v] == WHITE and dfs(v):
                return True
        color[u] = BLACK
        return False

    return any(
        color[start] == WHITE and dfs(start)
        for start in range(len(adj))
    )

Java

java

import java.util.*;

final class DirectedCycleDetector {
    private static final int WHITE = 0;
    private static final int GRAY = 1;
    private static final int BLACK = 2;

    static boolean hasCycle(List<List<Integer>> adj) {
        int[] color = new int[adj.size()];
        for (int start = 0; start < adj.size(); start++) {
            if (color[start] == WHITE && dfs(start, adj, color)) {
                return true;
            }
        }
        return false;
    }

    private static boolean dfs(
            int u, List<List<Integer>> adj, int[] color) {
        color[u] = GRAY;
        for (int v : adj.get(u)) {
            if (color[v] == GRAY) return true;
            if (color[v] == WHITE && dfs(v, adj, color)) return true;
        }
        color[u] = BLACK;
        return false;
    }
}

3. Directed Graph (Kahn's Algorithm)

Every DAG has a zero-indegree vertex. Repeatedly remove all such vertices and decrement outgoing neighbors. If the queue empties before all vertices are processed, each remaining vertex is trapped behind at least one incoming edge: a cycle exists.

Python

python

from collections import deque

def has_cycle_kahn(adj):
    indegree = [0] * len(adj)
    for neighbors in adj:
        for v in neighbors:
            indegree[v] += 1

    queue = deque(v for v, d in enumerate(indegree) if d == 0)
    processed = 0
    while queue:
        u = queue.popleft()
        processed += 1
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    return processed != len(adj)

Java

java

import java.util.*;

final class KahnCycleDetector {
    static boolean hasCycle(List<List<Integer>> adj) {
        int[] indegree = new int[adj.size()];
        for (List<Integer> neighbors : adj) {
            for (int v : neighbors) indegree[v]++;
        }

        Deque<Integer> queue = new ArrayDeque<>();
        for (int v = 0; v < adj.size(); v++) {
            if (indegree[v] == 0) queue.addLast(v);
        }

        int processed = 0;
        while (!queue.isEmpty()) {
            int u = queue.removeFirst();
            processed++;
            for (int v : adj.get(u)) {
                if (--indegree[v] == 0) queue.addLast(v);
            }
        }
        return processed != adj.size();
    }
}

Correctness: what exactly proves a cycle?

Undirected parent proof

DFS tree edges connect a vertex to its parent. If u sees an already visited v through another edge, the unique tree path v ⇝ u plus edge u: v is a closed walk containing a cycle.

Directed gray-edge proof

Gray means “on the current DFS path.” For an edge u → v with v gray, the tree path v ⇝ u followed by u → v is a directed cycle. An edge to black has no such guarantee.

The outer loop is part of the proof: without starting DFS from every still-white vertex, a cycle in a disconnected component can remain invisible. Isolated vertices are processed and immediately finished.

Worked traces

Directed: A → B → D → E → C

Each entered vertex becomes gray.
C explores C → D while D is still gray.
The back edge C → D proves cycle D → E → C → D.
No finishing/black transition is needed after a certificate is found.

Undirected: A: B: D: C: A

A's edge seen from B is ignored because A is B's parent.
DFS reaches C through D.
C sees visited A, which is not C's parent D.
The DFS tree path A: B: D: C plus C: A closes the cycle.

Edge cases & alternatives

Self-loops & parallel edges

A self-loop (u,u) is an immediate cycle in an undirected graph. Multiple edges between the same pair can confuse naive parent checks, normalize or tag edges when building the adjacency structure.

Union–Find for undirected static graphs

Insert all edges into a DSU: if union(u,v) tries to merge two vertices already in the same set, you have a cycle. Runs in nearly O(E α(V)) after sorting (Kruskal-style) or online while streaming edges.

Directed graphs: the recursion-stack (white/gray/black) coloring is equivalent to finding a back edge to a vertex still being processed, different from the undirected “neighbor ≠ parent” rule.

Edge cases that change the implementation

Self-loop

u → u or u: u is an immediate cycle. All three detectors naturally report it when the edge is preserved.

Parallel undirected edges

Two edges between u and v form a length-2 multigraph cycle. A parent-vertex check misses it; store an edge ID and ignore only the exact incoming edge.

Disconnected graph

Run the detector from every unvisited/white vertex. One start covers only one component.

Isolated vertex

It forms an acyclic singleton component and must still have an adjacency bucket.

Recursive depth

A long path creates O(V) call depth; use an explicit stack or Kahn when stack overflow is possible.

Need the actual cycle

Store parents. On a gray back edge u→v, walk parents from u back to v; Kahn alone identifies a cyclic remainder but not a simple cycle.

Where cycles show up

Recognition clues

Course prerequisites / build ordering → directed cycle.
Redundant undirected connection → DSU or parent DFS.
Safe eventual states → reverse reasoning from directed cycles.
Alien dictionary → validate order edges, then reject cycles.

Production semantics

Wait-for graphs use directed cycles as deadlock candidates.
Dependency services need snapshot consistency during detection.
Return a cycle witness for diagnostics, not only a boolean.
Incremental graphs may need online algorithms rather than full rescans.

Short takeaway

Cycle detection is a certificate problem. Match the rule to orientation, scan every component, and return a witness when operators must debug the loop.

Exercises

Give a tiny digraph where an edge to a black vertex exists but no directed cycle does. Which wrong rule would falsely report a cycle?
Two undirected edges between the same pair. Why must the parent check track an edge id, not only a parent vertex?
Run Kahn on a digraph with a 3-cycle plus two independent nodes. What is processed count vs V, and what remains?

Primary sources

Cormen et al., CLRS: DFS classification of edges; topological sort / cycle detection.
Kahn, A. B. (1962): Topological sorting of large networks.
Tarjan / standard Union-Find notes for undirected connectivity and cycle tests.