Topological Sort Using DFS in DSA Python

Mental Model

We visit each task and all its successors first, then add the task to the order. This way, tasks come after their prerequisites.

Analogy: Imagine you have to build a toy car. You first build the wheels and the body separately, then put them together. You can't put the wheels on before making them.

Graph:
A -> B -> C
↑
D

We want an order like D -> A -> B -> C where each arrow means 'must come before'.

Dry Run Walkthrough

Input: Graph with edges: A->B, B->C, D->A

Goal: Find an order of tasks so that each task appears after all tasks it depends on

Step 1: Start DFS from node D

Visited: D
Stack: []

Why: We start from a node with no incoming edges to begin ordering

Step 2: From D, visit A

Visited: D, A
Stack: []

Why: Edge D -> A (successor), so visit A first

Step 3: From A, visit B

Visited: D, A, B
Stack: []

Why: Edge A -> B (successor), so visit B first

Step 4: From B, visit C

Visited: D, A, B, C
Stack: []

Why: Edge B -> C (successor), so visit C first

Step 5: C has no successors, add C to stack

Stack: [C]

Why: No successors, so C can be placed last

Step 6: Back to B, add B to stack

Stack: [C, B]

Why: All successors of B are processed, so B can come before C

Step 7: Back to A, add A to stack

Stack: [C, B, A]

Why: All successors of A are processed, so A can come before B

Step 8: Back to D, add D to stack

Stack: [C, B, A, D]

Why: All successors of D are processed, so D can come before A

Result:

Stack (reversed) gives topological order: D -> A -> B -> C

Annotated Code

DSA Python

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.V = vertices

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def dfs(self, v, visited, stack):
        visited.add(v)  # mark current node visited
        for neighbour in self.graph[v]:  # visit all successors first
            if neighbour not in visited:
                self.dfs(neighbour, visited, stack)
        stack.append(v)  # add node after visiting successors

    def topological_sort(self):
        visited = set()
        stack = []
        for vertex in self.graph:
            if vertex not in visited:
                self.dfs(vertex, visited, stack)
        return stack[::-1]  # reverse stack for correct order

# Driver code
if __name__ == '__main__':
    g = Graph(4)
    g.add_edge('A', 'B')
    g.add_edge('B', 'C')
    g.add_edge('D', 'A')

    order = g.topological_sort()
    print(' -> '.join(order) + ' -> null')

visited.add(v) # mark current node visited

mark current node as visited to avoid revisiting

for neighbour in self.graph[v]:

explore all successors of current node

if neighbour not in visited:

visit successor if not already visited

stack.append(v) # add node after dependencies

add current node after all successors are processed

for vertex in self.graph:

start DFS from each unvisited node to cover all graph

return stack[::-1] # reverse stack for correct order

reverse stack to get topological order

Output

D -> A -> B -> C -> null

Complexity Analysis

Time: O(V + E) because we visit each vertex and edge once during DFS

Space: O(V) for visited set and recursion stack in worst case

vs Alternative: Compared to Kahn's BFS approach, DFS uses recursion and stack but both have same time complexity

Edge Cases

Empty graph

Returns empty order without error

DSA Python

for vertex in self.graph:

Graph with single node and no edges

Returns list with that single node

DSA Python

stack.append(v)  # add node after dependencies

Graph with disconnected components

Processes each component separately and combines orders

DSA Python

for vertex in self.graph:

When to Use This Pattern

When you need to order tasks with dependencies and detect a sequence that respects all prerequisites, use topological sort with DFS to find a valid order.

Common Mistakes

Mistake: Adding the node to the stack before visiting its successors
Fix: Add the node to the stack only after all its successors are visited

Mistake: Not reversing the stack before returning the order
Fix: Reverse the stack to get the correct topological order

Summary

Finds an order of tasks so each task comes after all tasks it depends on.

Use when you have tasks with dependencies and need a valid sequence to complete them.

Visit successors first, then add the task to the order to ensure correct sequencing.

Practice

1. What is the main purpose of using DFS in Topological Sort on a directed graph?

easy

A. To visit nodes in a way that all dependencies come before the node itself

B. To find the shortest path between two nodes

C. To detect cycles in an undirected graph

D. To count the number of connected components

Solution

1. Step 1: Understand DFS role in Topological Sort

   DFS visits nodes deeply, ensuring all nodes reachable from a node are visited before the node itself.

2. Step 2: Relate DFS order to dependencies

   In Topological Sort, this means all dependencies (nodes with edges to current node) are processed before the node, preserving order.

3. Final Answer:

   To visit nodes in a way that all dependencies come before the node itself -> Option A

