Topological Sort Using Kahn's Algorithm BFS in DSA Go - Execution Trace

Concept Flow - Topological Sort Using Kahn's Algorithm BFS

Calculate in-degree of all nodes

↓

Initialize queue with nodes having in-degree 0

↓

While queue not empty

Yes↓

Dequeue node

→Add node to topological order

↓

For each neighbor

→Decrease in-degree by 1

↓

If in-degree becomes 0

→Enqueue neighbor

↩Back to While queue not empty

This flow shows how Kahn's algorithm uses in-degree counts and a queue to produce a topological order by repeatedly removing nodes with zero in-degree.

Execution Sample

DSA Go

graph := map[int][]int{
  5: {2, 0},
  4: {0, 1},
  2: {3},
  3: {1},
  0: {},
  1: {},
}
// Perform Kahn's Algorithm topological sort

This code performs topological sorting on a directed graph using Kahn's BFS algorithm.

Execution Table

Step	Operation	Queue	In-degree Map	Topological Order	Visual State
0	Calculate in-degree for all nodes	[]	{5:0,4:0,2:0,3:0,0:0,1:0}	[]	Graph nodes with initial in-degree 0
1	Count in-degree from edges	[]	{5:0,4:0,2:1,3:1,0:2,1:2}	[]	In-degree updated based on edges
2	Initialize queue with nodes having in-degree 0	[5,4]	{5:0,4:0,2:1,3:1,0:2,1:2}	[]	Queue starts with nodes 5 and 4
3	Dequeue node 5	[4]	{5:0,4:0,2:1,3:1,0:2,1:2}	[5]	Remove 5 from queue, add to order
4	Decrease in-degree of neighbors 2 and 0	[4]	{5:0,4:0,2:0,3:1,0:1,1:2}	[5]	In-degree of 2 and 0 decreased by 1
5	Enqueue nodes with in-degree 0 (2)	[4,2]	{5:0,4:0,2:0,3:1,0:1,1:2}	[5]	Node 2 added to queue
6	Dequeue node 4	[2]	{5:0,4:0,2:0,3:1,0:1,1:2}	[5,4]	Remove 4 from queue, add to order
7	Decrease in-degree of neighbors 0 and 1	[2]	{5:0,4:0,2:0,3:1,0:0,1:1}	[5,4]	In-degree of 0 and 1 decreased by 1
8	Enqueue nodes with in-degree 0 (0)	[2,0]	{5:0,4:0,2:0,3:1,0:0,1:1}	[5,4]	Node 0 added to queue
9	Dequeue node 2	[0]	{5:0,4:0,2:0,3:1,0:0,1:1}	[5,4,2]	Remove 2 from queue, add to order
10	Decrease in-degree of neighbor 3	[0]	{5:0,4:0,2:0,3:0,0:0,1:1}	[5,4,2]	In-degree of 3 decreased by 1
11	Enqueue nodes with in-degree 0 (3)	[0,3]	{5:0,4:0,2:0,3:0,0:0,1:1}	[5,4,2]	Node 3 added to queue
12	Dequeue node 0	[3]	{5:0,4:0,2:0,3:0,0:0,1:1}	[5,4,2,0]	Remove 0 from queue, add to order
13	Node 0 has no neighbors to update	[3]	{5:0,4:0,2:0,3:0,0:0,1:1}	[5,4,2,0]	No in-degree changes
14	Dequeue node 3	[]	{5:0,4:0,2:0,3:0,0:0,1:1}	[5,4,2,0,3]	Remove 3 from queue, add to order
15	Decrease in-degree of neighbor 1	[]	{5:0,4:0,2:0,3:0,0:0,1:0}	[5,4,2,0,3]	In-degree of 1 decreased by 1
16	Enqueue nodes with in-degree 0 (1)	[1]	{5:0,4:0,2:0,3:0,0:0,1:0}	[5,4,2,0,3]	Node 1 added to queue
17	Dequeue node 1	[]	{5:0,4:0,2:0,3:0,0:0,1:0}	[5,4,2,0,3,1]	Remove 1 from queue, add to order
18	Node 1 has no neighbors to update	[]	{5:0,4:0,2:0,3:0,0:0,1:0}	[5,4,2,0,3,1]	No in-degree changes
19	Queue empty, algorithm ends	[]	{5:0,4:0,2:0,3:0,0:0,1:0}	[5,4,2,0,3,1]	Topological order complete

💡 Queue is empty, all nodes processed, topological order found

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	After Step 11	After Step 16	Final
Queue	[]	[5,4]	[4,2]	[2,0]	[0,3]	[1]	[]
In-degree	{5:0,4:0,2:0,3:0,0:0,1:0}	{5:0,4:0,2:1,3:1,0:2,1:2}	{5:0,4:0,2:0,3:1,0:1,1:2}	{5:0,4:0,2:0,3:1,0:0,1:1}	{5:0,4:0,2:0,3:0,0:0,1:1}	{5:0,4:0,2:0,3:0,0:0,1:0}	{5:0,4:0,2:0,3:0,0:0,1:0}
Topological Order	[]	[]	[5]	[5,4]	[5,4,2]	[5,4,2,0,3]	[5,4,2,0,3,1]

