A topological ordering, or a topological sort, orders the vertices in a directed acyclic graph on a line, i.e. in a list, such that all directed edges go from left to right. Such an ordering cannot exist if the graph contains a directed cycle because there is no way that you can keep going right on a line and still return back to where you started from.

Formally, in a graph `G = (V, E)`

, then a linear ordering of all its
vertices is such that if `G`

contains an edge `(u, v) ∈ E`

from vertex `u`

to vertex `v`

then `u`

precedes `v`

in the ordering.

It is important to note that each DAG has *at least one*
topological sort.

There are known algorithms for constructing a topological ordering of any DAG in linear time, one example is:

- Call
`depth_first_search(G)`

to compute finishing times`v.f`

for each vertex`v`

- As each vertex is finished, insert it into the front of a linked list
- the linked list of vertices, as it is now sorted.

A topological sort can be performed in `ϴ(V + E)`

time, since the
depth-first search algorithm takes `ϴ(V + E)`

time and it takes `Ω(1)`

(constant time) to insert each of `|V|`

vertices into the front of
a linked list.

Many applications use directed acyclic graphs to indicate precedences among events. We use topological sorting so that we get an ordering to process each vertex before any of its successors.

Vertices in a graph may represent tasks to be performed and the edges
may represent constraints that one task must be performed before
another; a topological ordering is a valid sequence to perform the
tasks set of tasks described in `V`

.

Let a vertice `v`

describe a `Task(hours_to_complete: int)`

, i. e. `Task(4)`

describes a `Task`

that takes `4`

hours to complete, and an edge `e`

describe a `Cooldown(hours: int)`

such that `Cooldown(3)`

describes a duration of time to cool down after a completed task.

Let our graph be called `dag`

(since it is a directed acyclic graph), and let it contain 5 vertices:

```
A <- dag.add_vertex(Task(4));
B <- dag.add_vertex(Task(5));
C <- dag.add_vertex(Task(3));
D <- dag.add_vertex(Task(2));
E <- dag.add_vertex(Task(7));
```

where we connect the vertices with directed edges such that the graph is acyclic,

```
// A ---> C ----+
// | | |
// v v v
// B ---> D --> E
dag.add_edge(A, B, Cooldown(2));
dag.add_edge(A, C, Cooldown(2));
dag.add_edge(B, D, Cooldown(1));
dag.add_edge(C, D, Cooldown(1));
dag.add_edge(C, E, Cooldown(1));
dag.add_edge(D, E, Cooldown(3));
```

then there are three possible topological orderings between `A`

and `E`

,

`A -> B -> D -> E`

`A -> C -> D -> E`

`A -> C -> E`

This modified text is an extract of the original Stack Overflow Documentation created by following contributors and released under CC BY-SA 3.0

This website is not affiliated with Stack Overflow