How do you produce a topological sort of a directed acyclic graph?
You use Kahn's algorithm. You find the nodes that have nothing coming into them, and you take them out one at a time, and each time you take one out you reduce the count of the nodes that depend on it.
from collections import deque
def topological_sort(graph):
indegree = {node: 0 for node in graph}
for neighbours in graph.values():
for neighbour in neighbours:
indegree[neighbour] += 1
queue = deque([node for node in graph if indegree[node] == 0])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbour in graph[node]:
indegree[neighbour] -= 1
if indegree[neighbour] == 0:
queue.append(neighbour)
return order
So what does a topological sort give you? It gives you an order for the nodes so that every node comes after all the nodes it depends on. That is the whole idea.
the dependencies the order
maths before maths, science, history, english
english, science because english and science need maths
history needs maths
And how does the algorithm work? The indegree of a node is the number of edges that come into it. A node with an indegree of zero depends on nothing, so it can go first. You put all of those in the queue. Then each time you take a node out you reduce the indegree of each node that depends on it, and when one of those reaches zero you add it to the queue.
And the complexity is O of n plus m for the time, because every node goes into the queue once and every edge is looked at once. And the space is O of n for the indegree dictionary and the queue.
So the rule to remember is this. The nodes with an indegree of zero go first, and each removal makes more nodes ready.
The next two questions in this topic show the cycle detection and a simple example.