4. Quick Check:

   DFS ensures dependency order in Topological Sort [OK]

Hint: DFS visits dependencies before the node itself [OK]

Common Mistakes:

• Confusing DFS with BFS for topological order
• Thinking DFS finds shortest paths here
• Mixing cycle detection with topological sorting

2. Which of the following is the correct way to mark a node as visited in a DFS-based topological sort in Python?

easy

A. visited.add(node)

B. visited[node] == True

C. visited[node] = True

D. visited.append(node)

Solution

1. Step 1: Understand visited data structure type

   Usually, visited is a list or dictionary indexed by node, so marking visited means assigning True to that index.

2. Step 2: Identify correct syntax for assignment

   Using visited[node] = True correctly marks the node as visited. Using '==' is a comparison, not assignment.

3. Final Answer:

   visited[node] = True -> Option C

4. Quick Check:

   Assign True to visited[node] to mark visited [OK]

Hint: Use assignment (=), not comparison (==), to mark visited [OK]

Common Mistakes:

• Using '==' instead of '=' for assignment
• Using visited.append(node) when visited is a dict/list
• Using visited.add(node) when visited is not a set

3. What is the output of the following code snippet for topological sort using DFS?

graph = {0: [1, 2], 1: [2], 2: []}
visited = [False, False, False]
stack = []
def dfs(node):
    visited[node] = True
    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs(neighbor)
    stack.append(node)

for v in range(3):
    if not visited[v]:
        dfs(v)
print(stack[::-1])

medium

A. [0, 1, 2]

B. [2, 1, 0]

C. [1, 0, 2]

D. [2, 0, 1]

Solution

1. Step 1: Trace DFS calls and stack appends

   Start with node 0: visit 0, then neighbors 1 and 2. DFS(1) visits 1, then 2. DFS(2) visits 2, appends 2. Then append 1, then append 0.

2. Step 2: Reverse stack to get topological order

   Stack after DFS: [2, 1, 0]. Reversing gives [0, 1, 2].

3. Final Answer:

   [0, 1, 2] -> Option A

4. Quick Check:

   Stack reversed gives correct topological order [OK]

Hint: Reverse stack after DFS to get topological order [OK]

Common Mistakes:

• Not reversing the stack before printing
• Appending nodes before recursive DFS calls
• Confusing order of neighbors visited

4. Identify the error in this DFS-based topological sort code snippet:

def dfs(node):
    visited[node] = True
    for neighbor in graph[node]:
        if visited[neighbor]:
            dfs(neighbor)
    stack.append(node)

medium

A. DFS should not append nodes to stack

B. Stack should be cleared before DFS

C. Visited should be a set, not a list

D. The condition should be 'if not visited[neighbor]' before calling dfs

Solution

1. Step 1: Analyze the if condition in DFS

   The code calls dfs(neighbor) only if visited[neighbor] is True, which means neighbor was already visited. This causes repeated visits or infinite recursion.

2. Step 2: Correct the condition to avoid revisiting

   The condition should be 'if not visited[neighbor]' to visit unvisited neighbors only.

3. Final Answer:

   The condition should be 'if not visited[neighbor]' before calling dfs -> Option D

4. Quick Check:

   Visit neighbors only if not visited [OK]

Hint: Call dfs only on unvisited neighbors [OK]

Common Mistakes:

• Calling dfs on already visited nodes
• Not marking nodes visited before recursion
• Appending nodes to stack too early

5. Given a directed acyclic graph with edges: 5->2, 5->0, 4->0, 4->1, 2->3, 3->1, which of the following is a valid topological order using DFS-based topological sort?

hard

A. [1, 3, 2, 4, 5, 0]

B. [5, 4, 2, 3, 1, 0]

C. [0, 1, 2, 3, 4, 5]

D. [5, 2, 3, 1, 0, 4]

Solution

1. Step 1: Understand dependencies from edges

   Edges mean 5 before 2 and 0, 4 before 0 and 1, 2 before 3, 3 before 1. So 5 and 4 come before 2,3,1,0.

2. Step 2: Check each option for order validity

   [5, 4, 2, 3, 1, 0] respects all edges: 5 before 2 and 0, 4 before 0 and 1, 2 before 3, 3 before 1. Others violate these orders.

3. Final Answer:

   [5, 4, 2, 3, 1, 0] -> Option B

4. Quick Check:

   All edges respected in order [OK]

Hint: Check all edges respected in order for valid topological sort [OK]

Common Mistakes:

• Ignoring edge directions in order
• Assuming any order of nodes is valid
• Not verifying all dependencies before nodes