Topological sorting
In combinatorics, topologically sorting a directed acyclic graph (DAG) means finding a linear ordering of the nodes so that any node x in the linear order comes before any other node y, if there's a path through the DAG leading from x to y.
The usual algorithm for topological sorting has running time linear in the number of nodes plus the number of edges. It works by depth first search. First, find a list of "start nodes" which have no incoming edges. Put them into a queue Q. Then,
while Q is nonempty:
remove a node n from Q
output n to the linear order
for each node m with an edge e from n to m:
remove edge e from the graph
if m has no other incoming edges, insert m into Q
If this algorithm terminates without outputting all the nodes from the graph, it means the graph has at least one cycle and is not a DAG, so the algorithm can report an error.
This article is a stub. You can help BambooWeb by .
