graphs.kahns_algorithm_topo

Functions

topological_sort(→ list[int] | None)

Perform topological sorting of a Directed Acyclic Graph (DAG)

Module Contents

graphs.kahns_algorithm_topo.topological_sort(graph: dict[int, list[int]]) → list[int] | None

Perform topological sorting of a Directed Acyclic Graph (DAG) using Kahn’s Algorithm via Breadth-First Search (BFS).

Topological sorting is a linear ordering of vertices in a graph such that for every directed edge u → v, vertex u comes before vertex v in the ordering.

Parameters: graph: Adjacency list representing the directed graph where keys are

vertices, and values are lists of adjacent vertices.

Returns: The topologically sorted order of vertices if the graph is a DAG. Returns None if the graph contains a cycle.

Example: >>> graph = {0: [1, 2], 1: [3], 2: [3], 3: [4, 5], 4: [], 5: []} >>> topological_sort(graph) [0, 1, 2, 3, 4, 5]

>>> graph_with_cycle = {0: [1], 1: [2], 2: [0]}
>>> topological_sort(graph_with_cycle)