10217

# Topological Sort in DAGs

A topological sort (or topological ordering) of a directed graph is a linear ordering of its vertices such that for every edge , comes before in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another . 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.

### PERMANENT CITATION

 Share: Embed Interactive Demonstration New! Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details » Download Demonstration as CDF » Download Author Code »(preview ») Files require Wolfram CDF Player or Mathematica.

#### Related Topics

 RELATED RESOURCES
 The #1 tool for creating Demonstrations and anything technical. Explore anything with the first computational knowledge engine. The web's most extensive mathematics resource. An app for every course—right in the palm of your hand. Read our views on math,science, and technology. The format that makes Demonstrations (and any information) easy to share and interact with. Programs & resources for educators, schools & students. Join the initiative for modernizing math education. Walk through homework problems one step at a time, with hints to help along the way. Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet. Knowledge-based programming for everyone.