Trees, graphs and optimization
Topological sort
Order work constrained by dependencies.
Understand the problem
Compute indegrees and enqueue all zero-indegree vertices. Removing a vertex decrements each outgoing neighbor’s indegree. If fewer than V vertices are processed, a directed cycle exists.
Make it concrete
Course prerequisites form edges from prerequisites to dependents. Several valid orders may exist.
Trade-offs and pitfalls
Topological order exists only for directed acyclic graphs.
Check your understanding
Distinguish a cycle from an isolated vertex.
Practice this topic