Topological sort is an algorithmic method for ordering the vertices of a directed graph so every prerequisite comes before the item that depends on it. It is essential for scheduling tasks, resolving build dependencies, planning course prerequisites, and analyzing partial orders. This cheat sheet helps students compare the two standard approaches, DFS-based sorting and Kahn’s algorithm, while keeping the rules and edge cases clear.
Key Facts
- A topological ordering of a directed graph places every edge u -> v so that u appears before v in the ordering.
- A graph has a topological ordering if and only if it is a directed acyclic graph, also called a DAG.
- DFS topological sort adds each vertex to the front of the answer, or pushes it onto a stack, after all of its outgoing neighbors are fully visited.
- In DFS cycle detection, a back edge to a vertex currently in the recursion stack means the graph has a directed cycle.
- Kahn’s algorithm starts with all vertices of indegree 0, repeatedly removes one, appends it to the order, and decreases the indegree of its outgoing neighbors.
- If Kahn’s algorithm outputs fewer than V vertices, then at least one cycle exists in the graph.
- Both DFS topological sort and Kahn’s algorithm run in O(V + E) time when the graph uses adjacency lists.
- Topological order is not necessarily unique because multiple vertices may have indegree 0 or be otherwise unconstrained at the same time.
Vocabulary
- Directed graph
- A graph whose edges have direction, so an edge u -> v goes from vertex u to vertex v.
- DAG
- A directed acyclic graph, meaning a directed graph with no directed cycles.
- Topological order
- A linear ordering of vertices where every prerequisite vertex appears before each vertex that depends on it.
- Indegree
- The number of directed edges entering a vertex.
- Back edge
- In DFS, an edge from a vertex to an ancestor currently on the recursion stack, which indicates a cycle in a directed graph.
- Adjacency list
- A graph representation that stores, for each vertex, the list of vertices reached by its outgoing edges.
Common Mistakes to Avoid
- Using topological sort on an undirected graph is wrong because topological ordering is defined for directed dependency relationships.
- Forgetting to detect cycles is wrong because a directed cycle makes a valid topological order impossible.
- Appending a DFS vertex before exploring its outgoing neighbors is wrong for the standard DFS method because dependents may be placed before prerequisites.
- Updating indegrees incorrectly in Kahn’s algorithm is wrong because only outgoing neighbors of the removed vertex should have their indegree decreased.
- Assuming there is only one correct topological order is wrong because independent vertices can often be arranged in multiple valid ways.
Practice Questions
- 1 Given edges A -> C, B -> C, C -> D, and B -> E, list one valid topological ordering.
- 2 For vertices A, B, C, D with edges A -> B, A -> C, B -> D, and C -> D, compute the initial indegree of each vertex.
- 3 Run one possible version of Kahn’s algorithm on edges 1 -> 3, 2 -> 3, 3 -> 4, and 2 -> 5, choosing the smallest available vertex first.
- 4 Explain why the graph with edges X -> Y, Y -> Z, and Z -> X cannot have a topological ordering.
Understanding Topological Sort Reference
The hardest part is often choosing what each arrow means. In a dependency graph, an arrow from A to B usually means A must be finished before B can begin. In other programs, an arrow may mean B depends on A.
Both conventions are valid, but mixing them reverses the result. Write down one sentence defining the arrow before coding. A graph may have several disconnected groups.
A correct ordering still includes every vertex, even when one group has no links to another. Isolated vertices have no requirements and no dependents, so they can appear almost anywhere.
Depth first search works by following a chain of unfinished work as far as possible. A vertex is placed only when the search has returned from every vertex it points to. This finishing moment is important.
Recording a vertex when it is first discovered gives an order that can violate dependencies. Many implementations use three states. An unvisited vertex has not been explored.
A visiting vertex is on the current search path. A finished vertex has had all relevant outgoing edges processed.
Meeting a visiting vertex reveals a loop in the dependency chain. Keeping parent links can help reconstruct the actual cycle for an error message.
Kahn's algorithm treats indegree as a count of requirements that remain unmet. Removing a ready vertex is like marking one completed task. Each outgoing edge lowers the count of a task that was waiting for it.
When the count reaches zero, that task becomes ready. A queue gives one valid result, while a priority queue can choose the alphabetically smallest ready item for a predictable result.
This matters in build tools, test output, and grading, where two correct runs should ideally produce the same displayed order. The list of currently ready vertices is useful information because it shows which tasks could proceed in parallel.
A cycle is more than a failed algorithm. It represents impossible requirements. For example, a course plan may say that course A requires course B, course B requires course C, and course C requires course A.
No course can be taken first. In a software build, the same problem can arise through imported modules or generated files. Students should test empty graphs, one vertex, disconnected components, duplicate edges, and a graph with a known cycle.
Duplicate edges need careful handling because each stored edge changes an indegree count. With adjacency lists, the work grows roughly with the number of vertices plus the number of edges, since each vertex and each edge is processed a limited number of times.