Cycle detection

Overview

A cycle is a path that comes back to where it started. Detecting one depends on whether the graph is directed. Directed graphs use a three-colour DFS (unseen / on-stack / finished) and look for a 'back edge' to a vertex still on the recursion stack. Undirected graphs carry the parent vertex and flag any edge to an already-visited vertex that is not the parent.

Why it matters

Cycle detection decides whether a set of tasks can be scheduled (a dependency cycle makes it impossible), whether a build graph is valid, whether a deadlock exists among lock waiters, and whether a graph is a tree or forest.

Core concepts

Directed — three colours. White = unvisited, gray = in the current DFS stack, black = fully explored. An edge to a gray vertex is a back edge → cycle.

Undirected — parent tracking. DFS remembers who it came from; a visited neighbour other than that parent means a cycle.

Why the distinction. In an undirected graph every edge looks like an immediate 2-cycle; excluding the parent removes that false positive.

Syntax notes

/* DIRECTED: three-colour DFS. 0 = white (unseen), 1 = gray (on stack), 2 = black (done) */
static int dfs_dir(const int *adj, int n, int v, int *col) {
    col[v] = 1;                                   /* gray: currently on the recursion stack */
    for (int u = 0; u < n; u++)
        if (adj[v*n + u]) {
            if (col[u] == 1) return 1;            /* back edge to a GRAY vertex = cycle */
            if (col[u] == 0 && dfs_dir(adj, n, u, col)) return 1;
        }
    col[v] = 2;                                   /* black: fully explored, no longer on stack */
    return 0;
}

/* UNDIRECTED: carry the parent; any other visited neighbour closes a cycle */
static int dfs_undir(const int *adj, int n, int v, int parent, int *vis) {
    vis[v] = 1;
    for (int u = 0; u < n; u++)
        if (adj[v*n + u]) {
            if (!vis[u]) { if (dfs_undir(adj, n, u, v, vis)) return 1; }
            else if (u != parent) return 1;       /* visited, not our parent -> cycle */
        }
    return 0;
}

Key points:

• An edge to a black vertex is a cross/forward edge, not a cycle — only gray counts.
• The undirected version must exclude the parent, or every single edge looks like a 2-cycle.
• Both need an outer sweep over all vertices to cover disconnected graphs.

Lesson

A cycle is a path that returns to its start. Detecting one differs by graph type. In a directed graph, a three-colour DFS (white/gray/black) spots a back edge to a vertex still on the recursion stack (gray). In an undirected graph, DFS carries the parent and any edge to an already-visited non-parent vertex closes a cycle.

Code examples

#include <stdio.h> static int n=3; static int col[3]; static int dfs(const inta,int v){ col[v]=1; for(int u=0;u<n;u++) if(a[vn+u]){ if(col[u]==1) return 1; if(col[u]==0&&dfs(a,u)) return 1; } col[v]=2; return 0; } static int cyclic(const int*a){ for(int i=0;i<n;i++)col[i]=0; for(int i=0;i<n;i++) if(col[i]==0&&dfs(a,i)) return 1; return 0; } int main(void){ int dag[9] ={ 0,1,1, 0,0,1, 0,0,0 }; /* 0->1,0->2,1->2 : acyclic / int loop[9] ={ 0,1,0, 0,0,1, 1,0,0 }; / 0->1->2->0 : cycle */ printf("DAG has cycle? %s\n", cyclic(dag)?"yes":"no"); printf("loop has cycle? %s\n", cyclic(loop)?"yes":"no"); return 0; }

Line by line

Common mistakes

Using undirected (parent) logic on a directed graph, or vice-versa. In the directed case, flagging an edge to a black (finished) vertex — that is a cross/forward edge, not a cycle. Forgetting to reset colours between DFS roots.

Debugging tips

Compiler errors and warnings:

• -Wunused-variable if you keep a colour array but test a plain boolean instead.
• No warning distinguishes gray from black misuse.

Runtime symptoms:

• Every non-trivial directed graph reports a cycle. You treated black as a cycle indicator. Only gray (on the current stack) counts.
• A real directed cycle is missed. You set col[v] = 2 before the neighbour loop finishes, so the ancestor no longer looks gray.
• Every undirected edge reports a cycle. The parent exclusion is missing.
• A genuine undirected cycle is missed with parallel edges. Excluding by parent vertex also excludes a second distinct edge to the same parent; if multi-edges are possible, exclude by edge instead.
• Cycles in a disconnected part are missed. You started DFS only from vertex 0 — sweep every unvisited vertex.

Technique: test four graphs: a DAG, a directed 3-cycle, an undirected tree, and an undirected triangle. Those four pin down both algorithms and both classic mistakes.

Memory safety

• Colour array sizing and initialisation. n entries, calloc-zeroed so every vertex starts white; garbage values read as gray or black and produce arbitrary answers.
• Depth equals the longest path. Deep or large graphs can exhaust the stack — an iterative DFS with an explicit stack (and explicit colour transitions) removes that risk.
• The gray marking is a correctness and termination property. Marking on entry is what stops the recursion revisiting a vertex already on the stack; without it a cycle recurses forever.
• Sweep bounds. The outer loop must cover 0..n-1; skipping it leaves cycles in disconnected components undetected.
• Directed vs undirected preconditions are unchecked. Running the undirected algorithm on a directed matrix (or vice versa) silently produces wrong results — document which one a function expects.
• Free the colour/visited array on every path.

Real-world uses

Concrete uses: Build systems and package managers reject dependency cycles; spreadsheet engines detect circular references; deadlock detection looks for cycles in a wait-for graph; a directed acyclic check is the precondition for topological sorting and for DAG-based DP. The undirected version tests whether a graph is a tree or forest — used in validating spanning structures and in Kruskal's MST, where adding an edge that would close a cycle is exactly what union-find prevents.

Professional best practices:

Beginner:

• Keep the three colours explicit rather than collapsing them into a boolean.
• Test a DAG and a cyclic graph side by side.

Intermediate:

• Report where the cycle is, not just that one exists — a dependency error naming the offending chain is far more useful than a bare "cycle detected".
• For undirected graphs with possible parallel edges, exclude the traversed edge rather than the parent vertex.
• Consider union-find for undirected cycle detection when edges arrive incrementally.

Practice tasks

1. (Beginner) Directed cycle detection. Implement the three-colour DFS with an outer sweep. Example: a DAG -> 0; 0->1->2->0 -> 1. Concepts: gray vs black.

2. (Beginner) Undirected cycle detection. Implement the parent-carrying DFS. Example: a tree -> 0; a triangle -> 1. Concepts: parent exclusion.

3. (Intermediate) Report the cycle. Extend the directed version to print the vertices forming the cycle. Hint: keep a parent array and walk back from the gray vertex you hit. Concepts: diagnostics, not just detection.

4. (Intermediate) Tree check. Use the undirected detector plus a connectivity check to decide whether a graph is a tree (connected and acyclic with exactly n-1 edges). Concepts: combining properties.

Summary

A cycle is a back edge, but what counts as one differs by graph type. In a directed graph, three-colour DFS distinguishes vertices on the current recursion stack (gray) from fully explored ones (black) — only an edge into a gray vertex is a cycle, and marking a vertex black before its neighbour loop finishes hides real cycles. In an undirected graph, every edge would look like a 2-cycle, so the DFS carries its parent and only reports a visited neighbour that is not that parent. Both need an outer sweep over all vertices to cover disconnected graphs, both need a calloc-zeroed state array, and both recurse to the depth of the longest path.

Practice with these exercises

• Detect a cycle (directed)
• Detect a cycle (undirected)