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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kahn's Algorithm on a Simple DAG

What is the printed topological order of the graph after running Kahn's Algorithm BFS?

DSA Java

import java.util.*;

public class Main {
    public static void kahnTopologicalSort(int vertices, List<List<Integer>> graph) {
        int[] indegree = new int[vertices];
        for (int i = 0; i < vertices; i++) {
            for (int node : graph.get(i)) {
                indegree[node]++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < vertices; i++) {
            if (indegree[i] == 0) {
                queue.add(i);
            }
        }

        List<Integer> topoOrder = new ArrayList<>();
        while (!queue.isEmpty()) {
            int current = queue.poll();
            topoOrder.add(current);
            for (int neighbor : graph.get(current)) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.add(neighbor);
                }
            }
        }

        if (topoOrder.size() != vertices) {
            System.out.println("Cycle detected, no topological order exists.");
        } else {
            for (int node : topoOrder) {
                System.out.print(node + " -> ");
            }
            System.out.println("null");
        }
    }

    public static void main(String[] args) {
        int vertices = 4;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }
        graph.get(0).add(1);
        graph.get(0).add(2);
        graph.get(1).add(2);
        graph.get(2).add(3);

        kahnTopologicalSort(vertices, graph);
    }
}

A 0 -> 1 -> 2 -> 3 -> null

B 0 -> 2 -> 1 -> 3 -> null

C 1 -> 0 -> 2 -> 3 -> null

D Cycle detected, no topological order exists.

💡 Hint

Start with nodes having zero incoming edges and remove edges as you process nodes.

Node 0 has no incoming edges, so it starts. Then 1 and 2 become zero indegree in order, followed by 3. The order is 0 -> 1 -> 2 -> 3 -> null.

❓ Predict Output

intermediate

Detecting Cycle with Kahn's Algorithm

What will be the output when Kahn's Algorithm BFS is run on this graph with a cycle?

DSA Java

import java.util.*;

public class Main {
    public static void kahnTopologicalSort(int vertices, List<List<Integer>> graph) {
        int[] indegree = new int[vertices];
        for (int i = 0; i < vertices; i++) {
            for (int node : graph.get(i)) {
                indegree[node]++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < vertices; i++) {
            if (indegree[i] == 0) {
                queue.add(i);
            }
        }

        List<Integer> topoOrder = new ArrayList<>();
        while (!queue.isEmpty()) {
            int current = queue.poll();
            topoOrder.add(current);
            for (int neighbor : graph.get(current)) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.add(neighbor);
                }
            }
        }

        if (topoOrder.size() != vertices) {
            System.out.println("Cycle detected, no topological order exists.");
        } else {
            for (int node : topoOrder) {
                System.out.print(node + " -> ");
            }
            System.out.println("null");
        }
    }

    public static void main(String[] args) {
        int vertices = 3;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }
        graph.get(0).add(1);
        graph.get(1).add(2);
        graph.get(2).add(0); // cycle edge

        kahnTopologicalSort(vertices, graph);
    }
}

A 0 -> 1 -> 2 -> null

B 2 -> 0 -> 1 -> null

C 1 -> 2 -> 0 -> null

D Cycle detected, no topological order exists.

💡 Hint

If the number of nodes processed is less than total nodes, a cycle exists.

Because of the cycle 0->1->2->0, no node has zero indegree initially, so the queue is empty and no nodes are processed. The algorithm detects a cycle.

🧠 Conceptual

advanced

Understanding Indegree in Kahn's Algorithm

In Kahn's Algorithm BFS for topological sorting, what does the 'indegree' array represent?

A The distance of each node from the start node

B The number of edges coming into each node

C The total number of edges connected to each node

D The number of edges going out from each node

💡 Hint

Think about which nodes can be processed first in topological order.

Indegree counts how many edges come into a node. Nodes with zero indegree have no dependencies and can be processed first.

❓ Predict Output

advanced

Output of Kahn's Algorithm on a Graph with Multiple Valid Orders

What is the output of the following code running Kahn's Algorithm BFS on this graph?

DSA Java

import java.util.*;

public class Main {
    public static void kahnTopologicalSort(int vertices, List<List<Integer>> graph) {
        int[] indegree = new int[vertices];
        for (int i = 0; i < vertices; i++) {
            for (int node : graph.get(i)) {
                indegree[node]++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < vertices; i++) {
            if (indegree[i] == 0) {
                queue.add(i);
            }
        }

        List<Integer> topoOrder = new ArrayList<>();
        while (!queue.isEmpty()) {
            int current = queue.poll();
            topoOrder.add(current);
            for (int neighbor : graph.get(current)) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.add(neighbor);
                }
            }
        }

        if (topoOrder.size() != vertices) {
            System.out.println("Cycle detected, no topological order exists.");
        } else {
            for (int node : topoOrder) {
                System.out.print(node + " -> ");
            }
            System.out.println("null");
        }
    }

    public static void main(String[] args) {
        int vertices = 5;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }
        graph.get(0).add(2);
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(3).add(4);

        kahnTopologicalSort(vertices, graph);
    }
}

A 0 -> 1 -> 2 -> 3 -> 4 -> null

B 1 -> 0 -> 2 -> 3 -> 4 -> null

C 0 -> 1 -> 3 -> 2 -> 4 -> null

D Cycle detected, no topological order exists.

💡 Hint

Nodes 0 and 1 have zero indegree initially and can be processed in any order, but queue order affects output.

Queue adds nodes with zero indegree in order 0 then 1, so output starts with 0 then 1. Then 2, 3, 4 follow.

🧠 Conceptual

expert

Why Kahn's Algorithm Uses a Queue

Why does Kahn's Algorithm for topological sorting use a queue data structure to process nodes?

A To process nodes in the order they appear in the graph adjacency list

B To store nodes temporarily before sorting them alphabetically

C To ensure nodes with zero indegree are processed in a breadth-first manner, respecting dependencies

D To reverse the order of nodes for the final topological sort

💡 Hint

Think about how dependencies are resolved layer by layer.

The queue helps process nodes with zero indegree first, then their neighbors, ensuring dependencies are respected in BFS order.

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