Back

Table of contents

Next

Topological sort

    This section shows how depth-first search can be used to perform topological sorts of directed acyclic graphs, or "dags" as they are sometimes called. A topological sort of a dag G =(V,E) is a linear ordering of all its vertices such that if G contains an edge (u,v), then u appears before v in the ordering. A topological sort of a graph can be viewed as an ordering of its vertices along a horizontal line so that all directed edges go from left to right.

    The following simple algorithm topologically sorts a dag.
 

TOPOLOGICAL-SORT(G)

   1   call DFS(G) to compute finishing times f[v] for each vertex v
   2   as each vertex is finished, insert it onto tha front of a linked list
   3   return the linked list of vertices
 

    We can perform a topological sort in time theta(V+E), since depth-first search takes theta(V+E) time and takes O(1) time to insert each of the |V| vertices on to the front of the linked list.