Graphs 0/61

Topological sort: ordering directed graphs · 2 of 3

Topological sort

Build a topological order with Kahn's algorithm, tell from its length whether one exists, choose among several valid orders, and compute values such as route counts in that order.

2,742 words · 13 min read

Part 1 of 7 Topological order

An order that respects every edge

When some tasks have to be finished before others, we may want a list of all the tasks in an order in which they can be carried out one after another. Putting the vertices of a directed graph into such an order is called topological sorting. Courses with prerequisites are one example:

Difficulty tier:Normal

There are numCourses courses, labeled 00 to numCourses−1\text{numCourses} - 1. Each pair [a, b] in prerequisites says that course b must be taken before course a.

Return an order that takes every course after all of its prerequisites. Any valid order is accepted. If no order works, return an empty list.

Constraints

  • 1≤1 \le numCourses ≤2000\le 2000
  • Each pair [a, b] has 0≤a,b<0 \le a, b < numCourses and a≠ba \ne b
  • At most numCourses ⋅\cdot (numCourses −1- 1) pairs, all different

Sample 1 · Input

numCourses = 2, prerequisites = [[1,0]]

Output

[0,1]

Sample 2 · Input

numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

Output

[0,2,1,3]

Sample 3 · Input

numCourses = 1, prerequisites = []

Output

[0]

In the second sample, courses 1 and 2 each need course 0, and course 3 needs both 1 and 2. We draw a pair [a, b] as an edge b→ab \to a, from the course that is taken first to the course that needs it. The pair names the two courses the other way round, so each pair has to be turned around when we build the graph. The four pairs give the edges 0→10 \to 1, 0→20 \to 2, 1→31 \to 3 and 2→32 \to 3.

A topological order of a directed graph is a list of all its vertices in which every edge goes from an earlier vertex to a later one. If we write the vertices in a row in that order, every edge points to the right.

Top: the four courses in the order 0, 2, 1, 3, the output shown on the card. Bottom: with an edge 3→03 \to 0 added, one edge among courses 0, 1 and 3 points left. Course 2 is left out of the lower drawing.

The graph has one other topological order, 0, 1, 2, 3. The list 0, 1, 3, 2 is not one, because the edge 2→32 \to 3 would point left.

The lower half of the figure adds a rule that course 3 must be taken before course 0. Courses 0, 1 and 3 now wait for each other in a circle. Whichever of them is written first has an edge coming into it from one that is written later, so no topological order exists. For input like this the problem wants an empty list.

We could look for an order by trying every arrangement of the courses and checking each one against the rules. Four courses have 4!=244! = 24 arrangements, but the number grows too fast for this to work. Twenty courses have

20!≈2.4×1018 arrangements,20! \approx 2.4 \times 10^{18} \text{ arrangements,}

which would take about 770 years to try at roughly 10810^8 steps a second, and the problem allows 2000 courses. We have to build the order directly.