## [Algorithm 101] Topological Sorting

A directed acyclic graph (DAG) is not only necessary but also sufficient for topological sorting to be possible.

## DFS

Perform a DFS traversal and note the order in which vertices become dead-ends (i.e., popped off the traversal stack). Reversing this order yields a solution to the topological sorting problem, provided, of course, no back edge has been encountered during the traversal. If a back edge has been encountered, the digraph is not a dag, and topological sorting of its vertices is impossible.

(a) Digraph for which the topological sorting problem needs to be solved.

(b) DFS traversal stack with the subscript numbers indicating the poppingoff order.

(c) Solution to the problem.

L ← Empty list that will contain the sorted elements S ← Set of all nodes with no incoming edge while S is non-empty do remove a node n from S add n to tail of L for each node m with an edge e from n to m do remove edge e from the graph if m has no other incoming edges then insert m into S if graph has edges then return error (graph has at least one cycle) else return L (a topologically sorted order)

## BFS

Repeatedly, identify in a remaining digraph a * source*, which is a vertex with no

**incoming**edges, and delete it along with all the edges outgoing from it. (If there are several sources, break the tie arbitrarily. If there are none, stop because the problem cannot be solved.) The order in which the vertices are deleted yields a solution to the topological sorting problem.

L ← Empty list that will contain the sorted nodes while there are unmarked nodes do select an unmarked node n visit(n) function visit(node n) if n has a permanent mark then return if n has a temporary mark then stop (not a DAG) mark n temporarily for each node m with an edge from n to m do visit(m) mark n permanently add n to head of L