Topological sort

From Algorithmist

Topological sort is not a sorting algorithm in the sense that we are given a list of comparable items to put in order. It is given the name "sort" because it provides an ordering, albeit of a different type.

Say we have a directed acyclic graph G. Then a topological sort of G is an ordering of its vertices v₁,v₂,...,v_n such that if there is an edge from v_i to v_j, then i is less than j. Note that such an ordering is not necessarily unique.

The algorithm has a complexity of O(V + E).

[edit] Pseudocode

• indegree(v) counts the number of edges leading into vertex v

for i from 1 to N
    select some vertex v with indegree(v) equal to 0
    add v to our topological sort
    remove v and all edges leading from it