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

Practice - 5 Tasks

1fill in blank

easy

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

DSA Java

int[] inDegree = new int[V];
for (int i = 0; i < V; i++) {
    inDegree[i] = [1];
}

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

A0

B1

C-1

DV

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing in-degree with 1 or -1 instead of 0.

Using the number of vertices V as initial in-degree.

In-degree counts start at zero for all vertices before counting edges.

2fill in blank

medium

Complete the code to increase the in-degree of adjacent vertices.

DSA Java

for (int u = 0; u < V; u++) {
    for (int v : adj.get(u)) {
        [1];
    }
}

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

AinDegree[u]++

BinDegree[u]--

CinDegree[v]++

DinDegree[v]--

Attempts:

3 left

💡 Hint

Common Mistakes

Increasing in-degree of u instead of v.

Decreasing in-degree instead of increasing.

For each edge u->v, increase in-degree of v by 1.

3fill in blank

hard

Fix the error in the queue initialization to add all vertices with zero in-degree.

DSA Java

Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < V; i++) {
    if (inDegree[i] [1] 0) {
        queue.add(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 added.

Using '>' which never matches zero in-degree.

Vertices with in-degree equal to zero are added to the queue first.

4fill in blank

hard

Fill both blanks to correctly update in-degree and add vertices to the queue during BFS.

DSA Java

while (!queue.isEmpty()) {
    int u = queue.poll();
    for (int v : adj.get(u)) {
        inDegree[[1]]--;
        if (inDegree[[2]] == 0) {
            queue.add(v);
        }
    }
}

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

Av

Bu

Cqueue

Dadj

Attempts:

3 left

💡 Hint

Common Mistakes

Using u instead of v for in-degree update.

Using queue or adj as index causing errors.

Decrease in-degree of v and add v to queue if its in-degree becomes zero.

5fill in blank

hard

Fill all three blanks to complete the topological sort method returning the order list.

DSA Java

public List<Integer> topologicalSort(int V, List<List<Integer>> adj) {
    int[] inDegree = new int[V];
    for (int i = 0; i < V; i++) {
        for (int v : adj.get(i)) {
            inDegree[v][1];
        }
    }
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < V; i++) {
        if (inDegree[i] [2] 0) {
            queue.add(i);
        }
    }
    List<Integer> topoOrder = new ArrayList<>();
    while (!queue.isEmpty()) {
        int u = queue.poll();
        topoOrder.add(u);
        for (int v : adj.get(u)) {
            inDegree[v][3];
            if (inDegree[v] == 0) {
                queue.add(v);
            }
        }
    }
    return topoOrder;
}

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

A++

B--

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using -- when counting in-degree initially.

Using != instead of == to check zero in-degree.

Using ++ when decreasing in-degree during BFS.

Increase in-degree when counting edges, check for zero in-degree, decrease in-degree when removing edges.

Practice

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

easy

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

B. To detect cycles in an undirected graph

C. To find the shortest path between two nodes

D. To calculate the minimum spanning tree

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 describe different algorithms: cycle detection, shortest path, and minimum spanning tree are unrelated to Kahn's Algorithm.

3. Final Answer:

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

4. Quick Check:

   Topological sort = Kahn's Algorithm purpose [OK]

Hint: Kahn's Algorithm always finds order in DAGs [OK]

Common Mistakes:

• Confusing topological sort with shortest path
• Thinking it detects cycles in undirected graphs
• Mixing with minimum spanning tree algorithms

2. Which Java data structure is typically used to store nodes with zero incoming edges in Kahn's Algorithm?

easy

A. Queue

B. HashSet

C. Stack

D. PriorityQueue

Solution

1. Step 1: Identify the data structure for zero in-degree nodes

   Kahn's Algorithm uses a queue to process nodes with zero incoming edges in FIFO order to maintain correct topological order.

2. Step 2: Eliminate other options

   Stack is LIFO, which can change order; HashSet does not maintain order; PriorityQueue is not required for basic Kahn's Algorithm.

3. Final Answer:

   Queue -> Option A

4. Quick Check:

   Zero in-degree nodes stored in queue [OK]

Hint: Use queue for BFS order in Kahn's Algorithm [OK]

Common Mistakes:

• Using stack instead of queue
• Choosing unordered sets instead of ordered structures
• Confusing with priority queue usage

3. What is the output of the following Java code snippet using Kahn's Algorithm on this graph?

Graph edges: 5->0, 5->2, 4->0, 4->1, 2->3, 3->1

// After running Kahn's Algorithm, print the topological order.

medium

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

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

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

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

Solution

1. Step 1: Calculate in-degree and start nodes

   Nodes 4 and 5 have zero in-degree. Start queue with [4,5] (assuming ascending order).

2. Step 2: Process nodes in queue

   Process 4: output [4], reduce 0 to 1, 1 to 1. Process 5: output [4,5], reduce 0 to 0 (add 0), 2 to 0 (add 2); queue=[0,2]. Process 0: [4,5,0], no neighbors. Process 2: [4,5,0,2], reduce 3 to 0 (add 3). Process 3: [4,5,0,2,3], reduce 1 to 0 (add 1). Process 1: [4,5,0,2,3,1].

3. Final Answer:

   [4, 5, 0, 2, 3, 1] -> Option C

4. Quick Check:

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

Hint: Start with zero in-degree nodes, process neighbors, repeat [OK]

Common Mistakes:

• Mixing order of nodes with zero in-degree
• Not updating in-degree after removing edges
• Adding nodes to queue too early or late

4. Identify the bug in this Java snippet implementing Kahn's Algorithm:

while (!queue.isEmpty()) {
  int node = queue.poll();
  result.add(node);
  for (int neighbor : graph.get(node)) {
    inDegree[neighbor]--;
    if (inDegree[node] == 0) {
      queue.add(neighbor);
    }
}

medium

A. Neighbors should not be iterated in this loop

B. Queue should be a stack for correct order

C. Result list should be cleared inside the loop

D. Incorrect check: should check inDegree[neighbor] == 0, not inDegree[node]

Solution

1. Step 1: Analyze the in-degree update and condition

   After decrementing inDegree[neighbor], the code incorrectly checks if inDegree[node] == 0 instead of inDegree[neighbor] == 0.

2. Step 2: Correct the condition to add neighbors with zero in-degree

   The correct condition is if (inDegree[neighbor] == 0) to add that neighbor to the queue for processing.

3. Final Answer:

   Incorrect check: should check inDegree[neighbor] == 0, not inDegree[node] -> Option D

4. Quick Check:

   Check zero in-degree on neighbor, not current node [OK]

Hint: Check in-degree of neighbor after decrement [OK]

Common Mistakes:

• Checking in-degree of wrong node
• Using stack instead of queue
• Clearing result inside loop mistakenly

5. Given a graph with edges: 1->2, 1->3, 3->4, 2->4, 4->5, and 5->6, which of the following is a valid topological order using Kahn's Algorithm?

hard

A. [1, 2, 3, 5, 4, 6]

B. [1, 3, 2, 4, 5, 6]

C. [6, 5, 4, 3, 2, 1]

D. [1, 2, 3, 4, 6, 5]

Solution

1. Step 1: Identify nodes with zero in-degree and dependencies

   Node 1 has zero in-degree. Nodes 2 and 3 depend on 1; 4 depends on 2 and 3; 5 depends on 4; 6 depends on 5.

2. Step 2: Validate each option for correct order

   [1, 3, 2, 4, 5, 6] respects dependencies: 1 before 2 and 3, 3 and 2 before 4, 4 before 5, 5 before 6. [1, 2, 3, 4, 6, 5] places 6 before 5, invalid. [6, 5, 4, 3, 2, 1] reverses order, invalid. [1, 2, 3, 5, 4, 6] places 5 before 4, invalid.

3. Final Answer:

   [1, 3, 2, 4, 5, 6] -> Option B

4. Quick Check:

   Dependencies respected in order D [OK]

Hint: Parents always appear before children in topological order [OK]

Common Mistakes:

• Placing dependent nodes before their parents
• Reversing the order of edges
• Ignoring multiple valid topological orders