Which Course First? Topological Sort

Plan an order for a student's courses where every prerequisite comes first, fast even for a huge catalog, and spot the loop of prerequisites that makes any order impossible: why alphabetical order, sorting by prerequisite count and rescanning the catalog all fall short, and the method that fixes them, a topological sort.

Freelancer · Data Structures · Updated

By

After this lesson you can

  • Order tasks so every prerequisite comes first, using a topological sort
  • Spot a loop of prerequisites that makes a topological sort impossible
  • Choose breadth-first search, Dijkstra's algorithm or a topological sort for a graph job, and say why

Key takeaways

  • Alphabetical order and sorting by how many prerequisites a course has both put a course before what it needs; rescanning the whole catalog each round works but costs O(V × (V + E)).
  • A topological sort puts the vertices of a one-way graph in an order where every edge points forward: every prerequisite comes first.
  • Count what each task still waits on; a task waiting on nothing is ready. Take a ready task, and cross it off the tasks it unlocks.
  • If tasks are left over that never become ready, they wait on each other in a loop, and no order works.
  • It looks at every task and every prerequisite once, so it takes O(V + E) time.

Before this: breadth-first search and Dijkstra's algorithm answer "how far?". A course catalog asks something new about one-way edges: "in what order?"

A college's planning app has to show each student an order to take their courses in, where every course comes after the courses it needs. Here's a small catalog of six courses and its prerequisites, each one a one-way "before" edge:

Before After
Programming 1 Programming 2
Programming 2 Data Structures
Discrete Math Data Structures
Data Structures Algorithms
Programming 2 Databases

The same question runs all over software: a build tool compiling each project after the ones it uses, a package manager installing what a package depends on first, a spreadsheet calculating each cell after the cells it reads. In what order can you take the six courses?

What would you try?

Alphabetical order. Algorithms, Data Structures, Databases, Discrete Math, Programming 1, Programming 2. The very first course, Algorithms, needs Data Structures, which needs Programming 2. Alphabetical order knows nothing about the arrows.

Sort by how many prerequisites each course has, fewest first. Programming 1 and Discrete Math have none; Programming 2, Algorithms and Databases have one each; Data Structures has two. So: Programming 1, Discrete Math, Programming 2, Algorithms, Databases, Data Structures. It looks closer, but Algorithms still comes before Data Structures. A count says how many prerequisites a course has, not whether they're done yet.

Rescan the catalog, round after round. Each round, read every course and pick one whose prerequisites are all placed already. Round 1 finds Programming 1, round 2 Discrete Math, round 3 Programming 2, and so on. This one works. But each round reads the whole catalog and its prerequisites again, to place one course: O(V × (V + E)) for V courses and E prerequisites. For six courses that's nothing. For a catalog of 10,000 courses in one long chain, listed backward, it took 30 seconds in Python.

What we tried The plan it gives Where it breaks
Alphabetical Algorithms first ignores the arrows
Fewest prerequisites first Algorithms before Data Structures counts prerequisites, doesn't check them
Rescan every round a right order O(V × (V + E)): 30 seconds for 10,000 courses

The questions that lead to it

When a student finishes Programming 1, which courses might have become ready? Only the ones it comes before: Programming 2. Nothing else changed, so rereading the whole catalog is wasted work.

What if each course kept a count of what it still waits on? Data Structures starts at 2. Finishing Programming 2 takes it to 1; finishing Discrete Math takes it to 0, and at 0 it's ready. No rescanning: each finished course crosses itself off the few courses it unlocks.

And the courses that are ready: in what order do we take them? Any order works. A line, a queue from Module 2, takes them in the order they became ready.

What if a count never reaches 0? Then that course waits on something that waits on it. Hold that thought for the loop below.

How it got its name

An order like this was so useful that it got a name: a topological sort. It puts the vertices of a one-way graph in a line so every arrow points forward: every course comes after all of its prerequisites. There's often more than one right answer (Discrete Math could come first or second), and any of them will do.

