Graph Theory37 sections · 1633 units
Open in Course

Common Topological Sort Mistakes

Pitfalls to avoid

Mistake 11: Forgetting to check for cycles. Topological sort only works on DAGs. If your graph has cycles, Kahn's algorithm gives an incomplete result, and DFS-based sort might loop forever without proper cycle detection.

Mistake 22: Using the wrong direction. If prerequisites[i] = [a, b] means "b before a", the edge is b → a, not a → b. Read the problem carefully.

Mistake 33: Not handling disconnected graphs. Always iterate through all nodes, not those reachable from a single start. Some nodes might have in-degree 00 but not be connected to others.

Mistake 44: Confusing topological order with shortest path. Topological order is any valid ordering. It does not minimize anything. Use it as a preprocessing step for DP, not as a final answer.