Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Topological Sort

 

A topological sort is an ordering of the vertices of a directed acyclic graph given by the following definition:

Definition (Topological Sort) Consider a directed acyclic graph tex2html_wrap_inline71355. A topological sort   of the vertices of G is a sequence tex2html_wrap_inline72047 in which each element of tex2html_wrap_inline71357 appears exactly once. For every pair of distinct vertices tex2html_wrap_inline71521 and tex2html_wrap_inline72053 in the sequence S, if tex2html_wrap_inline71669 is an edge in G, i.e., tex2html_wrap_inline72061, then i<j.

Informally, a topological sort is a list of the vertices of a DAG in which all the successors of any given vertex appear in the sequence after that vertex. Consider the directed acyclic graph tex2html_wrap_inline72065 shown in Figure gif. The sequence tex2html_wrap_inline72067 is a topological sort of the vertices of tex2html_wrap_inline72065. To see that this is so, consider the set of vertices:

displaymath72041

The vertices in each edge are in alphabetical order, and so is the sequence S.

   figure50567
Figure: A Directed Acyclic Graph

It should also be evident from Figure gif that a topological sort is not unique. For example, the following are also valid topological sorts of the graph tex2html_wrap_inline72065:

eqnarray50796

One way to find a topological sort is to consider the in-degrees  of the vertices. (The number above a vertex in Figure gif is the in-degree of that vertex). Clearly the first vertex in a topological sort must have in-degree zero and every DAG must contain at least one vertex with in-degree zero. A simple algorithm to create the sort goes like this:

Repeat the following steps until the graph is empty:

  1. Select a vertex that has in-degree zero.
  2. Add the vertex to the sort.
  3. Delete the vertex and all the edges emanating from it from the graph.



next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.