Topological Sort Using Kahn's Algorithm BFS in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kahn's Algorithm on a Simple DAG

What is the output of the following Go code implementing Kahn's Algorithm for topological sorting on the given graph?

DSA Go

package main

import (
	"fmt"
)

func kahnTopoSort(vertices int, edges [][]int) []int {
	inDegree := make([]int, vertices)
	graph := make([][]int, vertices)

	for _, edge := range edges {
		graph[edge[0]] = append(graph[edge[0]], edge[1])
		inDegree[edge[1]]++
	}

	queue := []int{}
	for i := 0; i < vertices; i++ {
		if inDegree[i] == 0 {
			queue = append(queue, i)
		}
	}

	var topoOrder []int
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		topoOrder = append(topoOrder, node)

		for _, neighbor := range graph[node] {
			inDegree[neighbor]--
			if inDegree[neighbor] == 0 {
				queue = append(queue, neighbor)
			}
		}
	}

	return topoOrder
}

func main() {
	vertices := 6
	edges := [][]int{{5, 2}, {5, 0}, {4, 0}, {4, 1}, {2, 3}, {3, 1}}
	topo := kahnTopoSort(vertices, edges)
	fmt.Println(topo)
}

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

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

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

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

💡 Hint

Start with nodes having zero incoming edges and remove edges step by step.

The algorithm starts with nodes 4 and 5 which have zero incoming edges. Then it removes edges from these nodes and adds new zero in-degree nodes to the queue. The resulting order is [5, 4, 0, 2, 3, 1].

🧠 Conceptual

intermediate

Understanding In-degree in Kahn's Algorithm

In Kahn's Algorithm for topological sorting, what does the 'in-degree' of a node represent?

A The number of edges coming into the node.

B The number of nodes reachable from the node.

C The total number of edges connected to the node.

D The number of edges going out from the node.

💡 Hint

Think about what must be zero for a node to be processed first.

In-degree is the count of edges coming into a node. Nodes with zero in-degree have no dependencies and can be processed first.

🔧 Debug

advanced

Identify the Bug in Kahn's Algorithm Implementation

What error will the following Go code produce when running Kahn's Algorithm on a graph with a cycle?

DSA Go

package main

import "fmt"

func kahnTopoSort(vertices int, edges [][]int) []int {
	inDegree := make([]int, vertices)
	graph := make([][]int, vertices)

	for _, edge := range edges {
		graph[edge[0]] = append(graph[edge[0]], edge[1])
		inDegree[edge[1]]++
	}

	queue := []int{}
	for i := 0; i < vertices; i++ {
		if inDegree[i] == 0 {
			queue = append(queue, i)
		}
	}

	var topoOrder []int
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		topoOrder = append(topoOrder, node)

		for _, neighbor := range graph[node] {
			inDegree[neighbor]--
			if inDegree[neighbor] == 0 {
				queue = append(queue, neighbor)
			}
		}
	}

	return topoOrder
}

func main() {
	vertices := 3
	edges := [][]int{{0, 1}, {1, 2}, {2, 0}}
	topo := kahnTopoSort(vertices, edges)
	fmt.Println(topo)
}

A The code will print an empty slice [] because no node has zero in-degree.

B The code will panic with an index out of range error.

C The code will print a partial topological order missing some nodes.

D The code will enter an infinite loop.

💡 Hint

Consider what happens when the graph contains a cycle.

Kahn's Algorithm cannot produce a full topological order if the graph has a cycle. It returns a partial order missing nodes involved in the cycle.

🚀 Application

advanced

Use Case of Kahn's Algorithm in Task Scheduling

Which of the following scenarios is best solved by using Kahn's Algorithm for topological sorting?

A Balancing a binary search tree after insertion.

B Detecting cycles in an undirected graph.

C Finding the shortest path between two nodes in a weighted graph.

D Scheduling tasks with dependencies so that all prerequisites are completed first.

💡 Hint

Think about ordering tasks where some must happen before others.

Kahn's Algorithm is used to order tasks with dependencies, ensuring all prerequisite tasks are done before dependent tasks.

❓ Predict Output

expert

Output of Kahn's Algorithm on a Complex DAG

What is the output of the following Go code implementing Kahn's Algorithm on the given graph?

DSA Go

package main

import (
	"fmt"
)

func kahnTopoSort(vertices int, edges [][]int) []int {
	inDegree := make([]int, vertices)
	graph := make([][]int, vertices)

	for _, edge := range edges {
		graph[edge[0]] = append(graph[edge[0]], edge[1])
		inDegree[edge[1]]++
	}

	queue := []int{}
	for i := 0; i < vertices; i++ {
		if inDegree[i] == 0 {
			queue = append(queue, i)
		}
	}

	var topoOrder []int
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		topoOrder = append(topoOrder, node)

		for _, neighbor := range graph[node] {
			inDegree[neighbor]--
			if inDegree[neighbor] == 0 {
				queue = append(queue, neighbor)
			}
		}
	}

	return topoOrder
}

func main() {
	vertices := 8
	edges := [][]int{{0, 2}, {1, 2}, {1, 3}, {3, 4}, {2, 5}, {4, 5}, {5, 6}, {6, 7}}
	topo := kahnTopoSort(vertices, edges)
	fmt.Println(topo)
}

A [1, 0, 2, 3, 4, 5, 6, 7]

B [1, 0, 3, 2, 4, 5, 6, 7]

C [0, 1, 3, 2, 4, 5, 6, 7]

D [0, 1, 2, 3, 4, 5, 6, 7]

💡 Hint

Check which nodes have zero in-degree initially and the order they are processed.

Nodes 0 and 1 have zero in-degree. The queue starts with [0,1]. Processing 1 before 0 leads to the order [1, 0, 2, 3, 4, 5, 6, 7].

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