Key Moments - 3 Insights

Why do we start with nodes that have in-degree 0?

Nodes with in-degree 0 have no dependencies and can be placed first in the order. See execution_table row 2 where queue is initialized with nodes 5 and 4.

What happens when we decrease the in-degree of neighbors?

Decreasing in-degree simulates removing edges. When a neighbor's in-degree reaches 0, it means all its dependencies are processed, so it is added to the queue. See rows 4-5 and 7-8 for examples.

Why does the algorithm end when the queue is empty?

An empty queue means no nodes are left with zero in-degree to process. If all nodes are processed, the topological order is complete. See row 19 where the queue empties and the order is finalized.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, which node was added to the queue?

A Node 3

B Node 0

C Node 2

D Node 1

💡 Hint

Check the 'Queue' column at step 5 in the execution_table

At which step does node 1 get added to the queue?

A Step 16

B Step 11

C Step 8

D Step 5

💡 Hint

Look at the 'Queue' and 'Operation' columns in execution_table rows around step 16

If node 4 had an additional edge to node 3, how would the in-degree of node 3 change after step 7?

A It would decrease to 0

B It would remain 1

C It would increase to 2

D It would become negative

💡 Hint

Adding an edge from 4->3 increases initial in-degree of 3 to 2, but processing node 4 at step 7 decrements it back to 1.

Concept Snapshot

