What Is a DAG & Topological Ordering
A Directed Acyclic Graph (DAG) is a directed graph with no cycles. If you follow the arrows, you can never loop back to a node you already visited. This property makes DAGs perfect for modelling dependencies.
A topological ordering (or topological sort) of a DAG is a linear ordering of its vertices such that for every directed edge u → v, vertex u comes before vertex v in the ordering. A topological sort is only possible if the graph is a DAG. If the graph has a cycle, no valid ordering exists.
Real-World Examples
- Build systems (Make, Gradle, Webpack): Source files depend on headers and libraries. The build order is a topological sort of the dependency graph.
- Course prerequisites: You cannot take "Machine Learning" before "Linear Algebra." Given all courses and prerequisites, topological sort finds a valid semester plan.
- Task scheduling: In project management, some tasks must finish before others can start. A topological sort gives a valid execution order.
- Package managers (pip, npm): Package A depends on B which depends on C. Installation order is determined by topological sort.
- Spreadsheet cell evaluation: Cell A1 references B2 which references C3. The evaluation order is a topological sort of the cell dependency graph.
DAG with Topological Order
Below is a DAG with 7 nodes. Each node is labelled with its name, and the red number shows one valid topological order (the position in the sorted output).
DAG — Topological Order Numbered
One valid topological order is [A, B, C, D, E, F, G]. Another valid order could be [A, C, B, E, D, F, G]. Both satisfy the constraint that every dependency comes before the dependent node.
Kahn's Algorithm (BFS with In-Degree)
Kahn's algorithm uses a BFS-like approach with an in-degree counter for each node. The in-degree of a node is the number of edges pointing into it. Nodes with in-degree 0 have no dependencies and can be processed first.
Kahn's Algorithm — Step by Step
Step 1: Count In-Degrees
For each node, count how many edges point to it. Store in an in_degree dictionary.
Step 2: Initialize Queue
Add all nodes with in_degree == 0 to a deque. These have no prerequisites.
Step 3: Process BFS
Pop a node from the queue, add it to the result. For each neighbour, decrement its in-degree. If in-degree drops to 0, add it to the queue.
Step 4: Detect Cycle
If the result contains all V nodes, the ordering is valid. If not, the graph has a cycle.
DFS-Based Topological Sort
The DFS approach exploits a key property: in a DFS traversal of a DAG, a node finishes (returns from its recursive call) only after all its descendants have finished. By collecting nodes in post-order and then reversing, we get a valid topological order.
How it works
- Run DFS from each unvisited node.
- After visiting all neighbours of a node, push it onto a stack (post-order).
- Reverse the stack at the end to get topological order.
Cycle Detection in Directed Graphs
Detecting cycles in a directed graph is a critical prerequisite for topological sort. If a cycle exists, no topological ordering is possible. The standard approach uses 3-color DFS (WHITE / GRAY / BLACK).
The 3-Color Approach
- WHITE (0): Node has not been visited yet.
- GRAY (1): Node is currently being processed (in the DFS call stack). If we encounter a GRAY node, we have found a back edge, which means a cycle.
- BLACK (2): Node and all its descendants are fully processed. Encountering a BLACK node is safe — it just means we have already explored that subtree.
Kahn's vs DFS Topological Sort
| Feature | Kahn's (BFS) | DFS Post-Order |
|---|---|---|
| Approach | BFS with in-degree counting | DFS with post-order reversal |
| Data structure | Queue (deque) | Recursion stack |
| Time complexity | O(V + E) | O(V + E) |
| Space complexity | O(V + E) | O(V + E) |
| Cycle detection | len(order) < V | GRAY node revisited |
| Iterative? | Yes (naturally iterative) | Recursive (can be made iterative) |
| Best for | When you need level-by-level processing | When you're already doing DFS |
Problem: Course Schedule II
There are numCourses courses labelled 0 to numCourses-1. You are given a list of prerequisites where [a, b] means you must take course b before course a. Return a valid ordering of courses, or an empty list if it is impossible (cycle exists).
Problem: Alien Dictionary
Given a list of words sorted in an alien language's lexicographic order, derive the order of characters in that language. The key insight: compare adjacent words character by character to extract ordering constraints, then run topological sort on those constraints.
Approach
- Extract edges: For each pair of adjacent words, find the first character that differs. This gives us an edge:
char1 → char2(char1 comes before char2 in the alien alphabet). - Handle invalid input: If a longer word appears before its prefix (e.g., "abc" before "ab"), the input is invalid.
- Run Kahn's algorithm on the character graph to get the ordering.
Problem: Task Scheduler
Given a list of tasks (characters) and a cooldown interval n, find the minimum number of intervals the CPU needs to finish all tasks. The same task must wait at least n intervals before it can be executed again. Idle slots are allowed.
Greedy approach
This problem is best solved with a greedy/mathematical approach rather than topological sort. The key insight: the most frequent task determines the minimum time. We arrange tasks in "frames" of size n + 1, filling the most frequent tasks first.
Try It Yourself
Course Ordering Challenge
Given 6 courses (0-5) and their prerequisites, find a valid order to take all courses. If no valid order exists, print "IMPOSSIBLE".
Prerequisites: Course 1 requires 0. Course 2 requires 0. Course 3 requires 1 and 2. Course 4 requires 3. Course 5 requires 4.
Challenge
Given n courses and prerequisite pairs, find the minimum number of semesters needed to take all courses, assuming you can take any number of courses simultaneously in a semester as long as prerequisites are met. This is the longest path in the DAG.
Given a tree with n nodes, find all nodes that, when used as root, minimize the height of the tree. These are the "centroid" nodes of the tree.
Quiz
Common Mistakes
- Using a visited set instead of 3-color for cycle detection in directed graphs. A simple visited set works for undirected graphs, but in directed graphs you need WHITE/GRAY/BLACK to distinguish back edges (cycles) from cross edges (safe). Encountering a previously visited node via a cross edge is not a cycle.
- Forgetting to reverse post-order in DFS topological sort. DFS finishes leaf nodes first, so the raw post-order is reversed. If you forget
order[::-1], your topological sort is backwards — dependencies come after dependents. - Not checking for cycles before returning the topological order. If the graph has a cycle, Kahn's algorithm will not process all nodes (some will remain with in-degree > 0). Always verify
len(order) == num_nodes. - In Alien Dictionary, comparing non-adjacent words. Only adjacent word pairs in the sorted list give valid ordering constraints. Comparing words[0] with words[2] skips information and can produce incorrect edges.
- Confusing edge direction in Course Schedule. The prerequisite
[a, b]means b must come before a, so the edge isb → a. Reversing this gives a wrong graph and wrong answers.
Key Takeaways
- Topological sort = linear ordering of a DAG, O(V + E). Use it whenever you need to process nodes in dependency order. It only works on DAGs — if a cycle exists, no valid ordering is possible.
- Two approaches: Kahn's (BFS) and DFS post-order reversal. Kahn's uses in-degree counting and a queue. DFS uses post-order collection and stack reversal. Both give valid topological orderings and run in O(V + E).
- Cycle detection in directed graphs requires 3 colors. WHITE (unvisited), GRAY (in progress), BLACK (done). A back edge to a GRAY node proves a cycle. A simple visited set is insufficient for directed graphs.
- Alien Dictionary = build graph from word comparisons + topo sort. Compare adjacent sorted words to extract character ordering edges, then run Kahn's. This pattern of "extract constraints, then topological sort" is extremely common.
- Course Schedule is the canonical topological sort interview problem. If you can solve Course Schedule II (LeetCode 210) cleanly with Kahn's algorithm, you can handle most topological sort variants in interviews.
You've mastered topological sort.
Now build the career it unlocks.
Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.
Explore our AI-era courses →