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.

Key insight: A DAG can have multiple valid topological orderings. For example, if nodes A and B have no dependency between them, either can appear first. The algorithms below produce one valid ordering.

Real-World Examples

🏗️
Where topological sort appears
Dependencies are everywhere
  • 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

A #1 B #2 C #3 D #4 E #5 F #6 G #7
Node Topological order Arrows = directed edges (dependencies)

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.

Kahn's Algorithm — BFS Topological Sort Python
Output
Kahn's topological order: [0, 1, 2, 3, 4, 5, 6]
Complexity: Time O(V + E) — we visit every node once and process every edge once. Space O(V + E) for the graph and in-degree array.

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.
DFS-Based Topological Sort Python
Output
DFS topological order: [0, 2, 4, 1, 3, 5, 6]
Complexity: Time O(V + E), Space O(V + E). Same as Kahn's, but DFS uses recursion stack space (up to O(V) depth).

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.
Cycle Detection — 3-Color DFS Python
Output
DAG has cycle? False Cycle graph has cycle? True
Important: A visited set alone is NOT enough for cycle detection in directed graphs. In an undirected graph, revisiting a node means a cycle. In a directed graph, you might revisit a node via a different path (cross edge), which is not a cycle. The GRAY state distinguishes back edges (cycles) from cross edges (safe).

Kahn's vs DFS Topological Sort

FeatureKahn's (BFS)DFS Post-Order
ApproachBFS with in-degree countingDFS with post-order reversal
Data structureQueue (deque)Recursion stack
Time complexityO(V + E)O(V + E)
Space complexityO(V + E)O(V + E)
Cycle detectionlen(order) < VGRAY node revisited
Iterative?Yes (naturally iterative)Recursive (can be made iterative)
Best forWhen you need level-by-level processingWhen you're already doing DFS

Problem: Course Schedule II

🎓
LeetCode 210
Find a valid order to take all courses

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).

Course Schedule II — Kahn's Algorithm Python
Output
[0, 1, 2, 3] [] [0, 1, 2]
Complexity: Time O(V + E) where V = numCourses, E = len(prerequisites). Space O(V + E).

Problem: Alien Dictionary

👽
LeetCode 269
Derive character order from sorted alien words

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

  1. 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).
  2. Handle invalid input: If a longer word appears before its prefix (e.g., "abc" before "ab"), the input is invalid.
  3. Run Kahn's algorithm on the character graph to get the ordering.
Alien Dictionary — Build Graph + Kahn's Python
Output
Alien order: wertf Alien order: Alien order:
Complexity: Time O(C) where C = total number of characters across all words (we scan every character to build edges). The topological sort itself is O(V + E) where V = unique chars, E = ordering edges. Space O(V + E).

Problem: Task Scheduler

📋
LeetCode 621
Minimum intervals to complete all tasks with cooldown

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.

Task Scheduler — Greedy Python
Output
Min intervals: 8 Min intervals: 6 Min intervals: 16
Complexity: Time O(N) where N = number of tasks (one pass to count frequencies). Space O(1) since there are at most 26 distinct task types.

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

Push yourself further
Challenge 1: Parallel Courses (LeetCode 1136)

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.

Use Kahn's algorithm, but process level by level (like BFS levels). Each "level" is one semester. The number of levels in the BFS is the answer. If a cycle exists, return -1.
Challenge 2: Minimum Height Trees (LeetCode 310)

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.

Use a topological sort-like approach: repeatedly remove leaf nodes (degree 1) from the outside in. The last 1 or 2 nodes remaining are the answer. This is similar to Kahn's algorithm but on an undirected tree using degree instead of in-degree.

Quiz

Question 1 of 5
What does "DAG" stand for in the context of topological sort?
Question 2 of 5
In Kahn's algorithm, which nodes are added to the queue first?
Question 3 of 5
In 3-color DFS cycle detection, what does encountering a GRAY node during DFS indicate?
Question 4 of 5
What is the time complexity of topological sort (both Kahn's and DFS)?
Question 5 of 5
In the Alien Dictionary problem, how do you extract ordering constraints between characters?
0
/5
Great work! You understand topological sort.

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 is b → 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.

Next Lesson — Arc E Begins!

Lesson 18: Sorting Algorithms →
Africa & India's Best AI Academy
🤖 AI-first 🎓 Placement Assistance

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 →