Graph Modelling Example: Ordering Courses That Have Prerequisites

Draw an edge from each prerequisite to the course that needs it, and an order exists exactly when the arrows never loop back.

Dependencies form a directed graph, and a topological sort of it, an order in which every edge points forwards, is an order that respects every dependency; when none exists, the dependencies loop. A student plans six courses. Algebra comes before Calculus and before Statistics, Calculus before Physics, and Statistics and Programming before Data Science.

Which courses can the student take first?

Algebra and Programming, the two courses that nothing comes before.

The courses are the vertices, and each prerequisite is an edge with a direction. Pointing it from the prerequisite to the course that needs it makes every arrow point the way the order runs, so a course can be taken once every arrow into it comes from a course already taken.

Six courses, each arrow from a prerequisite to the course that needs it

Kahn's method, from the Topological Sort topic in Algorithms, gives the order: count each course's prerequisites, start with the courses that have none, and each time a course is taken, cross it off the courses it unlocks and add any that now have none left. If the dependencies loop, the courses on the loop never reach zero, so the order comes out with fewer courses than the plan holds. The listing runs it, then adds Data Science as a prerequisite of Statistics.

courses.pypy

from collections import deque

courses = ["Algebra", "Calculus", "Physics", "Statistics", "Data Science", "Programming"]
prerequisites = [
    ("Algebra", "Calculus"), ("Calculus", "Physics"), ("Algebra", "Statistics"),
    ("Statistics", "Data Science"), ("Programming", "Data Science"),
]


def course_order(edges: list[tuple[str, str]]) -> list[str]:
    needs = {course: 0 for course in courses}
    unlocks: dict[str, list[str]] = {course: [] for course in courses}
    for before, after in edges:
        unlocks[before].append(after)
        needs[after] += 1
    ready = deque(course for course in courses if needs[course] == 0)
    order = []
    while ready:
        course = ready.popleft()
        order.append(course)
        for after in unlocks[course]:
            needs[after] -= 1
            if needs[after] == 0:
                ready.append(after)
    return order


print("can be taken first:", ", ".join(c for c in courses if all(after != c for _, after in prerequisites)))
order = course_order(prerequisites)
print(f"order ({len(order)} of {len(courses)}):", ", ".join(order))
looped = course_order(prerequisites + [("Data Science", "Statistics")])
print(f"with Data Science before Statistics ({len(looped)} of {len(courses)}):", ", ".join(looped))
print("left out:", ", ".join(c for c in courses if c not in looped))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

can be taken first: Algebra, Programming
order (6 of 6): Algebra, Programming, Calculus, Statistics, Physics, Data Science
with Data Science before Statistics (4 of 6): Algebra, Programming, Calculus, Physics
left out: Statistics, Data Science

The first order holds all six courses. With the extra prerequisite, Statistics and Data Science each wait for the other, so neither is ever ready, and the order holds 4 of the 6: the missing two are the loop. Which valid order comes out depends on the order the courses are listed, since several are correct. Each course and each prerequisite is handled once, so the sort is O(V + E) for V courses and E prerequisites. Pointing the edges the other way, from a course to what it needs, also works but gives the order backwards.

← → move through sections and cards