AlgoScope

Directed Acyclic Graph

A directed graph with no cycles, which is exactly when a topological order exists.

Data structures, data structure, intermediateAlso called DAG
The order is 0, 1, 2, 3, 5, 4.011223344655
The order is 0, 1, 2, 3, 5, 4.011223344655

Topological Sort: Kahn's algorithm

Result, step 8 of 8

Topological order: 0, 1, 2, 3, 5, 4. Every edge now points from an earlier position to a later one. Each vertex was placed once and each edge lowered one count: O(V + E).

Cost

Topological sort
O(V + E)
Space
O(V + E)

Leads to

Topics that need this one first.

Taught by the same lesson

Topological Sort covers these too, in the same run.