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:
There are numCourses courses, labeled to . 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
-
numCourses - Each pair
[a, b]hasnumCoursesand - At most
numCourses(numCourses) 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 , 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 , , and .
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.
The graph has one other topological order, 0, 1, 2, 3. The list 0, 1, 3, 2 is not one, because the edge 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 arrangements, but the number grows too fast for this to work. Twenty courses have
which would take about 770 years to try at roughly steps a second, and the problem allows 2000 courses. We have to build the order directly.
Kahn's algorithm
To build an order directly, we start with the question of which vertex can go first. The first vertex of a topological order cannot have an edge coming into it, because that edge would start at a later vertex. The number of edges that end at a vertex is its indegree, so the first vertex must have indegree 0. In our graph that is course 0.
Once course 0 is in the order, its edges and are taken care of. They start at a vertex that is already placed, so they will point right wherever courses 1 and 2 end up, and we can ignore them from now on. Without them, courses 1 and 2 have no incoming edges left, and either one can go next. Kahn's algorithm repeats this step until every vertex is placed:
- Count the indegree of every vertex.
- Put every vertex with indegree 0 into a queue.
- Take a vertex out of the queue and add it to the end of the order.
- For each edge , subtract 1 from the count of . If the count becomes 0, put into the queue.
- Repeat steps 3 and 4 until the queue is empty.
Step 4 does not delete anything from the graph. Subtracting 1 from a count is how we ignore an edge. At every moment the count of a vertex is the number of edges into it from vertices that are not in the order yet, and a vertex enters the queue when that number reaches 0. So when a vertex is taken, every vertex with an edge into it is already in the order, and that is what makes the result a topological order.
The algorithm on the four courses
On the four courses the algorithm runs as follows. Each row shows the counts, the queue and the order after one more vertex has been taken:
| Vertex taken | Counts of 0, 1, 2, 3 | Queue | Order |
|---|---|---|---|
| none yet | 0, 1, 1, 2 | 0 | empty |
| 0 | 0, 0, 0, 2 | 1, 2 | 0 |
| 1 | 0, 0, 0, 1 | 2 | 0, 1 |
| 2 | 0, 0, 0, 0 | 3 | 0, 1, 2 |
| 3 | 0, 0, 0, 0 | empty | 0, 1, 2, 3 |
Course 3 has two incoming edges. It enters the queue only when the second of them has been subtracted, after course 2 is taken. The result, 0, 1, 2, 3, is not the order shown on the card, and it does not need to be, since the problem accepts any valid order.
Worked example
Step through Kahn's algorithm
The trace runs the same steps one at a time. It has two more inputs: three courses with no prerequisites, which are all in the queue from the start, and three courses in which courses 1 and 2 need each other.
A vertex with zero incoming edges has no unfinished prerequisite. Begin with every such vertex.
Change the example input
Current result: [0,1,2,3]
Kahn's algorithm in code
The function below solves Course Schedule II. Its first loop builds the adjacency lists and counts the indegrees in one pass over the pairs, and its while loop is steps 3 to 5.
def find_order(num_courses, prerequisites):
graph = [[] for _ in range(num_courses)]
indegree = [0] * num_courses
for course, before in prerequisites:
graph[before].append(course) # the edge before -> course
indegree[course] += 1
ready = deque(v for v in range(num_courses) if indegree[v] == 0)
order = []
while ready:
u = ready.popleft()
order.append(u)
for v in graph[u]:
indegree[v] -= 1
if indegree[v] == 0:
ready.append(v)
return order if len(order) == num_courses else []
print(find_order(2, [[1, 0]]))
print(find_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]]))
print(find_order(1, []))
print(find_order(2, [[1, 0], [0, 1]]))The last four lines run the three samples and then two courses that need each other.
The first loop is where each pair is turned around. The pair [a, b] says that comes first, so goes into the adjacency list of , and it is the indegree of that goes up.
The queue is a deque, whose popleft takes constant time. Calling pop(0) on a list would move every remaining element one place to the left. If all 2000 courses were in the queue at once, that would be about two million moves.
The last step compares the length of the order with the number of courses and returns an empty list when the order is too short. The fourth call is an example: for two courses that need each other, the function returns []. The next part explains why the order can come out short.
When the order comes out short
Kahn's algorithm can stop before all the vertices are placed. Suppose two courses need each other, as in the pairs [[1, 0], [0, 1]]. Both have indegree 1, so the queue is empty from the start and the order stays empty. Something similar happens whenever some vertices wait for each other in a circle, which is called a cycle: none of them is ever taken.
To see why, suppose some vertex of the cycle were taken, and call the first of them to be taken . The vertex before on the cycle has an edge into and had not been taken yet, so the count of was still above 0 and could not have been in the queue. So in a graph with a cycle, the order comes out shorter than the number of vertices.
The opposite also holds: in a graph without a cycle the algorithm places every vertex. The Cycle detection page gives the argument. So the length of the order tells us which kind of graph we have, and that is all the next problem asks:
The input is the same as in Course Schedule II. Return true if every course can be taken, and false otherwise.
Constraints
-
numCourses - At most 5000 pairs, all different
Sample 1 · Input
numCourses = 2, prerequisites = [[1,0]]
Output
true
Sample 2 · Input
numCourses = 2, prerequisites = [[1,0],[0,1]]
Output
false
The solution is find_order with a different last line, which returns whether the length of the order equals numCourses. In the second sample the order is empty, so the answer is false.
Choosing among the vertices in the queue
When the queue holds more than one vertex, any of them could be taken next, and every choice leads to a valid order. In the table above, the queue held courses 1 and 2 after course 0 was taken. Taking course 2 first gives 0, 2, 1, 3, the order on the card. The algorithm stays correct with any container in place of the queue, because all that step 3 needs is some vertex whose count is 0.
This freedom is useful when a problem asks for one particular order. A problem can ask, for example, for the smallest order in dictionary order: of all the topological orders, the one with the smallest first vertex, among those the one with the smallest second vertex, and so on. A topological order can only begin with a vertex whose count is 0, so the smallest order begins with the smallest of those, and the same reasoning applies at every later step. Taking the smallest vertex in the queue each time therefore produces the smallest order, and a min-heap finds that vertex in time.
In find_order, ready becomes a plain list that is turned into a heap once with heapq.heapify(ready). After that, heapq.heappop(ready) and heapq.heappush(ready, v) take the place of popleft and append.
For example, take four vertices and the two edges and . With the queue the algorithm outputs 1, 3, 2, 0. With the heap it outputs 1, 2, 3, 0, which is the smallest of the six topological orders of this graph.
Compute a value for every vertex in topological order
Often the order itself is not the answer to a problem. What the problem asks for is a value at every vertex, where the value of a vertex depends on the values of the vertices that have edges into it. A topological order is the right order for such a calculation, because each vertex comes after every vertex its value depends on. The order does not even have to be stored, because the calculation can run inside Kahn's algorithm while it takes the vertices one by one. The next problem is a calculation of that kind:
A game has levels and one-way teleporters; a teleporter goes from level to level . No sequence of teleporters leads back to a level already visited. Count the routes from level 1 to level , modulo .
The first input line holds and , and each of the next lines holds one teleporter .
Constraints
Sample · Input
4 5 1 2 2 4 1 3 3 4 1 4
Output
3
In the sample there are three routes: 1, 2, 4 and 1, 3, 4 and 1, 4. The levels and teleporters form a directed graph, and the statement says that it has no cycle. We cannot count the routes by listing them, because there can be too many. Levels 1 to 4 of the sample, without the teleporter that goes straight from 1 to 4, give two routes from level 1 to level 4. Thirty such groups in a row, each starting at the level where the one before it ends, have 91 levels and routes, which is more than a billion, and the problem allows levels.
To count without listing, let ways[v] be the number of routes from level 1 to level . There is one route from level 1 to itself, the one that uses no teleporter, so ways[1] is 1. A route to any other level ends with one last teleporter , and the part before that teleporter is a route from level 1 to . There are ways[u] of those, so
In words, the count of a level is the sum of the counts of the levels that have a teleporter into it. In the sample, levels 2 and 3 can only be entered from level 1, and level 4 can be entered from levels 2, 3 and 1:
ways[4] = ways[2] + ways[3] + ways[1], which is .The sum for is correct only if every ways[u] in it is already final. A topological order guarantees that, because every level with a teleporter into comes before . There is one obstacle: the sum runs over the teleporters into a level, and the adjacency lists hold the teleporters out of a level. So the program works in the other direction. When Kahn's algorithm takes a level out of the queue, it adds ways[u] to ways[v] for each teleporter . By the time is taken, every teleporter into it has made its addition.
MOD = 10**9 + 7
def game_routes(n, teleporters):
graph = [[] for _ in range(n + 1)] # levels are numbered from 1
indegree = [0] * (n + 1)
for a, b in teleporters:
graph[a].append(b)
indegree[b] += 1
ways = [0] * (n + 1)
ways[1] = 1
ready = deque(v for v in range(1, n + 1) if indegree[v] == 0)
while ready:
u = ready.popleft()
for v in graph[u]:
ways[v] = (ways[v] + ways[u]) % MOD
indegree[v] -= 1
if indegree[v] == 0:
ready.append(v)
return ways[n]
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
teleporters = [(int(data[2 + 2 * i]), int(data[3 + 2 * i])) for i in range(m)]
print(game_routes(n, teleporters))On the sample input the program prints 3.
Compared with Kahn's algorithm for the courses, the loop over the edges has one new line, the addition into ways[v]. Levels that cannot be reached from level 1 go through the queue like any other level. Their ways value stays 0, so their additions change nothing.
Other values can be computed in the same loop with a different operation in place of the sum. To find the largest number of levels on a route from level 1, for example, a level takes one more than the largest value among the levels with a teleporter into it, in place of their sum, and the levels that cannot be reached from level 1 have to be kept out of the calculation. The DP on DAGs page of the DP fundamentals lesson works that problem out.
Cost of Kahn's algorithm
- With a queue
time - Each vertex enters and leaves the queue once, and each edge is subtracted once. Course Schedule II allows 2000 courses and about pairs, so about four million steps.
- With a min-heap
time - Each vertex is pushed and popped once, at steps each.
- Game Routes
time - One addition per teleporter, at most of them.
- Memory
- The adjacency lists hold every edge once. The counts, the queue and the order hold one entry per vertex.
Common mistakes in topological sorting
Building the edge the wrong way round from a
[course, prerequisite]pair.- Where it breaks
- Course Schedule II with
numCourses = 2, prerequisites = [[1, 0]]returns[1, 0], which takes course 1 before its prerequisite. The answer is[0, 1]. - The fix
- Turn each pair
[a, b]into the edge .
Returning the order without comparing its length with the number of vertices.
- Where it breaks
- For three vertices with the edges , and , Kahn's algorithm places vertex 0 and stops. Returning
[0]is wrong; the answer is[]. - The fix
- Return the order only if it holds every vertex.
Adding the route counts in the order of the input.
- Where it breaks
- With three levels and the teleporters
2 3and1 2, in that order, the teleporter2 3addsways[2]toways[3]whileways[2]is still 0. The program prints 0, and the answer is 1. - The fix
- Add
ways[u]to the levels after only when Kahn's algorithm takes out of the queue.
Recall Run Kahn's algorithm by hand on five vertices with the edges $0 \to 2$, $1 \to 2$, $2 \to 3$ and $2 \to 4$. What does it output, and how many topological orders does the graph have?
The indegrees are 0, 0, 2, 1 and 1, so the queue starts with 0 and 1. Taking 0 lowers the count of vertex 2 to 1, and taking 1 lowers it to 0. Then 2 is taken, which puts 3 and 4 into the queue. The output is 0, 1, 2, 3, 4.
There are four topological orders. Vertices 0 and 1 can go in either order, vertex 2 must be third, and vertices 3 and 4 can go in either order, which gives .