Topological Sort Using Kahn's Algorithm BFS in DSA Go

Mental Model

We find an order to do tasks so that all dependencies come before the task itself. We start with tasks that have no dependencies and remove them step by step.

Analogy: Imagine you have to bake a cake, but you must first prepare ingredients like flour and eggs. You start with tasks that need no preparation, then move on to tasks that depend on those, like mixing and baking.

Graph nodes with arrows showing dependencies:

  [A] -> [B] -> [D]
   ↓      ↓
  [C] -> [E]

In-degree counts:
A:0, B:1, C:1, D:1, E:2

Queue starts with nodes having in-degree 0:
Queue: [A]

Dry Run Walkthrough

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

Goal: Find a valid order to complete tasks so that all dependencies come before the task

Step 1: Calculate in-degree for each node and enqueue nodes with in-degree 0

In-degree: A=0, B=1, C=1, D=1, E=2
Queue: [A]

Why: We start with tasks that have no dependencies

Step 2: Dequeue A, add to result, reduce in-degree of B and C by 1

Result: [A]
In-degree: B=0, C=0, D=1, E=2
Queue: [B, C]

Why: Removing A means B and C lose one dependency

Step 3: Dequeue B, add to result, reduce in-degree of D and E by 1

Result: [A, B]
In-degree: C=0, D=0, E=1
Queue: [C, D]

Why: Removing B means D and E lose one dependency

Step 4: Dequeue C, add to result, reduce in-degree of E by 1

Result: [A, B, C]
In-degree: D=0, E=0
Queue: [D, E]

Why: Removing C means E loses one dependency

Step 5: Dequeue D, add to result

Result: [A, B, C, D]
In-degree: E=0
Queue: [E]

Why: D has no outgoing edges, just add to result

Step 6: Dequeue E, add to result

Result: [A, B, C, D, E]
Queue: []

Why: E is last with no dependencies left

Result:

Final order: A -> B -> C -> D -> E

Annotated Code

DSA Go

package main

import (
	"container/list"
	"fmt"
)

// Graph represents a directed graph using adjacency list
type Graph struct {
	adj map[string][]string
}

// NewGraph creates a new graph
func NewGraph() *Graph {
	return &Graph{adj: make(map[string][]string)}
}

// AddEdge adds a directed edge from u to v
func (g *Graph) AddEdge(u, v string) {
	g.adj[u] = append(g.adj[u], v)
	if _, exists := g.adj[v]; !exists {
		g.adj[v] = []string{}
	}
}

// TopologicalSortKahn performs topological sort using Kahn's algorithm (BFS)
func (g *Graph) TopologicalSortKahn() []string {
	inDegree := make(map[string]int)

	// Calculate in-degree of each node
	for u := range g.adj {
		inDegree[u] = 0
	}
	for u := range g.adj {
		for _, v := range g.adj[u] {
			inDegree[v]++
		}
	}

	// Enqueue nodes with in-degree 0
	queue := list.New()
	for node, deg := range inDegree {
		if deg == 0 {
			queue.PushBack(node)
		}
	}

	var result []string

	// Process nodes
	for queue.Len() > 0 {
		front := queue.Front()
		curr := front.Value.(string)
		queue.Remove(front)

		result = append(result, curr)

		// Decrease in-degree of neighbors
		for _, neighbor := range g.adj[curr] {
			inDegree[neighbor]--
			if inDegree[neighbor] == 0 {
				queue.PushBack(neighbor)
			}
		}
	}

	// If result size != number of nodes, graph has a cycle
	if len(result) != len(g.adj) {
		return []string{} // empty means cycle detected
	}

	return result
}

func main() {
	g := NewGraph()
	g.AddEdge("A", "B")
	g.AddEdge("A", "C")
	g.AddEdge("B", "D")
	g.AddEdge("B", "E")
	g.AddEdge("C", "E")

	order := g.TopologicalSortKahn()
	if len(order) == 0 {
		fmt.Println("Cycle detected, no topological order")
	} else {
		for i, node := range order {
			if i > 0 {
				fmt.Print(" -> ")
			}
			fmt.Print(node)
		}
		fmt.Println()
	}
}

for u := range g.adj { inDegree[u] = 0 }

initialize in-degree count for all nodes

for u := range g.adj { for _, v := range g.adj[u] { inDegree[v]++ } }

count incoming edges for each node

for node, deg := range inDegree { if deg == 0 { queue.PushBack(node) } }

enqueue nodes with zero in-degree to start processing

curr := front.Value.(string) queue.Remove(front) result = append(result, curr)

dequeue node and add to result order

for _, neighbor := range g.adj[curr] { inDegree[neighbor]-- if inDegree[neighbor] == 0 { queue.PushBack(neighbor) } }

reduce in-degree of neighbors and enqueue if zero

if len(result) != len(g.adj) { return []string{} }

detect cycle if not all nodes processed

Output

A -> B -> C -> D -> E

Complexity Analysis

Time: O(V + E) because we visit each node and edge once during in-degree calculation and BFS traversal

Space: O(V + E) for storing adjacency list, in-degree map, queue, and result list

vs Alternative: Compared to DFS-based topological sort, Kahn's algorithm uses BFS and explicit in-degree counts, which can be easier to understand and detect cycles early

Edge Cases

Empty graph

Returns empty order immediately

DSA Go

if len(result) != len(g.adj) {
	return []string{}
}

Graph with cycle

Returns empty slice indicating no valid order

DSA Go

if len(result) != len(g.adj) {
	return []string{}
}

Graph with single node and no edges

Returns list with that single node

DSA Go

for node, deg := range inDegree {
	if deg == 0 {
		queue.PushBack(node)
	}
}

When to Use This Pattern

When you need to order tasks with dependencies and want to detect cycles, use Kahn's algorithm BFS for topological sorting because it processes nodes with no dependencies first.

Common Mistakes

Mistake: Not initializing in-degree for all nodes, missing nodes with zero in-degree
Fix: Initialize in-degree map with zero for every node before counting edges

Mistake: Not checking for cycles by comparing result length with number of nodes
Fix: Add a check after BFS to return empty result if cycle detected

Mistake: Not enqueueing neighbors when their in-degree drops to zero
Fix: Enqueue neighbors immediately when their in-degree becomes zero

Summary

Finds an order to complete tasks so all dependencies come before the task using BFS and in-degree counts.

Use it when you have a directed graph with dependencies and want a valid linear order or to detect cycles.

Start with nodes having zero dependencies and remove them step by step, updating neighbors' dependencies.

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