Traversal and connectivity · HTML
Maintain remaining indegree indeg[v]. Output any zero-indegree vertex and delete its outgoing edges. If fewer than V vertices are output, the remainder contains a cycle.
Recognition signals
- The story uses prerequisite, dependency, or build order.
- A permutation satisfying all precedence constraints is requested.
- The question asks whether every task can finish or whether a directed cycle exists.
- Completing one prerequisite removes exactly one unmet condition from each successor.
False friends
| Signal | Why it is different |
|---|
| Undirected connectivity | Undirected edges have no prerequisite direction; indegree elimination is not connectivity. |
| Profit-aware scheduling | Topology supplies feasibility only; optimizing value still needs a heap, greedy proof, or DP. |
Core invariant
Every frontier vertex has zero indegree in the remaining graph; outputting u changes only the indegrees of u's direct successors.
State, transition, and processing order
| Item | Definition |
|---|
| State | Indegree map, outgoing adjacency, zero-indegree frontier, and processed count or order. |
| Transition | Remove and output u; for each u→v decrement indeg[v], adding v exactly when it reaches zero. |
| Frontier / order | All currently executable vertices; a queue yields any order, while a min-heap can yield the lexicographically smallest one. |
Python skeleton
from collections import deque
def topo_order(nodes, edges):
graph = {u: [] for u in nodes}
indeg = {u: 0 for u in nodes}
for u, v in edges:
graph[u].append(v)
indeg[v] += 1
q = deque(u for u in nodes if indeg[u] == 0)
order = []
while q:
u = q.popleft()
order.append(u)
for v in graph[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return order if len(order) == len(nodes) else None
Correctness sketch
- A vertex is output only with zero remaining indegree, so every prerequisite still represented in the graph is already satisfied.
- Every nonempty DAG has a zero-indegree vertex, so elimination cannot stall on an acyclic remainder.
- If elimination stalls with vertices left, following predecessors indefinitely in a finite graph repeats a vertex and forms a directed cycle.
Complexity
| Time | Space | Parameters |
|---|
| O(V+E) | O(V+E) | V is the task count and E the dependency count; each edge is built and removed once. |
Edge cases
- With no edges, every order is valid.
- A self-loop can never reach zero indegree.
- Parallel edges must be consistently retained in both adjacency and indegree, or consistently deduplicated.
- Tasks absent from every edge still belong in nodes.
Error patterns
| Pattern | Why it fails / fix |
|---|
| Reversing edge direction | For prereq→task, increment the task's indegree. |
| Dropping isolated tasks | Inferring nodes solely from edges loses tasks with no dependencies. |
| Wrong cycle test | Kahn's criterion is processed==V, not a plain visited set. |
Selection and exclusion rules
- Prefer Kahn's method when an explicit order or parallel layers are needed.
- A three-color DFS is a viable alternative when only cycle detection matters.
- To test uniqueness, require exactly one frontier choice at every step.
Original micro-example
| Part | Detail |
|---|
| Result | grind, clean, brew, serve is valid but not unique. |
| Setup | brew requires grind, serve requires brew, and clean has no prerequisite. |
| Trace | grind and clean start available; completing grind releases brew, which later releases serve. |
Recall prompts
My notes