Topological Sort Using DFS in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Topological Sort on a Simple DAG

What is the output of the following Go code performing topological sort using DFS on a directed acyclic graph (DAG)?

DSA Go

package main

import "fmt"

func topoSortDFS(graph map[int][]int) []int {
    visited := make(map[int]bool)
    stack := []int{}

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

    for node := range graph {
        if !visited[node] {
            dfs(node)
        }
    }
    return stack
}

func main() {
    graph := map[int][]int{
        5: {2, 0},
        4: {0, 1},
        2: {3},
        3: {1},
        0: {},
        1: {},
    }
    result := topoSortDFS(graph)
    fmt.Println(result)
}

A [5 4 2 3 1 0]

B [4 5 3 2 1 0]

C [5 4 0 1 2 3]

D [4 5 2 3 1 0]

💡 Hint

Remember that in DFS-based topological sort, nodes are added to the stack after visiting all their neighbors.

The DFS visits nodes starting from 5 and 4. Node 5 leads to 2 and 0, and 2 leads to 3, which leads to 1. The order of finishing times results in [5 4 2 3 1 0].

🧠 Conceptual

intermediate

Understanding the Role of the Stack in DFS Topological Sort

In a DFS-based topological sort, why do we add nodes to the stack only after visiting all their neighbors?

A Because adding nodes before visiting neighbors would cause a runtime error.

B Because adding nodes after visiting neighbors ensures dependencies come before dependents in the order.

C Because adding nodes after visiting neighbors sorts the nodes in ascending order by value.

D Because adding nodes before visiting neighbors results in a reversed graph.

💡 Hint

Think about the order in which tasks depending on others should appear.

Adding nodes after visiting neighbors ensures that all nodes they depend on are placed earlier in the order, respecting dependencies.

🔧 Debug

advanced

Identify the Bug in This DFS Topological Sort Implementation

What error will this Go code produce when running topological sort using DFS on a graph with a cycle?

DSA Go

package main

import "fmt"

func topoSortDFS(graph map[int][]int) []int {
    visited := make(map[int]bool)
    stack := []int{}

    var dfs func(int)
    dfs = func(node int) {
        visited[node] = true
        for _, neighbor := range graph[node] {
            dfs(neighbor)
        }
        stack = append([]int{node}, stack...)
    }

    for node := range graph {
        if !visited[node] {
            dfs(node)
        }
    }
    return stack
}

func main() {
    graph := map[int][]int{
        1: {2},
        2: {3},
        3: {1},
    }
    result := topoSortDFS(graph)
    fmt.Println(result)
}

A The code enters infinite recursion causing a stack overflow.

B The code prints an empty list because of the cycle.

C The code runs and prints a topological order despite the cycle.

D The code panics with a nil pointer dereference.

💡 Hint

Think about what happens when DFS revisits nodes in a cycle without cycle detection.

Without cycle detection, DFS revisits nodes endlessly in the cycle, causing infinite recursion and stack overflow.

📝 Syntax

advanced

Find the Syntax Error in This DFS Topological Sort Snippet

Which option contains the correct syntax to prepend an element to a slice in Go during DFS topological sort?

DSA Go

stack = append(?, stack...)

A node

B stack

C []int{node}

D stack[node]

💡 Hint

Appending a slice to another requires the first argument to be a slice.

To prepend node to stack, we create a new slice with node and append the existing stack after it: append([]int{node}, stack...).

🚀 Application

expert

Determine the Number of Valid Topological Orders for a Given DAG

Given the DAG below, how many valid topological orders exist? Graph edges: 1 -> 3 2 -> 3 3 -> 4 Options:

A 1

B 3

C 4

D 2

💡 Hint

Consider the independent nodes and their possible orderings before the dependent nodes.

Nodes 1 and 2 have no dependencies and can appear in any order before 3 and 4. The valid orders are [1,2,3,4] and [2,1,3,4].

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