Cycle Detection

The Core Problem

A cycle is a path that starts and ends at the same vertex. Detecting cycles is essential for:

WHY CYCLE DETECTION MATTERS:
  Topological sort:    Only works on DAGs (no directed cycles)
  Deadlock detection:  Circular waiting = directed cycle in resource graph
  Infinite loops:      Cycle in dependency graph = no valid build order
  BST validation:      A proper BST has no cycles (it's a tree)

THREE DISTINCT PROBLEMS:
  1. Undirected graph — BFS with Pair(node, parent)
  2. Undirected graph — DFS with parent parameter
  3. Directed graph   — DFS with pathVisited[] (current stack)
  4. Directed graph   — Kahn's BFS (in-degree approach)

Approach 1 & 2 are equivalent (BFS vs DFS for undirected).
Approach 3 & 4 are equivalent (DFS vs BFS for directed).
The KEY difference is undirected vs directed — not BFS vs DFS.

Why Undirected and Directed Need Different Logic

UNDIRECTED GRAPH:
  Edge (u,v) exists in BOTH adjacency lists.
  When at node u (arrived from parent p):
    Neighbour p will always appear as "visited" — it's where we came from.
    We must skip p (it's our parent, not a back edge).
    Any OTHER visited neighbour → real back edge → CYCLE.

  CHECK: visited[nbr] AND nbr != parent

       A ─── B
       │     │
       C ─── D    ← 4-cycle: when DFS reaches D from C (parent=C),
                              D sees B as visited and B≠C → CYCLE ✓

DIRECTED GRAPH:
  Edge u→v exists ONLY in u's list (not v's list).
  When DFS finishes a node, it could be revisited from a different branch.
  Revisiting a FINISHED node → cross edge → NOT a cycle.
  Revisiting a node still ON the active path → back edge → CYCLE.

  CHECK: pathVisited[nbr] (currently on recursion stack)

       A → B → C
       ↑         |
       └─────────┘    Cycle: C→A is visited AND A is still on active path

       A → B → C
       D ─────→ C     No cycle: D→C reaches C which is FINISHED, not on stack

Approach 1: BFS Cycle Detection — Undirected Graph

Based on the reference Java implementation — Pair(node, parent) stored in the queue.

ALGORITHM:
  For each unvisited vertex (outer loop for disconnected graphs):
    Start BFS with Pair(start, -1) in queue.
    Mark start visited.
    While queue not empty:
      Dequeue Pair(node, parent).
      For each neighbour nbr of node:
        If nbr not visited: enqueue Pair(nbr, node), mark visited.
        Else if nbr != parent: CYCLE FOUND — return true.
  Return false (no cycle).

Sample Input (cyclic):    Sample Input (acyclic):
4 4                       4 3
0 1                       0 1
1 2                       1 2
2 3                       2 3
3 0

Output: Cycle is Detected    Output: Cycle is Not Detected

Dry Run: BFS Cycle Detection (Undirected)

Graph (cyclic): 0─1─2─3─0   (square — has a cycle)

Adjacency list:
  0: [1, 3]
  1: [0, 2]
  2: [1, 3]
  3: [2, 0]

visited = [F, F, F, F]

Outer loop: i=0, not visited
  Enqueue Pair(0, -1). visited[0]=T
  visited = [T, F, F, F]

  Dequeue Pair(0, -1):  node=0, parent=-1
    nbr=1: not visited → enqueue Pair(1,0), visited[1]=T
    nbr=3: not visited → enqueue Pair(3,0), visited[3]=T
  queue = [Pair(1,0), Pair(3,0)],  visited=[T,T,F,T]

  Dequeue Pair(1, 0):  node=1, parent=0
    nbr=0: visited AND 0==parent(0) → SKIP (same edge we came from)
    nbr=2: not visited → enqueue Pair(2,1), visited[2]=T
  queue = [Pair(3,0), Pair(2,1)],  visited=[T,T,T,T]

  Dequeue Pair(3, 0):  node=3, parent=0
    nbr=2: visited AND 2 ≠ parent(0) → CYCLE DETECTED! ✓
    return true

Output: "Cycle is Detected"

Approach 2: DFS Cycle Detection — Undirected Graph

Same logic as BFS, but using the call stack. Pass parent as a parameter.

ALGORITHM:
  dfs(node, parent, graph, visited):
    visited[node] = true
    for each nbr of node:
      if not visited[nbr]: recursively dfs(nbr, node, ...)
      else if nbr != parent: CYCLE (back edge to non-parent visited node)
    return false

Same input/output as BFS approach — both detect cycles correctly.
BFS uses Pair(node,parent) in queue.
DFS passes parent as a function parameter.

Approach 3: DFS Cycle Detection — Directed Graph

For directed graphs, visited[] alone is insufficient. We need pathVisited[] (also called inStack[]) to track the current active DFS path.

WHY visited[] ALONE FAILS FOR DIRECTED GRAPHS:

    A ──→ B ──→ C
              ↑
    D ─────────┘     No cycle! D→C is a cross edge.

  DFS from A: visits A, B, C (C marked visited).
  DFS from D: visits D, then tries C.
  C is visited → if we check visited[] alone → FALSE CYCLE DETECTION!

  But C is NOT on the current path (D→C) — it was reached via A→B→C earlier.
  pathVisited[C] = false (C is finished) → correctly detected as NOT a cycle.

CORRECT RULE:
  visited[nbr]     = ever been visited (any DFS path)
  pathVisited[nbr] = currently on the active DFS stack

  CYCLE ←→ pathVisited[nbr] is true when we try to visit nbr

CRITICAL: pathVisited[start] = false AFTER returning (backtrack)
  Removing start from the current path when we're done with it.

Cyclic directed (0→1→2→0):   Cycle detected
DAG (0→1→2→3):                Cycle not detected

Dry Run: DFS Directed Graph Cycle Detection

Graph:  0 ──→ 1 ──→ 2
              ↑       |
              └───────┘    Cycle: 1→2→1 (directed!)

Adjacency list (directed):
  0: [1]
  1: [2]
  2: [1]   ← creates the cycle

visited      = [F, F, F]
pathVisited  = [F, F, F]

Outer loop: i=0, not visited
  dfs(0):
    visited[0]=T, pathVisited[0]=T
    nbr=1: not visited
      dfs(1):
        visited[1]=T, pathVisited[1]=T
        nbr=2: not visited
          dfs(2):
            visited[2]=T, pathVisited[2]=T
            nbr=1: visited! AND pathVisited[1]=T → CYCLE DETECTED!
            return true
        return true
      return true

Output: "Cycle detected" ✓

CONTRAST — cross edge (NO cycle):
  0 ──→ 1 ──→ 2
             ↑
  3 ──────────┘

  dfs(0): visits 0,1,2 → finishes.  pathVisited[2]=false after 2 finishes.
  dfs(3): visits 3, tries 2.
    visited[2]=T but pathVisited[2]=F → NOT a cycle → skip.
  Output: "Cycle not detected" ✓

Approach 4: Kahn's Algorithm — Directed Graph

BFS-based approach using in-degrees. If all vertices are processed → no cycle. If some remain unprocessed → cycle.

ALGORITHM (Kahn's):
  1. Compute in-degree for every vertex.
  2. Enqueue all vertices with in-degree 0.
  3. While queue not empty:
       Dequeue vertex u.
       count++.
       For each neighbour v of u: decrement in-degree[v].
         If in-degree[v] == 0: enqueue v.
  4. If count == V: no cycle (valid topological order).
     If count <  V: cycle exists (those V-count vertices stuck with in-degree > 0).

INTUITION:
  Cycle vertices always have incoming edges from within the cycle.
  Their in-degree NEVER reaches 0 while cycle members exist.
  They are never enqueued → never counted.
  count < V signals cycle.

Cyclic directed:   Cycle detected
DAG:               Cycle not detected

Side-by-Side Comparison

APPROACH                 GRAPH TYPE  DATA STRUCTURE  KEY CHECK              COMPLEXITY
───────────────────────────────────────────────────────────────────────────────────────
BFS + Pair(node,parent)  Undirected  Queue           nbr != parent          O(V + E)
DFS + parent param       Undirected  Call stack      nbr != parent          O(V + E)
DFS + pathVisited[]      Directed    Call stack      pathVisited[nbr]==true O(V + E)
Kahn's (in-degree BFS)   Directed    Queue           count < V after BFS    O(V + E)

MEMORY:
  BFS approaches: O(V) queue + O(V) visited = O(V)
  DFS approaches: O(V) visited + O(V) pathVisited + O(h) call stack = O(V)

PREFERENCE:
  Undirected: either BFS or DFS — same result, choose based on comfort
  Directed:   DFS (pathVisited) is more intuitive for interview code
              Kahn's doubles as topological sort — versatile

Common Mistakes

Using visited[] alone for directed cycle detection. In directed graphs, a visited node reached via a different DFS path is a cross edge — NOT a cycle. Only a node currently on the ACTIVE recursion path (pathVisited/inStack = true) indicates a back edge and a real cycle. Using visited[] alone gives false positives for diamond-shaped DAGs.

Forgetting pathVisited[start] = false before returning in directed DFS. This is the most common implementation bug. Without resetting, nodes from earlier DFS paths remain "on the stack" — causing false cycle detection in later paths. Always reset pathVisited on backtrack.

Not handling disconnected graphs with the outer loop. BFS/DFS from a single starting vertex only covers one component. The outer loop for i in range(V): if not visited[i]: bfs/dfs(i) is required to check all components.

Confusing parent check for undirected vs directed. For undirected graphs: nbr != parent — skip only the direct parent edge. For directed: no parent check needed — use pathVisited instead. Applying parent check to directed graphs misses real cycles (the parent edge in an undirected sense doesn't exist in directed graphs).

Kahn's: computing in-degree incorrectly by reading adjacency list backwards. In-degree[v] = number of edges pointing TO v. Iterate over each u's adjacency list and increment in-degree of each neighbour (destination). A common mistake is iterating and incrementing the source instead of the destination.

Interview Questions

Q: Why does cycle detection for undirected graphs check nbr != parent but directed graphs check pathVisited[nbr]?

In an undirected graph, every edge appears in both direction adjacency lists. When DFS traverses from u to v, the edge v→u appears in v's list — visiting it doesn't mean a cycle, it's just the same edge traversed backwards. The parent check filters this out. In directed graphs, edges are one-directional — there's no "edge back to parent" issue. Instead, the problem is distinguishing back edges (real cycles) from cross edges (visiting a node reached via an earlier, unrelated path). Only back edges — reaching a node currently on the active recursion stack — indicate cycles.

Q: What is the difference between a cross edge and a back edge in DFS of a directed graph?

A back edge u→v means v is an ancestor of u in the current DFS tree — v is still on the active recursion stack. This creates a cycle (you can go from v down to u then directly back to v). A cross edge u→v means v was already fully explored in a previous DFS call and is no longer on the active stack — v's pathVisited is false. Cross edges don't create cycles. The back edge test is: visited[nbr] && pathVisited[nbr].

Q: When would you prefer Kahn's over DFS for cycle detection in directed graphs?

Kahn's has two advantages: (1) it simultaneously builds a topological ordering — if the graph is a DAG, the processed order IS a valid topological sort, so you get cycle detection + topological sort in one pass; (2) it avoids recursion stack overflow for very deep graphs. DFS-based detection is often simpler to implement and remembers exactly where the cycle is (you can add cycle path tracking). For interview purposes: if the problem also requires topological sort, use Kahn's. If only cycle detection is needed, DFS is slightly simpler.

Summary

Cycle detection has four canonical implementations — two for undirected, two for directed:

Undirected graphs:

• ›BFS + Pair(node, parent) — queue stores both vertex and its parent; cycle if visited neighbour ≠ parent
• ›DFS + parent parameter — recursion carries parent; same check: visited AND neighbour ≠ parent

Directed graphs:

• ›DFS + pathVisited[] — two boolean arrays: visited[] (ever seen) and pathVisited[] (currently on stack); cycle if pathVisited[nbr] is true; MUST reset pathVisited[u] = false on backtrack
• ›Kahn's algorithm — compute in-degrees, BFS from zero-in-degree vertices; cycle exists when processed count < V

All four run in O(V + E) time and O(V) space.

In the next topic you will explore Shortest Path Algorithms — Dijkstra's for positive weights and Bellman-Ford for negative weights.