Topological Sort (Kahn's Algorithm):
- Calculate in-degree for all nodes
- Enqueue nodes with in-degree 0
- While queue not empty:
  - Dequeue node, add to order
  - Decrease in-degree of neighbors
  - Enqueue neighbors with in-degree 0
- Ends when all nodes processed
- Produces linear ordering of DAG nodes

Full Transcript

This visualization traces Kahn's algorithm for topological sorting using BFS. We start by calculating the in-degree of each node, which counts how many edges point to it. Nodes with zero in-degree have no dependencies and are added to a queue. We then repeatedly remove nodes from the queue, add them to the topological order, and reduce the in-degree of their neighbors. If any neighbor's in-degree drops to zero, it is added to the queue. This process continues until the queue is empty, meaning all nodes are processed and a valid topological order is found. The execution table shows each step's queue contents, in-degree map, and the growing topological order. Key moments clarify why we start with zero in-degree nodes, how in-degree updates simulate edge removals, and why the algorithm ends when the queue empties. The quiz tests understanding of queue changes and in-degree updates during execution.

Practice

1. What is the main purpose of Kahn's Algorithm in graph theory?

easy

A. To calculate the minimum spanning tree

B. To detect cycles in an undirected graph

C. To find the shortest path between two nodes

D. To find a topological ordering of a Directed Acyclic Graph (DAG)

Solution

1. Step 1: Understand Kahn's Algorithm goal

   Kahn's Algorithm is designed to produce a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u -> v, u comes before v in the ordering.

2. Step 2: Compare with other graph algorithms

   Other options like cycle detection, shortest path, or minimum spanning tree solve different problems unrelated to topological sorting.

3. Final Answer:

   To find a topological ordering of a Directed Acyclic Graph (DAG) -> Option D

4. Quick Check:

   Topological sort = Kahn's Algorithm purpose [OK]

Hint: Kahn's Algorithm always orders DAG nodes topologically [OK]

Common Mistakes:

• Confusing topological sort with cycle detection
• Thinking it works on undirected graphs
• Assuming it finds shortest paths

2. Which Go data structure is best suited to implement the queue in Kahn's Algorithm?

easy

A. Linked list from container/list package

B. Map with keys as indices

C. Slice with append and slicing for enqueue and dequeue

D. Array with fixed size and no dynamic resizing

Solution

1. Step 1: Identify queue operations needed

   Kahn's Algorithm requires efficient enqueue (push back) and dequeue (pop front) operations for nodes with zero indegree.

2. Step 2: Evaluate Go data structures

   Slices can be used but dequeue from front is costly (O(n)). Maps don't maintain order. The container/list package provides a doubly linked list with O(1) enqueue and dequeue, ideal for queue.

3. Final Answer:

   Linked list from container/list package -> Option A

4. Quick Check:

   Efficient queue = container/list linked list [OK]

Hint: Use container/list for efficient queue in Go [OK]

Common Mistakes:

• Using slice and removing front element inefficiently
• Using map which is unordered
• Using fixed-size array without resizing

3. What is the output of the following Go code snippet implementing Kahn's Algorithm on the graph with edges: 5->0, 5->2, 4->0, 4->1, 2->3, 3->1?

package main
import (
  "container/list"
  "fmt"
)
func kahnTopoSort(vertices int, edges [][2]int) []int {
  indegree := make([]int, vertices)
  graph := make([][]int, vertices)
  for _, e := range edges {
    graph[e[0]] = append(graph[e[0]], e[1])
    indegree[e[1]]++
  }
  queue := list.New()
  for i := 0; i < vertices; i++ {
    if indegree[i] == 0 {
      queue.PushBack(i)
    }
  }
  var result []int
  for queue.Len() > 0 {
    front := queue.Remove(queue.Front()).(int)
    result = append(result, front)
    for _, nbr := range graph[front] {
      indegree[nbr]--
      if indegree[nbr] == 0 {
        queue.PushBack(nbr)
      }
    }
  }
  return result
}
func main() {
  edges := [][2]int{{5,0},{5,2},{4,0},{4,1},{2,3},{3,1}}
  order := kahnTopoSort(6, edges)
  fmt.Println(order)
}

medium

A. [4 5 0 2 3 1]

B. [5 4 0 2 3 1]

C. [4 5 2 0 3 1]

D. [5 4 2 3 0 1]

Solution

1. Step 1: Calculate indegrees and initial queue

   Vertices: 0-5. Indegrees: 0->2 (from 4,5), 1->2 (from 3,4), 2->1 (from 5), 3->1 (from 2), 4->0, 5->0. Initial queue: nodes with indegree 0 are 4 and 5.

2. Step 2: Process queue in FIFO order

   Queue: [4,5]. Remove 4: result=[4], decrease indegree of 0 and 1. Indegree 0=1, 1=1. Remove 5: result=[4,5], decrease indegree of 0 and 2. Indegree 0=0 (enqueue 0), 2=0 (enqueue 2). Queue: [0,2]. Remove 0: result=[4,5,0], no neighbors. Remove 2: result=[4,5,0,2], decrease indegree of 3 to 0 (enqueue 3). Queue: [3]. Remove 3: result=[4,5,0,2,3], decrease indegree of 1 to 0 (enqueue 1). Queue: [1]. Remove 1: result=[4,5,0,2,3,1].

3. Final Answer:

   [4 5 0 2 3 1] -> Option A

4. Quick Check:

   Topological order = [4 5 0 2 3 1] [OK]

Hint: Track indegrees and enqueue zero indegree nodes FIFO [OK]

Common Mistakes:

• Mixing order of initial zero indegree nodes
• Forgetting to enqueue neighbors when indegree hits zero
• Confusing DFS topological sort with Kahn's BFS

4. The following Go code for Kahn's Algorithm has a bug causing an infinite loop. What is the error?

func kahnTopoSort(vertices int, edges [][2]int) []int {
  indegree := make([]int, vertices)
  graph := make([][]int, vertices)
  for _, e := range edges {
    graph[e[0]] = append(graph[e[0]], e[1])
    indegree[e[1]]++
  }
  queue := list.New()
  for i := 0; i < vertices; i++ {
    if indegree[i] == 0 {
      queue.PushBack(i)
    }
  }
  var result []int
  for queue.Len() > 0 {
    front := queue.Front().Value.(int)
    result = append(result, front)
    for _, nbr := range graph[front] {
      indegree[nbr]--
      if indegree[nbr] == 0 {
        queue.PushBack(nbr)
      }
    }
  }
  return result
}

medium

A. Indegree array is not initialized correctly

B. Graph edges are not added properly

C. Missing queue.Remove call to dequeue the front element

D. Result slice is not appended correctly

Solution

1. Step 1: Analyze queue usage in loop

   The code uses queue.Front().Value to get the front element but never removes it from the queue, so the queue length never decreases, causing an infinite loop.

2. Step 2: Identify missing operation

   To fix, call queue.Remove(queue.Front()) to dequeue the front element after processing it.

3. Final Answer:

   Missing queue.Remove call to dequeue the front element -> Option C

4. Quick Check:

   Dequeue missing = infinite loop [OK]

Hint: Always remove front element after processing in queue [OK]

Common Mistakes:

• Forgetting to remove front element from queue
• Assuming indegree or graph initialization causes loop
• Not appending result correctly

5. Given a Directed Acyclic Graph (DAG) with 7 vertices and edges: 0->1, 0->2, 1->3, 2->3, 3->4, 4->5, 5->6, how can Kahn's Algorithm be adapted to detect if the graph contains a cycle?

hard

A. Check if any node has indegree zero at start

B. Count processed nodes; if less than total vertices, a cycle exists

C. Use DFS instead of BFS to detect cycles

D. If queue becomes empty before processing all nodes, graph is acyclic

Solution

1. Step 1: Understand Kahn's Algorithm cycle detection

   Kahn's Algorithm processes nodes with zero indegree. If a cycle exists, some nodes never reach zero indegree and remain unprocessed.

2. Step 2: Use processed node count to detect cycle

   Count how many nodes are processed. If count is less than total vertices, it means some nodes are stuck in a cycle and were never enqueued.

3. Final Answer:

   Count processed nodes; if less than total vertices, a cycle exists -> Option B

4. Quick Check:

   Processed nodes < total vertices = cycle [OK]

Hint: Compare processed nodes count with total vertices [OK]

Common Mistakes:

• Assuming presence of zero indegree nodes means no cycle
• Confusing BFS with DFS cycle detection
• Thinking empty queue means acyclic always