Close Menu
    Code and Debug
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook X (Twitter) Instagram YouTube WhatsApp
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook Instagram YouTube LinkedIn WhatsApp
    Code and Debug – BlogCode and Debug – Blog
    Code and Debug – BlogCode and Debug – Blog
    Home»Data Structures & Algorithms»Topological Sort (Kahn’s Algorithm) – Simple BFS Solution in Python
    Data Structures & Algorithms

    Topological Sort (Kahn’s Algorithm) – Simple BFS Solution in Python

    codeanddebugBy codeanddebug4 June 2025Updated:4 June 2025No Comments3 Mins Read
    Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
    Featured Image of a question to how to generate a topo sort in a directed graph using kahn's algorithm
    Share
    Facebook Twitter LinkedIn Pinterest Email

    Learn how to perform topological sorting of a DAG using Kahn’s algorithm (BFS based). Clear steps, commented Python code, dry-run example, and Big-O complexity.

    Here’s the [Problem Link] to begin with.

    Contents:
     [show]
    • What does the problem ask?
    • Example
    • Intuition & Approach
    • Code
    • Code walkthrough
    • Dry run on the sample graph
    • Complexity
    • Conclusion

    What does the problem ask?

    Given a directed acyclic graph (DAG) with V vertices (0 … V-1) and a list of directed edges, return any order of the vertices such that for every edge u → v, vertex u appears before v in the list.


    Example

    V = 6
    Edges = [
      (5, 0), (5, 2),
      (4, 0), (4, 1),
      (2, 3), (3, 1)
    ]

    A correct topological order is 5 4 2 3 1 0.
    (Other valid orders are possible.)


    Intuition & Approach

    Kahn’s algorithm (BFS idea)

    1. Indegree
      For every vertex count how many incoming edges it has.
      Vertices with indegree 0 have no prerequisites; they can start the order.
    2. Queue of ready vertices
      Put all indegree-0 vertices in a queue.
    3. Process the queue
      • Pop a vertex, add it to the answer list.
      • For each outgoing edge u → v, reduce v’s indegree by 1.
      • If v’s indegree becomes 0, push v into the queue.
    4. Repeat until the queue is empty.
      If we output V vertices, we have a valid topological order.
      (If fewer—this would mean the graph had a cycle, but the problem guarantees a DAG.)

    Code

    from collections import deque
    
    
    class Solution:
        def topoSort(self, V, edges):
            adj_list = [[] for _ in range(V)]   # adjacency list
            indegrees = [0 for _ in range(V)]   # incoming edge counts
    
            # build graph and indegree array
            for u, v in edges:                  # edge u → v
                adj_list[u].append(v)
                indegrees[v] += 1
    
            queue = deque()                     # vertices ready to be processed
            result = []                         # final topological order
    
            # add all starting points (indegree == 0)
            for i in range(V):
                if indegrees[i] == 0:
                    queue.append(i)
    
            # BFS over the DAG
            while queue:
                current_node = queue.popleft()
                result.append(current_node)
    
                # remove current_node’s edges
                for adjNode in adj_list[current_node]:
                    indegrees[adjNode] -= 1
                    if indegrees[adjNode] == 0:  # new node becomes ready
                        queue.append(adjNode)
    
            return result                       # contains V vertices in order

    Code walkthrough

    1. Build
      • adj_list[u] holds all vertices reachable from u.
      • indegrees[v] counts how many edges come into v.
    2. Initial queue
      All vertices with no incoming edges can be placed first in the order.
    3. Loop
      • Take the next ready vertex.
      • Add it to result.
      • “Delete” its outgoing edges by lowering each neighbor’s indegree.
      • When a neighbor’s indegree hits 0, push it onto the queue.
    4. Finish
      When the queue is empty, result has one valid topological order.

    Dry run on the sample graph

    StepQueueResultindegrees (key changes)
    Start[4, 5][]4→0,5→0
    Pop 4[5][4]0→1,1→1
    Process edges 4→0, 4→1[5] (no new zeros)
    Pop 5[][4,5]0→0,2→1
    Edge 5→0 lowers indegree(0) to 0 → queue [0]
    Edge 5→2 lowers indegree(2) to 0 → queue [0,2]
    Pop 0[2][4,5,0](0 has no children)
    Pop 2[][4,5,0,2]3→0 → queue [3]
    Pop 3[][4,5,0,2,3]1→0 → queue [1]
    Pop 1[][4,5,0,2,3,1]done

    Final order: 4 5 0 2 3 1 —valid.


    Complexity

    MeasureValue
    TimeO(V + E)
    SpaceO(V + E)

    We look at each vertex and each edge once. We store the adjacency list (E) and two arrays of size V.


    Conclusion

    Kahn’s algorithm uses a simple queue and indegree counts to produce a topological order with breadth-first style processing. It is intuitive, runs in linear time, and is often the first choice for scheduling tasks with dependencies.

    Join our FREE Advance DSA COURSE

    For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.

    BFS Graph Medium
    Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
    Previous ArticleDetect Cycle in a Directed Graph
    Next Article Detect Cycle in a Directed Graph – Kahn’s Algorithm (BFS Topological Check) in Python
    codeanddebug
    • Website

    Related Posts

    Data Structures & Algorithms

    Detect Cycle in a Directed Graph – Kahn’s Algorithm (BFS Topological Check) in Python

    4 June 2025
    Data Structures & Algorithms

    Detect Cycle in a Directed Graph

    3 June 2025
    Data Structures & Algorithms

    Topological Sort in Graph | Simple DFS + Stack Solution in Python

    3 June 2025
    Add A Comment
    Leave A Reply Cancel Reply

    Categories
    • Data Structures & Algorithms (38)
      • Beginner (17)
      • Expert (7)
      • Intermediate (14)
    • Uncategorised (1)
    Recent Posts

    Detect Cycle in a Directed Graph – Kahn’s Algorithm (BFS Topological Check) in Python

    4 June 2025

    Topological Sort (Kahn’s Algorithm) – Simple BFS Solution in Python

    4 June 2025

    Detect Cycle in a Directed Graph

    3 June 2025

    Topological Sort in Graph | Simple DFS + Stack Solution in Python

    3 June 2025

    Is Graph Bipartite? | Leetcode 785 | Easy 2-Color DFS Solution in Python

    1 June 2025
    Facebook Instagram YouTube LinkedIn WhatsApp
    © 2025 Code and Debug. All rights reserved.

    Type above and press Enter to search. Press Esc to cancel.