Topological Sort Using DFS in DSA Go

Mental Model

We visit each node and all its dependencies first, then add the node to the order. This way, nodes come after their prerequisites.

Analogy: Imagine you must finish homework problems in order. You first complete all problems that a problem depends on, then you do that problem last.

Graph:
1 -> 2 -> 3
↑    ↑
4    5

Topological order means: 4,1,5,2,3 or 4,5,1,2,3 depending on dependencies.

Dry Run Walkthrough

Input: Graph edges: 1->2, 1->3, 3->4, 2->4

Goal: Find an order to do tasks so that each task comes after all tasks it depends on.

Step 1: Start DFS at node 1, mark 1 visited

Visited: {1}
Stack: []

Why: We start from node 1 to explore its dependencies first.

Step 2: From 1, DFS to 2, mark 2 visited

Visited: {1,2}
Stack: []

Why: We explore node 2 before finishing node 1.

Step 3: From 2, DFS to 4, mark 4 visited

Visited: {1,2,4}
Stack: []

Why: Node 4 depends on 2, so we visit 4 first.

Step 4: Node 4 has no neighbors, add 4 to stack

Stack: [4]

Why: No more dependencies, so 4 can be placed last in order.

Step 5: Back to 2, all neighbors visited, add 2 to stack

Stack: [4, 2]

Why: 2 can be placed after 4.

Step 6: Back to 1, DFS to 3, mark 3 visited

Visited: {1,2,3,4}
Stack: [4, 2]

Why: Explore other neighbor 3 of 1.

Step 7: From 3, DFS to 4 but 4 already visited, skip

Stack: [4, 2]

Why: Avoid revisiting nodes to prevent cycles.

Step 8: Add 3 to stack after its neighbors

Stack: [4, 2, 3]

Why: 3 can be placed after 4.

Step 9: Back to 1, all neighbors visited, add 1 to stack

Stack: [4, 2, 3, 1]

Why: 1 can be placed after 2 and 3.

Result:

Topological order (reverse stack): 1 -> 3 -> 2 -> 4

Annotated Code

DSA Go

package main

import (
	"fmt"
)

type Graph struct {
	adj map[int][]int
}

func NewGraph() *Graph {
	return &Graph{adj: make(map[int][]int)}
}

func (g *Graph) AddEdge(u, v int) {
	g.adj[u] = append(g.adj[u], v)
}

func (g *Graph) TopologicalSort() []int {
	visited := make(map[int]bool)
	stack := []int{}

	var dfs func(int)
	dfs = func(node int) {
		visited[node] = true // mark node visited
		for _, neighbor := range g.adj[node] {
			if !visited[neighbor] {
				dfs(neighbor) // visit dependencies first
			}
		}
		stack = append(stack, node) // add node after dependencies
	}

	for node := range g.adj {
		if !visited[node] {
			dfs(node) // start DFS if not visited
		}
	}

	// reverse stack to get topological order
	topo := make([]int, len(stack))
	for i := range stack {
		topo[i] = stack[len(stack)-1-i]
	}
	return topo
}

func main() {
	g := NewGraph()
	g.AddEdge(1, 2)
	g.AddEdge(1, 3)
	g.AddEdge(3, 4)
	g.AddEdge(2, 4)

	order := g.TopologicalSort()
	for i, v := range order {
		if i > 0 {
			fmt.Print(" -> ")
		}
		fmt.Print(v)
	}
	fmt.Println()
}

visited[node] = true // mark node visited

mark current node as visited to avoid revisiting

for _, neighbor := range g.adj[node] { if !visited[neighbor] { dfs(neighbor) } }

visit all neighbors (dependencies) first recursively

stack = append(stack, node) // add node after dependencies

add node to stack after all dependencies are processed

for node := range g.adj { if !visited[node] { dfs(node) } }

start DFS from all nodes to cover disconnected parts

reverse stack to get topological order

reverse collected nodes to get correct order

Output

1 -> 3 -> 2 -> 4

Complexity Analysis

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

Space: O(V) for visited map and recursion stack to track nodes

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 Go

for node := range g.adj { if !visited[node] { dfs(node) } }

Graph with single node and no edges

Returns list with single node

DSA Go

for node := range g.adj { if !visited[node] { dfs(node) } }

Graph with disconnected components

Visits all components and returns combined topological order

DSA Go

for node := range g.adj { if !visited[node] { dfs(node) } }

When to Use This Pattern

When you need to order tasks with dependencies and detect a valid sequence, use DFS topological sort to explore dependencies first and build order backwards.

Common Mistakes

Mistake: Adding node to stack before visiting neighbors
Fix: Add node to stack only after all neighbors are visited to ensure dependencies come first

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

Summary

Finds an order of nodes so each node appears after all nodes it depends on.

Use when you have tasks with dependencies and want a valid execution order.

Visit dependencies first with DFS, then add the node 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 ensures dependencies come before dependents

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 dependencies of a node are visited before the node itself.

2. Step 2: Relate DFS order to dependencies

   By pushing nodes to a stack after visiting all neighbors, we get an order where dependencies come before dependents.

3. Final Answer:

   To visit nodes in a way that ensures dependencies come before dependents -> Option A

4. Quick Check:

   DFS ensures dependency order = A [OK]

Hint: DFS post-order gives correct dependency order [OK]

Common Mistakes:

• Confusing DFS with BFS for topological sort
• Thinking topological sort finds shortest paths
• Assuming DFS detects cycles in undirected graphs here

