Topological Sort Explained with Course Prerequisites

By Hourly DSA · September 27, 2026 · 4 min read

Topological sorting orders the vertices of a directed graph so every prerequisite appears before the item that depends on it. A complete ordering exists exactly when the graph has no directed cycle. Such a graph is called a directed acyclic graph, or DAG.

Course prerequisites make the idea concrete, but the same reasoning applies to build dependencies and tasks that must happen in a particular order.

Choose one meaning for each directed edge

Let A → C mean that you must complete A before C. Consider four courses with these requirements:

A → C
B → C
C → D

C needs both A and B. D needs C. One valid order is A, B, C, D; another is B, A, C, D.

There is no rule between A and B, so either can come first. A topological ordering does not need to be unique.

If a problem gives pairs in the form “course, prerequisite,” take care when constructing edges. Under our convention, each edge goes from the prerequisite to the course. Reversing every edge would answer the reverse ordering question.

Count prerequisites with indegrees

A vertex's indegree is the number of edges entering it. In this graph:

Course	Initial indegree	Meaning
A	0	No prerequisites
B	0	No prerequisites
C	2	Waits for A and B
D	1	Waits for C

Kahn's algorithm begins with all zero-indegree vertices in a queue. Here, A and B are ready.

When you remove a course from the queue, append it to the ordering. Then remove its contribution to each dependent course's indegree. A dependent becomes ready when its indegree reaches zero.

You can treat these updated indegrees as the number of prerequisites that remain unfinished.

Walk through the queue

Start with queue [A, B] and an empty output.

Remove A. Output is [A]. C's indegree falls from 2 to 1, so C is still waiting.
Remove B. Output is [A, B]. C's indegree becomes zero, so enqueue C.
Remove C. Output is [A, B, C]. D's indegree becomes zero, so enqueue D.
Remove D. Output is [A, B, C, D]. All courses are included.

Enqueuing C after only A would be a bug: one of C's prerequisites is still unfinished. Reaching zero, rather than merely reducing the count, is the event that makes a course ready.

Include isolated vertices too. A course with no incoming or outgoing edges belongs in the result even though it never appears in a dependency pair.

How does this detect a cycle?

Add a new edge D → B. Now B waits for D, D waits for C, and C waits for B as well as A.

You can still process A. After that, the queue becomes empty while B, C, and D remain unfinished. No remaining vertex has indegree zero.

The check is whether the output contains all V vertices. If fewer than V were processed, a directed cycle prevents a complete topological ordering.

Some blocked vertices can sit downstream of a cycle without belonging to it. The algorithm detects that a cycle exists; the unfinished set is not necessarily an exact list of cycle members.

Princeton's directed graph chapter explains topological order and its connection to cycle detection, including a DFS-based approach.

How is this different from ordinary BFS?

Both can use a queue, but their readiness rules differ. In ordinary BFS, discovering an unvisited neighbor is enough to enqueue it. In Kahn's algorithm, a vertex must wait for all incoming dependencies to be removed.

The result is an order that respects prerequisites. It does not measure the shortest distance from a starting vertex.

If queue behavior is unfamiliar, start with stack vs. queue. For the traversal comparison, see BFS vs. DFS.

What is the complexity?

With adjacency lists, building indegrees examines each edge once. The main loop processes each vertex once and each outgoing edge once, giving O(V + E) time.

The adjacency lists take O(V + E) storage. Indegrees, the queue, and the output take O(V) additional space. These bounds assume constant-time queue operations.

If you need the smallest available course number at every step, use a min-heap instead of a FIFO queue. That tie-breaking requirement changes the bound to O(E + V log V), since vertices enter and leave the heap at most once.

Test one dependency change

Suppose A and B both point to C. Can the order be A, C, B?

No. It satisfies A's prerequisite edge but violates B → C. Both incoming requirements must be respected.

Practice checking every edge against a proposed order. Hourly DSA supports short reasoning sessions, and a four-course graph gives you enough structure to test the idea without a large implementation.