Step 4 of 7

Topological sort: ordering tasks with dependencies

A build system must compile a library before the code that uses it; a course plan must schedule prerequisites first; a deploy pipeline runs tests before packaging. Draw each task as a node and each "must happen before" rule as a directed edge, and you get a DAG: a directed acyclic graph (no cycles, since a task can't depend on itself, even indirectly).

A topological order lists the nodes so that every edge u -> v has u before v. Kahn's algorithm finds one:

1. Count each node's in-degree: how many tasks must happen before it.
2. Every node with in-degree 0 is ready. Put those in a queue.
3. Take a ready node, append it to the order, and for each node that depended on it, lower its in-degree by one. Anything that reaches 0 becomes ready.
4. When nothing is ready any more: if the order holds every node, you're done. If it doesn't, the remaining nodes are stuck in (or behind) a cycle.

use std::collections::VecDeque;

fn main() {
    let tasks = ["fetch", "compile", "test", "lint", "package"];
    // (before, after): fetch must happen before compile, ...
    let deps = [(0, 1), (1, 2), (0, 3), (2, 4), (3, 4)];
    let n = tasks.len();
    let mut next: Vec<Vec<usize>> = vec![Vec::new(); n];
    let mut indegree = vec![0; n];
    for &(before, after) in &deps {
        next[before].push(after);
        indegree[after] += 1;
    }
    let mut ready: VecDeque<usize> = (0..n).filter(|&t| indegree[t] == 0).collect();
    let mut order = Vec::new();
    while let Some(t) = ready.pop_front() {
        order.push(tasks[t]);
        for &u in &next[t] {
            indegree[u] -= 1;
            if indegree[u] == 0 {
                ready.push_back(u);
            }
        }
    }
    if order.len() == n {
        println!("{}", order.join(" -> "));
    } else {
        println!("cycle!");
    }
}

fetch -> compile -> lint -> test -> package

Every node and edge is handled once: O(V + E).

Which ready task first?

Often several tasks are ready at once (compile and lint above), and any choice gives a valid order. If you need one specific, repeatable order (for reproducible builds, or so tests can check the output), always take the smallest ready task: keep the ready set in a BinaryHeap<Reverse<usize>> (a min-heap) or a BTreeSet. That costs O(log V) per task.

A topological order can also be built with DFS: a node is finished after all its descendants, so the reverse of the finishing order is a topological order. Kahn's version is easier to make deterministic and detects cycles for free.

Common mistakes

• Edge direction. "A depends on B" means B must come first: the edge is B -> A. Getting it backwards produces the exact reverse order.
• Ignoring cycles. If you don't check order.len() == n, the tasks in a cycle silently vanish from the plan.
• Iterating a HashMap of task names. The order of the ready tasks then changes from run to run. Use a BTreeMap/BTreeSet or sort.

Your task

Write fn build_order(n: usize, deps: &[(usize, usize)]) -> Option<Vec<usize>> for tasks 0..n, where each (a, b) means task a must run before task b. Return the order (always taking the smallest-numbered ready task next), or None if there's a cycle. The tests include a chain of 200,000 tasks, so rescanning all tasks for a ready one each time is too slow.

Challenge 2

The CI system reads its pipeline from standard input. Each line is a job, a colon, and the jobs it depends on: test: build lint means test runs after build and lint. A job may have no dependencies (fetch:), and a job that only appears as a dependency is a job too. Skip blank lines.

Print the run order, one job per line numbered from 1 (1. fetch), always running the alphabetically first ready job next. If some jobs can never run because of a dependency cycle, print only cycle: followed by those jobs in alphabetical order, separated by , , and exit with code 1 (std::process::exit(1)).

Work with names directly: a BTreeMap<String, usize> of in-degrees, a BTreeMap<String, Vec<String>> of who waits for each job, and a BTreeSet<String> of ready jobs (pop_first gives the alphabetically first).

Challenge 3

A university wants to know the minimum number of semesters to finish n courses (0..n) when each (a, b) means course a must be passed in an earlier semester than course b, and students can take any number of courses per semester. Write fn min_semesters(n: usize, prereqs: &[(usize, usize)]) -> Option<usize> (None if a cycle makes it impossible; 0 for no courses).

Run Kahn's algorithm in layers: all courses ready now form one semester; taking them makes the next layer ready. Count the layers. The tests include a chain of 100,000 courses.

Previous: Depth-first search: recursion and an explicit stack Next: Dijkstra's shortest paths with BinaryHeap