WOLFRAM NOTEBOOK

WOLFRAM|DEMONSTRATIONS PROJECT

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
uv
,
u
comes before
v
in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges
uv
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.
Wolfram Cloud

You are using a browser not supported by the Wolfram Cloud

Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.


I understand and wish to continue anyway »

You are using a browser not supported by the Wolfram Cloud. Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.