Cycle detection

A cycle is a closed walk with distinct vertices (except start = end). Detecting cycles is essential for validating trees, detecting deadlocks in dependency graphs, and ruling out topological order when a directed cycle exists. The usual tool is DFS with extra state—the rule differs for undirected vs directed graphs.

1) Undirected graph

Run DFS from each unvisited component. When exploring edge (u, v), if v is already visited and v ≠ parent(u), you found a back edge → cycle. The edge to the parent is expected; any other visited neighbor closes a loop.

Triangle (cycle):             Path tree (acyclic):
    0                             0 — 1 — 2
   / \
  1---2

2) Directed graph

Track three states: 0 = unvisited, 1 = currently in the DFS recursion stack (being explored), 2 = finished. If an edge goes to a vertex in state 1, you found a back edge in the DFS forest → directed cycle. If an edge goes to state 2, it is a cross or forward edge in standard terminology—not necessarily a cycle by itself.

3) C — undirected cycle check

#include <string.h>
#define V 3
int adj[V][V];
int visited[V];

/* returns 1 if cycle starting from u with parent par */
int dfs_cycle_u(int u, int par) {
    visited[u] = 1;
    for (int v = 0; v < V; v++) {
        if (!adj[u][v]) continue;
        if (!visited[v]) {
            if (dfs_cycle_u(v, u)) return 1;
        } else if (v != par)
            return 1;   /* back edge to non-parent */
    }
    return 0;
}

int has_cycle_undirected(void) {
    memset(visited, 0, sizeof visited);
    for (int i = 0; i < V; i++)
        if (!visited[i] && dfs_cycle_u(i, -1))
            return 1;
    return 0;
}

4) C — directed cycle check

#define VD 3
int adjd[VD][VD];
/* state: 0 white, 1 gray (on stack), 2 black */
int state[VD];

int dfs_cycle_d(int u) {
    state[u] = 1;
    for (int v = 0; v < VD; v++) {
        if (!adjd[u][v]) continue;
        if (state[v] == 1) return 1;   /* back edge */
        if (state[v] == 0 && dfs_cycle_d(v)) return 1;
    }
    state[u] = 2;
    return 0;
}

int has_cycle_directed(void) {
    memset(state, 0, sizeof state);
    for (int i = 0; i < VD; i++)
        if (state[i] == 0 && dfs_cycle_d(i))
            return 1;
    return 0;
}

5) Complexity

• Time: O(V + E) with adjacency lists (each vertex/edge touched a constant number of times).
• Space: O(V) for visited / state and DFS stack depth.

6) Trace — undirected triangle (cycle)

Vertices 0, 1, 2; edges 0–1, 1–2, 2–0. DFS from 0, neighbor order increasing v. When at 2, neighbor 0 is visited and 0 ≠ parent(2)=1 → cycle detected.

7) Trace — directed 3-cycle

Arcs 0→1, 1→2, 2→0. States: 0 white, 1 gray, 2 black.