Graph/topological_sort library

⛓️ Topological Sort (Kahn's Algorithm)

Produces a linear ordering of vertices of a Directed Acyclic Graph (DAG) such that for every directed edge u -> v, u comes before v in the ordering. Throws StateError if the graph contains a cycle.

  • Time complexity: O(V + E)
  • Space complexity: O(V)

Example:

final dag = {
  1: [2], 2: [3], 3: [4], 4: []
};
final order = topologicalSort(dag); // [1, 2, 3, 4]

Functions

topologicalSort<T>(Map<T, List<T>> graph) → List<T>