The counting method is often called Kahn's algorithm, after Arthur Kahn, who published it in 1962. It's how a careful student plans:

  1. Count how many prerequisites each course is still waiting on. Programming 1 and Discrete Math wait on nothing, so they're ready. Data Structures waits on 2.
  2. Take a ready course from the front of the line and add it to the plan.
  3. Unlock: for every course it comes before, take 1 off that course's count. A course whose count reaches 0 joins the back of the ready line.
  4. Repeat until the line is empty.
Take Unlocks (count after) Ready line after
(start) Programming 1, Discrete Math
Programming 1 Programming 2 (0) Discrete Math, Programming 2
Discrete Math Data Structures (1) Programming 2
Programming 2 Data Structures (0), Databases (0) Data Structures, Databases
Data Structures Algorithms (0) Databases, Algorithms
Databases Algorithms
Algorithms (empty)

The course catalog drawn as six boxes joined by arrows from each prerequisite to the course it unlocks, Programming 1 to Programming 2, Programming 2 to Data Structures and to Databases, Discrete Math to Data Structures, and Data Structures to Algorithms, and beneath it the same six courses in the order the topological sort gives, numbered 1 to 6, with every arrow now pointing forward

A loop makes it impossible

Now suppose a catalog has a mistake: Programming 2 also requires Algorithms. Programming 2 waits on Algorithms, which waits on Data Structures, which waits on Programming 2. Each waits on another in a circle, so none of their counts can ever reach 0.

A path of one-way edges that leads back to where it started is a cycle (a loop). A topological sort is possible exactly when the graph has no cycle, which is why textbooks call the graphs it works on directed acyclic graphs, or DAGs ("acyclic", read "ay-SY-click", means "without a cycle").

You don't need a separate check to find one. Run the same steps: when the ready line is empty but some courses were never placed, those courses are stuck in, or behind, a loop.

Topological sort in code

Plan follows the four steps, then the code runs it twice: on the catalog, and on the catalog with the mistake added.

string[] courses = { "Programming 1", "Discrete Math", "Programming 2", "Data Structures", "Algorithms", "Databases" };
List<(string Before, string After)> prerequisites = new List<(string Before, string After)>
{
    ("Programming 1", "Programming 2"), ("Programming 2", "Data Structures"), ("Discrete Math", "Data Structures"),
    ("Data Structures", "Algorithms"), ("Programming 2", "Databases"),
};

List<string> Plan(string[] courses, List<(string Before, string After)> prerequisites)
{
    Dictionary<string, List<string>> unlocks = new Dictionary<string, List<string>>();
    Dictionary<string, int> waitingOn = new Dictionary<string, int>();
    foreach (string course in courses)
    {
        unlocks[course] = new List<string>();
        waitingOn[course] = 0;
    }
    foreach ((string before, string after) in prerequisites)
    {
        unlocks[before].Add(after);
        waitingOn[after]++;
    }
    Queue<string> ready = new Queue<string>(courses.Where(course => waitingOn[course] == 0));
    List<string> order = new List<string>();
    while (ready.Count > 0)
    {
        string course = ready.Dequeue();
        order.Add(course);
        foreach (string next in unlocks[course])
        {
            waitingOn[next]--;
            if (waitingOn[next] == 0)
            {
                ready.Enqueue(next);
            }
        }
    }
    return order;
}

Console.WriteLine("Order: " + string.Join(", ", Plan(courses, prerequisites)));
List<(string Before, string After)> withLoop = new List<(string Before, string After)>(prerequisites) { ("Algorithms", "Programming 2") };
List<string> stuck = Plan(courses, withLoop);
Console.WriteLine("With a loop: placed " + stuck.Count + " of " + courses.Length + " courses");
Order: Programming 1, Discrete Math, Programming 2, Data Structures, Databases, Algorithms
With a loop: placed 2 of 6 courses
String[] courses = {"Programming 1", "Discrete Math", "Programming 2", "Data Structures", "Algorithms", "Databases"};
List<List<String>> prerequisites = List.of(
    List.of("Programming 1", "Programming 2"), List.of("Programming 2", "Data Structures"), List.of("Discrete Math", "Data Structures"),
    List.of("Data Structures", "Algorithms"), List.of("Programming 2", "Databases"));

