Topological Sort in DAGs

number of vertices

8

random DAG


{7,6,3,2,8,5,1,4}

A topological sort (or topological ordering) of a directed graph is a linear ordering of its vertices such that for every edge

uv

,

u

comes before

v

in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges

uv

may represent constraints that one task

u

must be performed before another

v

. In this application, a topological ordering is just a valid sequence of tasks. A topological ordering is possible only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time. This Demonstration shows random DAGs with a prescribed number of vertices along with one topological sort and two matrices. The matrix on the left represents the adjacency matrix of the graph. In the first graph, vertices 2, 3, and 5 have no out vertices; for that reason their rows are empty. The matrix on the right shows the adjacency matrix corresponding to a relabeling of the vertices following the topological sort; this matrix is upper triangular.