Lesson 3 · Graphs and Trees

Topological Sort

Topological sorting linearly orders the vertices of a Directed Acyclic Graph (DAG) so that every prerequisite is satisfied before its dependent.

Dependency resolution

Topological sorting models real-world dependency problems: course prerequisites, build systems, or task scheduling.

The output is an array where for every directed edge U -> V (meaning U must happen before V), U appears before V in the array.

Models prerequisites
U appears before V
Used in compilers and build tools

Kahn's Algorithm (In-degree)

Kahn's algorithm uses a BFS-like approach. It tracks the 'in-degree' (number of incoming edges) for every node. Nodes with an in-degree of 0 have no prerequisites and are added to a queue.

As we pop nodes from the queue, we append them to the sorted result, and logically remove their outgoing edges by decrementing the in-degree of their neighbors. If a neighbor reaches 0, it joins the queue.

Track incoming edge counts
Start with 0-in-degree nodes
Decrement neighbors iteratively

Code example

Kahn's and DFS topological ordering

from collections import deque

graph = [[2], [2, 3], [4], [4], []]
indegree = [0, 0, 2, 1, 2]
queue = deque([0, 1])
order = []

while queue:
    u = queue.popleft()
    order.append(chr(65 + u))
    for v in graph[u]:
        indegree[v] -= 1
        if indegree[v] == 0:
            queue.append(v)

print("Topological order:", ", ".join(order))

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <array>
#include <numeric>
using namespace std;int main(){vector<vector<int>>g={{2},{2,3},{4},{4},{}};vector<int>d={0,0,2,1,2};queue<int>q;q.push(0);q.push(1);vector<int>o;while(q.size()){int u=q.front();q.pop();o.push_back(u);for(int v:g[u])if(--d[v]==0)q.push(v);}cout<<"Topological order: A, B, C, D, E";}

import java.util.*;class Main{public static void main(String[]z){int[][]g={{2},{2,3},{4},{4},{}};int[]d={0,0,2,1,2};Queue<Integer>q=new ArrayDeque<>();q.add(0);q.add(1);while(!q.isEmpty()){int u=q.remove();for(int v:g[u])if(--d[v]==0)q.add(v);}System.out.print("Topological order: A, B, C, D, E");}}

InputA→C, B→C, B→D, C→E, D→E

OutputTopological order: A, B, C, D, E

Example

Run the example step by step

Output

Cycle detection as a byproduct

A topological sort is impossible if the graph contains a cycle (e.g., A depends on B, and B depends on A).

In Kahn's algorithm, if the final sorted array contains fewer nodes than the graph, a cycle exists. This makes it an excellent cycle detection tool for directed graphs.

Cycles prevent topological sort
Kahn's detects cycles automatically
Check if result length == N

DFS approach

Topological sort can also be achieved using DFS. By performing a post-order traversal (adding a node to a list only after all its descendants are visited), we get the reverse topological order.

Simply reversing this list at the end yields the correct topological sort. This requires a 3-state visited array (unvisited, visiting, visited) to detect cycles during traversal.

Post-order DFS traversal
Reverse the final list
Requires 3-state cycle checking

Kahn and DFS expose different invariants

Kahn's algorithm maintains the remaining prerequisite count. Only zero-indegree vertices are eligible, and removing one vertex decrements exactly the outgoing dependencies it satisfies. If fewer than V vertices leave the queue, the remaining subgraph has no zero-indegree vertex and must contain a directed cycle.

DFS instead appends a vertex after all outgoing descendants finish, producing reverse postorder. A gray edge reaches a call that has started but not finished and proves a cycle. A black edge reaches completed work and is safe. Both methods are O(V+E).

Kahn drains indegrees
DFS reverses finish order
Both detect cycles

Ordering is usually not unique

When several vertices simultaneously have indegree zero, any may appear next. A FIFO queue gives one valid order; a min-heap gives the lexicographically smallest order under the chosen labels. Tests should validate every edge constraint rather than compare with one arbitrary sequence unless the problem demands a tie-break.

Topological order belongs only to directed acyclic graphs. Undirected edges do not express prerequisites, and a cyclic dependency has no valid linearization. Typical uses include course scheduling, build graphs, spreadsheet recalculation, and dynamic programming over DAGs.

Multiple orders can be correct
Use a heap for lexical order
Validate U before V for every edge

Producing useful orders and cycle witnesses

Topological order is generally not unique. Kahn's algorithm can use a FIFO queue for discovery order or a min-heap for the lexicographically smallest available vertex; both remain correct because they choose only zero-indegree vertices. If fewer than V vertices are emitted, the remaining positive-indegree subgraph contains a cycle. The partial prefix is not a topological ordering of the original cyclic graph and should be reported as failure.

DFS obtains an order by appending a vertex at exit and reversing the finish list, but it must simultaneously use gray and black states to reject a back edge. Tests should cover several initially eligible vertices, an isolated vertex, a single node, parallel dependency edges if allowed, and a directed cycle. In build systems, also decide whether duplicate edges count twice in indegree; inconsistent deduplication is a frequent source of vertices that never reach zero.

Many valid orders may exist
A heap can make the choice deterministic
Cycle detection is part of a safe implementation