List<String> plan(String[] courses, List<List<String>> prerequisites) {
    Map<String, List<String>> unlocks = new HashMap<>();
    Map<String, Integer> waitingOn = new HashMap<>();
    for (String course : courses) {
        unlocks.put(course, new ArrayList<>());
        waitingOn.put(course, 0);
    }
    for (List<String> pair : prerequisites) {
        unlocks.get(pair.get(0)).add(pair.get(1));
        waitingOn.put(pair.get(1), waitingOn.get(pair.get(1)) + 1);
    }
    Queue<String> ready = new ArrayDeque<>();
    for (String course : courses) {
        if (waitingOn.get(course) == 0) {
            ready.add(course);
        }
    }
    List<String> order = new ArrayList<>();
    while (!ready.isEmpty()) {
        String course = ready.remove();
        order.add(course);
        for (String next : unlocks.get(course)) {
            waitingOn.put(next, waitingOn.get(next) - 1);
            if (waitingOn.get(next) == 0) {
                ready.add(next);
            }
        }
    }
    return order;
}

void main() {
    IO.println("Order: " + String.join(", ", plan(courses, prerequisites)));
    List<List<String>> withLoop = new ArrayList<>(prerequisites);
    withLoop.add(List.of("Algorithms", "Programming 2"));
    List<String> stuck = plan(courses, withLoop);
    IO.println("With a loop: placed " + stuck.size() + " of " + courses.length + " courses");
}
Order: Programming 1, Discrete Math, Programming 2, Data Structures, Databases, Algorithms
With a loop: placed 2 of 6 courses
from collections import deque

courses = ["Programming 1", "Discrete Math", "Programming 2", "Data Structures", "Algorithms", "Databases"]
prerequisites = [
    ("Programming 1", "Programming 2"), ("Programming 2", "Data Structures"), ("Discrete Math", "Data Structures"),
    ("Data Structures", "Algorithms"), ("Programming 2", "Databases"),
]


def plan(courses, prerequisites):
    unlocks = {course: [] for course in courses}
    waiting_on = {course: 0 for course in courses}
    for before, after in prerequisites:
        unlocks[before].append(after)
        waiting_on[after] += 1
    ready = deque(course for course in courses if waiting_on[course] == 0)
    order = []
    while ready:
        course = ready.popleft()
        order.append(course)
        for following in unlocks[course]:
            waiting_on[following] -= 1
            if waiting_on[following] == 0:
                ready.append(following)
    return order


print("Order: " + ", ".join(plan(courses, prerequisites)))
with_loop = prerequisites + [("Algorithms", "Programming 2")]
stuck = plan(courses, with_loop)
print(f"With a loop: placed {len(stuck)} of {len(courses)} courses")
Order: Programming 1, Discrete Math, Programming 2, Data Structures, Databases, Algorithms
With a loop: placed 2 of 6 courses
const courses = ["Programming 1", "Discrete Math", "Programming 2", "Data Structures", "Algorithms", "Databases"];
const prerequisites = [
  ["Programming 1", "Programming 2"], ["Programming 2", "Data Structures"], ["Discrete Math", "Data Structures"],
  ["Data Structures", "Algorithms"], ["Programming 2", "Databases"],
];

function plan(courses, prerequisites) {
  const unlocks = new Map(courses.map((course) => [course, []]));
  const waitingOn = new Map(courses.map((course) => [course, 0]));
  for (const [before, after] of prerequisites) {
    unlocks.get(before).push(after);
    waitingOn.set(after, waitingOn.get(after) + 1);
  }
  const ready = courses.filter((course) => waitingOn.get(course) === 0);
  let head = 0;
  const order = [];
  while (head < ready.length) {
    const course = ready[head];
    head++;
    order.push(course);
    for (const next of unlocks.get(course)) {
      waitingOn.set(next, waitingOn.get(next) - 1);
      if (waitingOn.get(next) === 0) {
        ready.push(next);
      }
    }
  }
  return order;
}