2. Which of the following Go code snippets correctly declares a recursive DFS function for topological sort?

easy

A. func dfs(node int, graph map[int][]int, visited map[int]bool, stack *[]int) { if visited[node] { return } visited[node] = true *stack = append(*stack, node) for _, neighbor := range graph[node] { dfs(neighbor, graph, visited, stack) } }

B. func dfs(node int, graph map[int][]int, visited map[int]bool, stack []int) { if visited[node] { return } visited[node] = true for _, neighbor := range graph[node] { dfs(neighbor, graph, visited, stack) } stack = append(stack, node) }

C. func dfs(node int, graph map[int][]int, visited map[int]bool, stack *[]int) { if visited[node] { return } for _, neighbor := range graph[node] { dfs(neighbor, graph, visited, stack) } visited[node] = true *stack = append(*stack, node) }

D. func dfs(node int, graph map[int][]int, visited map[int]bool, stack *[]int) { if !visited[node] { visited[node] = true for _, neighbor := range graph[node] { dfs(neighbor, graph, visited, stack) } *stack = append(*stack, node) } }

Solution

1. Step 1: Check visited condition and marking

   func dfs(node int, graph map[int][]int, visited map[int]bool, stack *[]int) { if !visited[node] { visited[node] = true for _, neighbor := range graph[node] { dfs(neighbor, graph, visited, stack) } *stack = append(*stack, node) } } correctly checks if node is not visited before processing and marks it visited inside the condition.

2. Step 2: Confirm stack append and recursion

   It recursively calls dfs on neighbors and appends node to stack after visiting neighbors, using pointer to modify stack.

3. Final Answer:

   Option D code snippet -> Option D

4. Quick Check:

   Correct DFS recursion and stack append = D [OK]

Hint: Use pointer for stack to append in recursive DFS [OK]

Common Mistakes:

• Passing stack by value causing no changes
• Marking visited after recursion causing repeated visits
• Appending node before visiting neighbors

3. What is the output order of nodes after performing topological sort using DFS on this graph?

graph := map[int][]int{
  5: {2, 0},
  4: {0, 1},
  2: {3},
  3: {1},
  0: {},
  1: {},
}

Assuming DFS visits nodes in ascending order starting from 5, then 4.

medium

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

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

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

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

Solution

1. Step 1: Perform DFS starting from node 5

   DFS from 5 (neighbors ascending: 0 then 2): DFS(0) append 0; then DFS(2) -> DFS(3) -> DFS(1) append 1; append 3; append 2; append 5. Then DFS from 4 (0,1 visited), append 4.

2. Step 2: Collect nodes in post-order (append after visiting neighbors)

   Post-order stack push order: 0, 1, 3, 2, 5, 4. Reversing gives [4, 5, 2, 3, 1, 0].

3. Step 3: Consider DFS starting order and visited nodes

   Since DFS visits 5 first, then 4, the final topological order is the reverse of the post-order stack: [4, 5, 2, 3, 1, 0]. However, the question states DFS visits nodes in ascending order starting from 5, then 4. The actual post-order stack is [0,1,3,2,5,4], so reversed order is [4,5,2,3,1,0].

4. Final Answer:

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

5. Quick Check:

   Post-order reverse = [4,5,2,3,1,0] [OK]

Hint: Reverse DFS post-order for topological sort output [OK]

Common Mistakes:

• Not reversing the stack after DFS
• Visiting nodes in wrong order
• Ignoring already visited nodes

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

func dfs(node int, graph map[int][]int, visited map[int]bool, stack *[]int) {
  if visited[node] {
    return
  }
  for _, neighbor := range graph[node] {
    dfs(neighbor, graph, visited, stack)
  }
  visited[node] = true
  *stack = append(*stack, node)
}

medium

A. Visited is marked after recursion, causing repeated visits

B. Stack is appended before visiting neighbors

C. Visited map is not initialized

D. Function does not return any value

Solution

1. Step 1: Check visited marking timing

   Visited is marked after recursive calls, so neighbors may revisit the same node multiple times.

2. Step 2: Correct visited marking position

   Visited should be marked before recursion to avoid repeated visits and infinite loops.

3. Final Answer:

   Visited is marked after recursion, causing repeated visits -> Option A

4. Quick Check:

   Mark visited before recursion = B [OK]

Hint: Mark visited before recursion to avoid repeats [OK]

Common Mistakes:

• Marking visited too late causing infinite recursion
• Appending stack before recursion
• Ignoring initialization of visited map

5. Given a directed graph with edges:

1 -> 2, 1 -> 3, 3 -> 4, 2 -> 4, 4 -> 5

If you want to find a valid order to complete tasks represented by nodes, which topological sort order is correct?

hard

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

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

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

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

Solution

1. Step 1: Analyze dependencies from edges

   Node 1 must come before 2 and 3; 2 and 3 before 4; 4 before 5.

2. Step 2: Find order respecting dependencies

   Order [1, 2, 3, 4, 5] respects all edges: 1 before 2 and 3, 2 and 3 before 4, 4 before 5.

3. Final Answer:

   [1, 2, 3, 4, 5] -> Option C

4. Quick Check:

   Dependencies respected = C [OK]

Hint: Start with nodes having no incoming edges [OK]

Common Mistakes:

• Reversing order ignoring dependencies
• Placing dependent before dependency
• Choosing order with cycles