Detecting cycles is a high-priority interview task. A cycle exists if you can start at node $A$ and follow a path that leads back to node $A$.

Undirected Graph (Friends)

Think of a Park Walk:

• You are walking through the park. If you reach a spot you've seen before, AND it's not the spot you just came from, you've walked in a circle!

Directed Graph (Deadlocks)

Think of a Job Application:

• To get a Job, you need Experience.
• To get Experience, you need a Job.
• This is a Deadlock (Cycle). In directed graphs, you only care if you hit a node that is currently in your current search path.

---

1. Undirected Cycle Detection (BFS/DFS)

Use visited set. If you encounter a visited node that is NOT the direct parent of the current node, a cycle exists.

2. Directed Cycle Detection (DFS + Recursion Stack)

Keep two sets: visited and recStack (Nodes in the current recursion path).

• If you hit a node already in recStack, it's a cycle!
• Topological Sort can also be used (Kahn’s Algorithm): If the resulting list has fewer than $V$ nodes, a cycle exists.

---

javascript Standard
/**
 * Detect Cycle in Directed Graph
 */
function hasCycle(n, adj) {
  const visited = new Set();
  const recStack = new Set();

  function dfs(u) {
    visited.add(u);
    recStack.add(u);

    for (const v of adj.get(u)) {
      if (!visited.has(v)) {
        if (dfs(v)) return true;
      } else if (recStack.has(v)) {
        return true; // Found a back-edge!
      }
    }

    recStack.delete(u); // Backtrack
    return false;
  }

  for (let i = 0; i < n; i++) {
    if (!visited.has(i)) {
      if (dfs(i)) return true;
    }
  }

  return false;
}

---

Top Use Case: Topological Sort

If a graph is a DAG (Directed Acyclic Graph), you can order its nodes such that for every directed edge $uv$, $u$ comes before $v$. Example: Build systems (Must compile library $A$ before project $B$).

Common Questions

• How do the algorithms differ for directed vs. undirected graphs?
• Use Dijkstra's logic or BFS to detect a cycle in a weighted graph.
• Course Schedule (LeetCode): Can you finish all courses given the prerequisites? This is a classic Cycle Detection problem. 🔄