console.log(`Order: ${plan(courses, prerequisites).join(", ")}`);
const withLoop = [...prerequisites, ["Algorithms", "Programming 2"]];
const stuck = plan(courses, withLoop);
console.log(`With a loop: placed ${stuck.length} of ${courses.length} courses`);
Order: Programming 1, Discrete Math, Programming 2, Data Structures, Databases, Algorithms
With a loop: placed 2 of 6 courses
const courses: string[] = ["Programming 1", "Discrete Math", "Programming 2", "Data Structures", "Algorithms", "Databases"];
const prerequisites: [string, string][] = [
  ["Programming 1", "Programming 2"], ["Programming 2", "Data Structures"], ["Discrete Math", "Data Structures"],
  ["Data Structures", "Algorithms"], ["Programming 2", "Databases"],
];

function plan(courses: string[], prerequisites: [string, string][]): string[] {
  const unlocks = new Map<string, string[]>(courses.map((course) => [course, []]));
  const waitingOn = new Map<string, number>(courses.map((course) => [course, 0]));
  for (const [before, after] of prerequisites) {
    unlocks.get(before)!.push(after);
    waitingOn.set(after, waitingOn.get(after)! + 1);
  }
  const ready = courses.filter((course) => waitingOn.get(course) === 0);
  let head = 0;
  const order: string[] = [];
  while (head < ready.length) {
    const course = ready[head];
    head++;
    order.push(course);
    for (const next of unlocks.get(course) ?? []) {
      waitingOn.set(next, waitingOn.get(next)! - 1);
      if (waitingOn.get(next) === 0) {
        ready.push(next);
      }
    }
  }
  return order;
}

console.log(`Order: ${plan(courses, prerequisites).join(", ")}`);
const withLoop: [string, string][] = [...prerequisites, ["Algorithms", "Programming 2"]];
const stuck = plan(courses, withLoop);
console.log(`With a loop: placed ${stuck.length} of ${courses.length} courses`);
Order: Programming 1, Discrete Math, Programming 2, Data Structures, Databases, Algorithms
With a loop: placed 2 of 6 courses

With the loop, only Programming 1 and Discrete Math are placed. Programming 2, Data Structures and Algorithms wait on each other forever, and Databases waits behind Programming 2. The program doesn't hang: it notices that 2 is less than 6 and can say so.

Try it. Add a seventh course, "Capstone", that needs Algorithms and Databases. Add it to the courses and two pairs to the prerequisites, and it comes out last.

In your textbook

Many textbooks sort with depth-first search instead (Who Can I Reach? Depth-First Search): when a course's search finishes, every course after it has already been placed, so writing courses down as their searches finish and turning the list around gives a topological order. It finds loops too, as an edge back to a course whose search hasn't finished. Both methods take O(V + E) time; the counting method needs no recursion, so a chain of 50,000 courses can't run it out of call stack.

Which graph tool for which job?

This chapter and the last gave you four tools for graphs. The job's question picks one:

The job asks Use Why
How few hops, stops or friendships? Breadth-first search Every edge counts as one step
Who can I reach at all? Which groups are separate? Either search (depth-first is the usual) Both visit everything reachable once
The cheapest total time, distance or cost? Dijkstra's algorithm Edges have different weights, and it settles the closest place first
In what order, so every "before" comes first? A topological sort Edges mean "before", and it places a task only when everything it waits on is placed

Cost card

What it does Big-O The everyday reason
Count what each course waits on O(V + E) One count per course, and one look at each prerequisite
Place every course in order O(V + E) Each course joins the ready line once, and each prerequisite is crossed off once
Spot a loop Included Courses left unplaced at the end are stuck in, or behind, a loop
Memory O(V + E) The unlock lists, the counts and the ready line

Check yourself

2 questions to try on the lesson page.

So what

Whenever work has "this before that" rules, from courses to builds to recipe steps, a topological sort gives an order that keeps every rule, and tells you when the rules contradict each other.

Key terms

Cheat sheets

Related