Topological Sort Using Kahn's Algorithm BFS in DSA Java - Build from Scratch

Topological Sort Using Kahn's Algorithm BFS

📖 Scenario: Imagine you are managing tasks in a project where some tasks must be done before others. You want to find an order to do all tasks without breaking any rules.

🎯 Goal: Build a Java program that uses Kahn's Algorithm with BFS to find a valid order of tasks (topological sort) from given task dependencies.

📋 What You'll Learn

Create an adjacency list to represent the graph of tasks

Create an array to store the in-degree (number of incoming edges) for each task

Use a queue to process tasks with zero in-degree

Implement the core logic of Kahn's Algorithm to find the topological order

Print the topological order of tasks

💡 Why This Matters

🌍 Real World

Topological sorting is used in project scheduling, build systems, and resolving dependencies in software packages.

💼 Career

Understanding topological sort and graph traversal algorithms is important for software engineers working on compilers, task schedulers, and dependency management.

1

Create the graph representation

Create an adjacency list called graph as an ArrayList<ArrayList<Integer>> with size 6. Add edges to represent these dependencies: task 5 points to 2 and 0, task 4 points to 0 and 1, task 2 points to 3, and task 3 points to 1.

DSA Java

// Create the graph adjacency list with 6 nodes
// Your code here

Hint

Use a loop to add empty lists for each node, then add edges using graph.get(node).add(neighbor).

2

Create the in-degree array

Create an integer array called inDegree of size 6. Initialize all values to 0. Then, use a for loop with variable i from 0 to 5 and a nested for loop with variable neighbor to count the in-degree of each node by iterating over graph.get(i) and incrementing inDegree[neighbor].

DSA Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int n = 6;
        ArrayList> graph = new ArrayList();
        for (int i = 0; i ());
        }
        graph.get(5).add(2);
        graph.get(5).add(0);
        graph.get(4).add(0);
        graph.get(4).add(1);
        graph.get(2).add(3);
        graph.get(3).add(1);

        // Create inDegree array and count in-degrees
        // Your code here
    }
}

Hint

Use nested loops to count how many edges point to each node.

3

Implement Kahn's Algorithm core logic

Create a Queue<Integer> called queue. Add all nodes with inDegree 0 to queue using a for loop with variable i. Create an ArrayList<Integer> called topoOrder to store the topological order. Use a while loop to process nodes from queue: remove the front node into current, add current to topoOrder, then for each neighbor in graph.get(current), decrement inDegree[neighbor]. If inDegree[neighbor] becomes 0, add neighbor to queue.

DSA Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int n = 6;
        ArrayList> graph = new ArrayList();
        for (int i = 0; i ());
        }
        graph.get(5).add(2);
        graph.get(5).add(0);
        graph.get(4).add(0);
        graph.get(4).add(1);
        graph.get(2).add(3);
        graph.get(3).add(1);

        int[] inDegree = new int[n];
        for (int i = 0; i < n; i++) {
            for (int neighbor : graph.get(i)) {
                inDegree[neighbor]++;
            }
        }

        // Implement Kahn's Algorithm core logic
        // Your code here
    }
}

Hint

Use a queue to process nodes with zero in-degree and update neighbors' in-degree.

4

Print the topological order

Use a for loop with variable node to iterate over topoOrder and print each node followed by a space on the same line using System.out.print(node + " "). Then print a newline with System.out.println().

DSA Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int n = 6;
        ArrayList> graph = new ArrayList();
        for (int i = 0; i ());
        }
        graph.get(5).add(2);
        graph.get(5).add(0);
        graph.get(4).add(0);
        graph.get(4).add(1);
        graph.get(2).add(3);
        graph.get(3).add(1);

        int[] inDegree = new int[n];
        for (int i = 0; i  queue = new LinkedList();
        for (int i = 0; i  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);
                }
            }
        }

        // Print the topological order
        // Your code here
    }
}

Hint

Print all nodes in topoOrder separated by spaces on one line.

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