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.