Contents    Page-10    Prev    Next    Page+10    Index   

Topological Sort

Some graphs specify an order in which things must be done; a common example is the course prerequisite structure of a university.

A topological sort orders the vertices of a directed acyclic graph (DAG) so that if there is a path from vertex vi to vj, vj comes after vi in the ordering. A topological sort is not necessarily unique. An example of a topological sort is a sequence of taking classes that is legal according to the prerequisite structure.

An easy way to find a topological sort is: