Algorithms

Topological Sort: Ordering Dependencies

Цели урока

Understand the topological sort problem
Implement via DFS
Implement Kahn's algorithm (BFS)
Detect cycles

Предварительные знания

DFS: Depth-First Search

Every time you run npm install or make, topological sort is working behind the scenes. It guarantees that dependencies are built in the correct order.

Build systems (Make, Gradle, Bazel)
Package managers (npm, pip, cargo)
Compilers (module compilation order)
Spreadsheets (formula recalculation order)

Kahn's 1962 algorithm and the DFS approach

Topological sort showed up as an explicit algorithm in 1962, in a short note by Arthur Kahn titled Topological Sorting of Large Networks in Communications of the ACM. Kahn was working with project network models like PERT, where tasks depend on one another and must be laid out in a runnable order. His method is simple and visual: find the vertices with no incoming edges (the sources), remove them, decrement their neighbors' in-degrees, and repeat. If at some point there are no sources left but vertices remain, the graph has a cycle and no valid order exists. The second approach, via depth-first search, became widely known after Robert Tarjan formalized the DFS technique in the 1970s: just take the vertices in reverse finish order. Both run in O(V + E). The underlying idea is older still: it was implicit in the PERT and CPM network analysis of the late 1950s, built to manage large engineering and military projects.

Idea: Order the Dependencies

**Problem:** given dependencies between tasks, find an execution order where each task is completed after all its dependencies.

**Requirements:**

Graph must be **directed** (DAG = Directed Acyclic Graph)
**No cycles!** (otherwise no order is possible)
If there is an edge u → v, then u must come BEFORE v

**Cycle = no solution.** A depends on B, B on C, C on A - none can be executed first!

Graph: A→B, B→C, C→A. Topological sort:

Algorithm via DFS

**Idea:** in DFS a vertex 'closes' after all its descendants. So the reverse order of closing is topological!

Why does the DFS result need to be reversed?

Kahn's Algorithm (BFS)

**Alternative:** Kahn's algorithm. Iteratively removes vertices with no incoming edges.

	DFS	Kahn
Approach	Reverse exit order	Remove sources
Cycle detection	GRAY→GRAY edge	len(result) < V
Memory	O(V) recursion	O(V) queue
Parallelization	Harder	Easier (independent sources)

Kahn detects a cycle when:

Applications

**1. Build systems (Make, Gradle, npm):**

**2. Task scheduling:**

**3. Compilers (initialization order):**

**4. Spreadsheets (formula recalculation):**

In npm/yarn, dependencies form a cycle. What happens?