Back
+30 XP
Concept

Directed Graph Cycle Detector (Kahn's Algorithm)

Circular dependencies in build pipelines (`A -> B -> C -> A`) lock task schedulers into deadlock freezes. Kahn's Algorithm calculates in-degrees (incoming prerequisites) for all vertices, repeatedly peeling away zero-in-degree nodes. If any unprocessed nodes remain, a cycle exists πŸ”„πŸ•ΈοΈπŸ›‘.

python
from collections import deque

def detect_cycle(nodes, edges):
    in_deg = [0] * nodes
    adj = [[] for _ in range(nodes)]
    for u, v in edges: adj[u].append(v); in_deg[v] += 1
    q = deque([i for i in range(nodes) if in_deg[i] == 0])
    count = 0
    while q:
        curr = q.popleft(); count += 1
        for nxt in adj[curr]:
            in_deg[nxt] -= 1
            if in_deg[nxt] == 0: q.append(nxt)
    return count != nodes

print("Cycle in (0->1->0):", detect_cycle(2, [(0, 1), (1, 0)]))

# 24. Directed Graph Cycle Detector (Kahn's Algorithm) Build tools (like Make, Webpack, Turborepo), package managers, and spreadsheet cell dependency graphs must guarantee that their dependency graph is a Directed Acyclic Graph (DAG) before attempting execution πŸ›‘. ```python # The Cyclic Deadlock Dilemma: # Module A depends on Module B # Module B depends on Module C # Module C depends on Module A # # Who builds first? # None can build! Every node has in_degree >= 1! ``` ### Kahn's Algorithm Flow ($O(V + E)$) 1. **Compute In-Degrees**: For every node $v$, calculate how many incoming arrows point to it. 2. **Initialize Queue with Roots**: Find all nodes with $\text{in\_degree} == 0$ (tasks that have no prerequisites) and push them to a `collections.deque`. 3. **Peel the Onion**: Pop a node, increment `visited_count`, and decrement the in-degree of all its downstream neighbors. 4. **Encounter Cycles**: If a cycle exists, the nodes in the cycle constantly keep each other's in-degree $\ge 1$. They never enter the queue, causing $\text{visited\_count} < V$ πŸ”„πŸ•ΈοΈπŸ›‘! --- ### Interactive Pop-Quiz 🧠 #### Why does Kahn's algorithm conclude that a directed graph contains a cycle if visited_count < total_nodes? - [ ] Nodes participating in a cycle never reach an in-degree of 0, so they are never added to the processing queue πŸ”„ - [ ] Because Python queues automatically reject cyclical pointers - [ ] Because in-degrees turn negative when cycles form - [ ] The operating system forcibly kills deadlocked graphs --- ### Practical Challenge 🎯 Implement `has_cycle(num_nodes: int, edges: list[tuple[int, int]]) -> bool` using Kahn's algorithm (in-degree tracking + BFS queue). Directed edge `(u, v)` represents dependency `u -> v`. Test with a clean DAG `[(0, 1), (1, 2)]` (expect `False`), and a cyclical graph `[(0, 1), (1, 2), (2, 0)]` (expect `True`). Assert both results and print output. <details> <summary>Solution</summary> ```python from collections import deque def has_cycle(num_nodes: int, edges: list[tuple[int, int]]) -> bool: in_degree = [0] * num_nodes adj = {i: [] for i in range(num_nodes)} for u, v in edges: adj[u].append(v) in_degree[v] += 1 queue = deque([i for i in range(num_nodes) if in_degree[i] == 0]) visited_count = 0 while queue: node = queue.popleft() visited_count += 1 for neighbor in adj[node]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor) return visited_count != num_nodes dag_clean = [(0, 1), (1, 2)] cycle_graph = [(0, 1), (1, 2), (2, 0)] assert has_cycle(3, dag_clean) is False assert has_cycle(3, cycle_graph) is True print("Kahn's cycle detector verified: clean DAG passed, cycle detected") ``` </details>

Checkpoint

Why does Kahn's algorithm conclude that a directed graph contains a cycle if `visited_count < total_nodes`? 🧠

Practice

Implement `has_cycle(num_nodes: int, edges: list[tuple[int, int]]) -> bool` using Kahn's algorithm (in-degree tracking + BFS queue). Directed edge `(u, v)` represents dependency `u -> v`. Test with a clean DAG `[(0, 1), (1, 2)]` (expect `False`), and a cyclical graph `[(0, 1), (1, 2), (2, 0)]` (expect `True`). Assert both results and print output. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks