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 in Graph | Simple DFS + Stack Solution in Python
    Data Structures & Algorithms

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

    codeanddebugBy codeanddebug3 June 2025No Comments3 Mins Read
    Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
    Featured Image of a question of topological sort
    Share
    Facebook Twitter LinkedIn Pinterest Email

    Learn how to find a topological sort of a directed acyclic graph (DAG) using depth-first search (DFS) and a stack. Clear intuition, step-by-step guide, commented Python code, dry run, and Big-O analysis.

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

    Contents:
    • What does the problem ask?
    • Example
    • Intuition & Approach
    • Code (original lines kept, only comments added)
    • Code explanation (step-by-step)
    • Dry run on the sample graph
    • Complexity
    • Conclusion

    What does the problem ask?

    You are given a directed acyclic graph (DAG) with V vertices (numbered 0…V-1) and a list of directed edges.
    Your task is to return any valid topological ordering of the vertices, an ordering where every edge u → v appears with u before v.


    Example

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

    One correct topological order is
    5 4 2 3 1 0

    Other valid orders exist; any that respect all edge directions is accepted.


    Intuition & Approach

    1. DFS explores forward edges.
      When DFS finishes exploring a node, all its outgoing neighbors are already placed somewhere before we push that node onto a stack.
    2. Stack collects finished nodes.
      After we visit every node reachable from the start, we push the start node onto the stack.
    3. Reverse the stack.
      If we pop elements (or simply reverse the stack list) we get a sequence where every parent appears before its children, exactly what we need.
    4. Handle every component.
      The graph can have more than one disconnected part, so we start DFS from every unvisited vertex.

    Code (original lines kept, only comments added)

    class Solution:
        # DFS helper: visit node, then its children, then push node to stack
        def dfs(self, current_node, visited, stack, adj_list):
            visited[current_node] = 1                # mark as visited
            for adjNode in adj_list[current_node]:   # explore all outgoing edges
                if visited[adjNode] == 0:
                    self.dfs(adjNode, visited, stack, adj_list)
            stack.append(current_node)               # post-order push
    
        def topoSort(self, V, edges):
            adj_list = [[] for _ in range(V)]        # build adjacency list
            for u, v in edges:                       # edge u → v
                adj_list[u].append(v)
    
            stack = []
            visited = [0 for _ in range(V)]          # 0 = not visited
            for i in range(0, V):                    # check every vertex
                if visited[i] == 0:
                    self.dfs(i, visited, stack, adj_list)
    
            return stack[::-1]                       # reverse = topo order

    Code explanation (step-by-step)

    1. Adjacency list – converts edge pairs into lists for quick lookup.
    2. visited array – keeps us from visiting a node twice.
    3. Outer loop – starts DFS from any node still unvisited (covers all components).
    4. Inside dfs()
      • Mark node visited.
      • Recursively visit each neighbor.
      • After children are done, push the node onto stack.
    5. Return reversed stack for the final topological order.

    Dry run on the sample graph

    Actionstack (bottom → top)visited
    Start DFS at 0? No, unreachable yet[]…
    Start DFS at 1? reachable later
    Start at 2? No, will hit via 5
    Start at 3? No
    Start at 4mark 4
    Visit 0 → push 0[0]mark 0
    Visit 1 → push 1[0,1]mark 1
    Push 4[0,1,4]
    Start at 5mark 5
    Visit 0 (already done)
    Visit 2mark 2
    Visit 3mark 3
    Visit 1 (done)
    Push 3[0,1,4,3]
    Push 2[0,1,4,3,2]
    Push 5[0,1,4,3,2,5]

    Reverse → 5 2 3 4 1 0 (also valid).


    Complexity

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

    Reason

    • We visit each vertex once and scan each edge once → V + E.
    • Adjacency list and recursion stack together store up to V + E items.

    Conclusion

    Topological sorting of a DAG can be done easily with DFS:

    1. Build an adjacency list.
    2. Perform a post-order DFS, pushing nodes onto a stack after visiting children.
    3. Reverse the stack to get a valid ordering.

    The method is linear, simple, and works for any directed acyclic graph.

    Join our FREE Advance DSA COURSE

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

    Easy Graph
    Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
    Previous ArticleIs Graph Bipartite? | Leetcode 785 | Easy 2-Color DFS Solution in Python
    Next Article Detect Cycle in a Directed Graph
    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

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

    4 June 2025
    Data Structures & Algorithms

    Detect Cycle in a Directed Graph

    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.