graphs.kahns_algorithm_topo
===========================

.. py:module:: graphs.kahns_algorithm_topo


Functions
---------

.. autoapisummary::

   graphs.kahns_algorithm_topo.topological_sort


Module Contents
---------------

.. py:function:: 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)