Topological Sort Using Kahn's Algorithm BFS in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind Kahn's Algorithm for Topological Sort?

Kahn's Algorithm uses BFS by repeatedly removing nodes with zero incoming edges (in-degree) and adding them to the sorted order until all nodes are processed.

beginner

In Kahn's Algorithm, what does a node with zero in-degree represent?

A node with zero in-degree has no dependencies and can be safely added next in the topological order.

intermediate

Why does Kahn's Algorithm detect cycles in a graph?

If after processing all zero in-degree nodes, some nodes remain unprocessed, it means there is a cycle preventing those nodes from reaching zero in-degree.

beginner

What data structure is commonly used to keep track of nodes with zero in-degree in Kahn's Algorithm?

A queue is used to store nodes with zero in-degree so they can be processed in order using BFS.

intermediate

How does Kahn's Algorithm update the in-degree of neighboring nodes?

When a node is removed from the graph, the in-degree of its neighbors is decreased by one because one dependency is removed.

What is the first step in Kahn's Algorithm for topological sorting?

A Sort nodes alphabetically

B Find all nodes with zero in-degree and add them to a queue

C Remove edges randomly

D Start DFS from any node

Kahn's Algorithm begins by finding all nodes with zero in-degree, meaning no dependencies, and adding them to a queue for processing.

What does it mean if after running Kahn's Algorithm some nodes are not included in the topological order?

A The graph has a cycle

B The graph is disconnected

C The graph is empty

D The graph is fully sorted

If nodes remain unprocessed, it means they are part of a cycle, so no valid topological order exists.

Which data structure is essential for implementing Kahn's Algorithm efficiently?

A Linked List

B Stack

C Hash Map

D Queue

A queue is used to process nodes with zero in-degree in FIFO order during BFS.

How is the in-degree of a node defined in a directed graph?

A Total number of edges connected to the node

B Number of edges going out of the node

C Number of edges coming into the node

D Number of nodes connected to it

In-degree counts how many edges point to the node.

What happens to the in-degree of neighbors when a node is removed in Kahn's Algorithm?

A It decreases by one

B It increases by one

C It stays the same

D It resets to zero

Removing a node removes one incoming edge from its neighbors, so their in-degree decreases by one.

Explain step-by-step how Kahn's Algorithm performs topological sorting on a directed graph.

Think about how dependencies are removed layer by layer.

Describe how Kahn's Algorithm can detect if a directed graph contains a cycle.

Focus on what happens when no nodes are left with zero in-degree but graph is not empty.

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