Topological Sort Using Kahn's Algorithm BFS in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the in-degree slice for all vertices.

DSA Go

inDegree := make([]int, [1])

Drag options to blanks, or click blank then click option'

Alen(graph)

Bcap(graph)

C0

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using capacity instead of length for the slice size.

Initializing with 0 or 1 which is too small.

The in-degree slice must have the same length as the number of vertices in the graph, which is len(graph).

2fill in blank

medium

Complete the code to enqueue vertices with zero in-degree.

DSA Go

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

Drag options to blanks, or click blank then click option'

A<

B==

C>

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' or '<' instead of '==' causing wrong vertices to be enqueued.

Using '!=' which includes all non-zero in-degree vertices.

Vertices with in-degree equal to zero are the starting points for topological sorting.

3fill in blank

hard

Fix the error in the code that decreases the in-degree of adjacent vertices.

DSA Go

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

Drag options to blanks, or click blank then click option'

A-= 1

B+= 1

C= 1

D*= 1

Attempts:

3 left

💡 Hint

Common Mistakes

Increasing in-degree instead of decreasing it.

Assigning in-degree to 1 incorrectly.

Multiplying in-degree by 1 which does nothing.

We decrease the in-degree of neighbors by 1 when we remove an edge from the graph.

4fill in blank

hard

Fill both blanks to complete the BFS loop that processes the queue.

DSA Go

for len(queue) > 0 {
    node := queue[1]
    queue = queue[2]
    // process node
}

Drag options to blanks, or click blank then click option'

A[0]

B[:1]

C[1:]

D[-1:]

Attempts:

3 left

💡 Hint

Common Mistakes

Using [:1] which returns a slice, not the element.

Using [-1:] which is invalid in Go.

Removing the wrong part of the queue.

We get the first element with queue[0] and remove it by slicing queue[1:].

5fill in blank

hard

Fill all three blanks to complete the function that returns the topological order or an empty slice if a cycle exists.

DSA Go

func topologicalSort(graph [][]int) []int {
    inDegree := make([]int, [1])
    for _, edges := range graph {
        for _, v := range edges {
            inDegree[v] [2]
        }
    }
    queue := []int{}
    for i := 0; i < len(inDegree); i++ {
        if inDegree[i] == 0 {
            queue = append(queue, i)
        }
    }
    var order []int
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        order = append(order, node)
        for _, neighbor := range graph[node] {
            inDegree[neighbor] [3]
            if inDegree[neighbor] == 0 {
                queue = append(queue, neighbor)
            }
        }
    }
    if len(order) != len(graph) {
        return []int{}
    }
    return order
}

Drag options to blanks, or click blank then click option'

Alen(graph)

B+= 1

C-= 1

Dcap(graph)

Attempts:

3 left

💡 Hint

Common Mistakes

Using cap(graph) instead of len(graph).

Decrementing in-degree when counting edges instead of incrementing.

Incrementing in-degree when removing edges instead of decrementing.

We initialize inDegree with len(graph), increment inDegree[v] for each edge, and decrement inDegree[neighbor] when processing.

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