Topological Sort Using Kahn's Algorithm BFS in DSA Javascript - Execution Trace

Concept Flow - Topological Sort Using Kahn's Algorithm BFS

Calculate in-degree for each node

↓

Add nodes with in-degree 0 to queue

↓

While queue not empty

Yes↓

Dequeue node

→Add node to topological order

↓

For each neighbor

→Decrease in-degree by 1

↓

If in-degree becomes 0

→Add neighbor to queue

↩Back to While queue not empty

The algorithm calculates in-degree for all nodes, then repeatedly removes nodes with zero in-degree, updating neighbors until all nodes are processed.

Execution Sample

DSA Javascript

const graph = {
  0: [1, 2],
  1: [3],
  2: [3],
  3: []
};

function topologicalSortKahn(graph) {
  const inDegree = {};
  Object.keys(graph).forEach(node => inDegree[node] = 0);
  Object.values(graph).forEach(neighbors => {
    neighbors.forEach(neighbor => {
      inDegree[neighbor] = (inDegree[neighbor] || 0) + 1;
    });
  });
  const queue = [];
  Object.keys(inDegree).forEach(node => {
    if (inDegree[node] === 0) queue.push(parseInt(node));
  });
  const order = [];
  while (queue.length) {
    const node = queue.shift();
    order.push(node);
    (graph[node] || []).forEach(neighbor => {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    });
  }
  return order;
}

console.log(topologicalSortKahn(graph)); // e.g., [0, 1, 2, 3]

This code performs topological sorting on a directed graph using Kahn's BFS algorithm.

Execution Table

Step	Operation	Nodes Processed	Queue State	In-degree Map	Topological Order	Visual State
1	Calculate in-degree	None	[]	{0:0,1:1,2:1,3:2}	[]	Graph nodes with in-degree counts
2	Initialize queue with nodes of in-degree 0	None	[0]	{0:0,1:1,2:1,3:2}	[]	Queue contains node 0
3	Dequeue node 0	[0]	[]	{0:0,1:1,2:1,3:2}	[0]	Node 0 removed from queue, added to order
4	Process neighbors of 0: nodes 1 and 2	[0]	[]	{0:0,1:0,2:0,3:2}	[0]	Decrement in-degree of 1 and 2
5	Add neighbors with in-degree 0 to queue: 1, 2	[0]	[1,2]	{0:0,1:0,2:0,3:2}	[0]	Queue updated with nodes 1 and 2
6	Dequeue node 1	[0,1]	[2]	{0:0,1:0,2:0,3:2}	[0,1]	Node 1 removed from queue, added to order
7	Process neighbor of 1: node 3	[0,1]	[2]	{0:0,1:0,2:0,3:1}	[0,1]	Decrement in-degree of 3
8	Dequeue node 2	[0,1,2]	[]	{0:0,1:0,2:0,3:1}	[0,1,2]	Node 2 removed from queue, added to order
9	Process neighbor of 2: node 3	[0,1,2]	[]	{0:0,1:0,2:0,3:0}	[0,1,2]	Decrement in-degree of 3 to 0
10	Add neighbor with in-degree 0 to queue: 3	[0,1,2]	[3]	{0:0,1:0,2:0,3:0}	[0,1,2]	Queue updated with node 3
11	Dequeue node 3	[0,1,2,3]	[]	{0:0,1:0,2:0,3:0}	[0,1,2,3]	Node 3 removed from queue, added to order
12	Queue empty, end	[0,1,2,3]	[]	{0:0,1:0,2:0,3:0}	[0,1,2,3]	Topological order complete

💡 Queue is empty, all nodes processed, topological order is complete

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 5	After Step 7	After Step 9	Final
inDegree	{}	{0:0,1:1,2:1,3:2}	{0:0,1:0,2:0,3:2}	{0:0,1:0,2:0,3:2}	{0:0,1:0,2:0,3:1}	{0:0,1:0,2:0,3:0}	{0:0,1:0,2:0,3:0}
queue	[]	[]	[]	[1,2]	[2]	[]	[]
topologicalOrder	[]	[]	[0]	[0]	[0,1]	[0,1,2]	[0,1,2,3]

Key Moments - 3 Insights

Why do we start with nodes that have in-degree 0?

Nodes with in-degree 0 have no dependencies and can be safely placed first in the order, as shown in execution_table row 2 where node 0 is added to the queue first.

What happens when we decrease the in-degree of neighbors?

Decreasing in-degree represents removing the dependency from the processed node. When in-degree reaches 0, the neighbor is ready to be processed, as seen in rows 4, 7, and 9 where neighbors' in-degree is updated.

Why do we add neighbors to the queue only when their in-degree becomes 0?

Adding neighbors only when in-degree is 0 ensures all their dependencies are processed first, preventing cycles and maintaining correct order, demonstrated in rows 5 and 10.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what nodes are in the queue?

A [1, 2]

B [0]

C [3]

D []

💡 Hint

Check the 'Queue State' column at step 5 in execution_table

At which step does node 3 get added to the queue?

A Step 7

B Step 10

C Step 9

D Step 11

💡 Hint

Look for when in-degree of node 3 becomes 0 and it appears in the queue in execution_table

If node 2 had an extra edge to node 1, how would the in-degree of node 1 change after step 1?

A It would be 0

B It would be 1

C It would be 2

D It would be 3

💡 Hint

In-degree counts incoming edges; adding an edge from 2 to 1 increases node 1's in-degree by 1

Concept Snapshot

Topological Sort using Kahn's Algorithm (BFS):
- Calculate in-degree for all nodes
- Enqueue nodes with in-degree 0
- While queue not empty:
  - Dequeue node, add to order
  - Decrease in-degree of neighbors
  - Enqueue neighbors with in-degree 0
- Result is a valid topological order
- Detects cycles if order size < nodes count

Full Transcript

Topological Sort using Kahn's Algorithm works by first calculating the in-degree (number of incoming edges) for each node in the graph. Nodes with zero in-degree have no dependencies and are added to a queue. The algorithm then repeatedly removes nodes from the queue, adds them to the topological order, and decreases the in-degree of their neighbors. When a neighbor's in-degree reaches zero, it is added to the queue. This process continues until the queue is empty, resulting in a topological order of the nodes. The execution table shows each step, including queue state, in-degree map, and the growing topological order. Key moments clarify why nodes with zero in-degree start the process and why neighbors are added only when their in-degree becomes zero. The visual quiz tests understanding of queue contents and in-degree changes during execution.

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 find the shortest path between two nodes

C. To detect cycles in an undirected graph

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 algorithms like shortest path or minimum spanning tree serve different purposes, so they do not match Kahn's Algorithm's goal.

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 orders DAG nodes topologically [OK]

Common Mistakes:

• Confusing topological sort with shortest path
• Thinking it works on undirected graphs
• Assuming it detects cycles directly

2. Which of the following is the correct way to initialize the queue in Kahn's Algorithm in JavaScript?

easy

A. const queue = []; // Push all nodes with indegree 0

B. const queue = new Set(); // Add all nodes with indegree 0

C. const queue = {}; // Store nodes with indegree 0 as keys

D. const queue = null; // Initialize empty queue

Solution

1. Step 1: Identify queue data structure for BFS

   Kahn's Algorithm uses a queue to process nodes with indegree 0 in order. In JavaScript, an array is commonly used as a queue by pushing and shifting elements.

2. Step 2: Evaluate options

   const queue = []; // Push all nodes with indegree 0 correctly initializes an empty array to be used as a queue. const queue = new Set(); // Add all nodes with indegree 0 uses a Set which does not guarantee order. const queue = {}; // Store nodes with indegree 0 as keys uses an object which is not suitable as a queue. const queue = null; // Initialize empty queue initializes null which is invalid.

3. Final Answer:

   const queue = []; // Push all nodes with indegree 0 -> Option A

4. Quick Check:

   Queue = array for BFS in Kahn's Algorithm [OK]

Hint: Use array as queue with push and shift in JavaScript [OK]

Common Mistakes:

• Using Set which does not preserve order
• Using object instead of queue
• Initializing queue as null

3. What will be the output of the following code snippet implementing Kahn's Algorithm on the graph edges [[5, 2], [5, 0], [4, 0], [4, 1], [2, 3], [3, 1]]?

function kahnTopoSort(edges) {
  const graph = {};
  const indegree = {};
  const nodes = new Set();

  edges.forEach(([u, v]) => {
    nodes.add(u);
    nodes.add(v);
    if (!graph[u]) graph[u] = [];
    graph[u].push(v);
    indegree[v] = (indegree[v] || 0) + 1;
    if (!(u in indegree)) indegree[u] = 0;
  });

  const queue = [];
  nodes.forEach(node => {
    if (indegree[node] === 0) queue.push(node);
  });

  const result = [];
  while (queue.length) {
    const node = queue.shift();
    result.push(node);
    (graph[node] || []).forEach(nei => {
      indegree[nei]--;
      if (indegree[nei] === 0) queue.push(nei);
    });
  }

  return result;
}

console.log(kahnTopoSort([[5, 2], [5, 0], [4, 0], [4, 1], [2, 3], [3, 1]]));

medium

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

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

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

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

Solution

1. Step 1: Build graph and indegree map

   Edges create graph: 5->2,5->0,4->0,4->1,2->3,3->1. Indegree counts: 5=0,4=0,2=1,3=1,1=2,0=2.

2. Step 2: Process nodes with indegree 0 and update

   Start queue with [5,4]. Remove 5: result=[5], decrease indegree of 2 and 0. 2 indegree=0, 0 indegree=1. Queue=[4,2]. Remove 4: result=[5,4], decrease indegree of 0 and 1. 0 indegree=0, 1 indegree=1. Queue=[2,0]. Remove 2: result=[5,4,2], decrease indegree of 3. 3 indegree=0. Queue=[0,3]. Remove 0: result=[5,4,2,0], no neighbors. Queue=[3]. Remove 3: result=[5,4,2,0,3], decrease indegree of 1. 1 indegree=0. Queue=[1]. Remove 1: result=[5,4,2,0,3,1]. Queue empty.

3. Final Answer:

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

4. Quick Check:

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

Hint: Track indegree zero nodes and update after removing each node [OK]

Common Mistakes:

• Not updating indegree correctly
• Wrong initial queue nodes
• Mixing order of nodes with same indegree

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

function kahnTopoSort(edges) {
  const graph = {};
  const indegree = {};
  edges.forEach(([u, v]) => {
    if (!graph[u]) graph[u] = [];
    graph[u].push(v);
    indegree[v] = (indegree[v] || 0) + 1;
  });
  const queue = [];
  for (const node in graph) {
    if (!indegree[node]) queue.push(node);
  }
  const result = [];
  while (queue.length) {
    const node = queue.shift();
    result.push(node);
    (graph[node] || []).forEach(nei => {
      indegree[nei]--;
      if (indegree[nei] === 0) queue.push(nei);
    });
  }
  return result;
}

medium

A. Graph edges are not added properly to adjacency list

B. Nodes with zero indegree not correctly identified because some nodes are missing in indegree

C. Queue is initialized incorrectly as an object instead of array

D. The while loop condition should be queue.length > 1

Solution

1. Step 1: Check indegree initialization

   Indegree is only set for nodes that appear as destination (v). Nodes that only appear as source (u) are missing in indegree, so their indegree is undefined, not zero.

2. Step 2: Identify impact on queue initialization

   The queue initialization only loops over keys in the graph object (nodes with outgoing edges). Nodes with zero indegree but no outgoing edges (e.g., isolated nodes) are missing from both the graph and indegree, so not correctly identified.

3. Final Answer:

   Nodes with zero indegree not correctly identified because some nodes are missing in indegree -> Option B

4. Quick Check:

   Indegree missing nodes cause wrong zero indegree detection [OK]

Hint: Initialize indegree for all nodes before queue setup [OK]

Common Mistakes:

• Not initializing indegree for all nodes
• Using wrong loop condition in while
• Incorrect queue data structure

5. Given a graph with edges [[1, 2], [1, 3], [3, 4], [2, 4], [4, 5], [6, 3]], how can you modify Kahn's Algorithm to detect if the graph contains a cycle?

hard

A. Add a visited set and mark nodes visited during BFS; if revisited, cycle exists

B. Count edges and compare with nodes; if edges > nodes, cycle exists

C. Use a stack instead of queue to detect cycles during processing

D. Check if the number of nodes processed is less than total nodes; if yes, a cycle exists

Solution

1. Step 1: Understand Kahn's Algorithm cycle detection

   Kahn's Algorithm processes nodes with zero indegree. If a cycle exists, some nodes will never reach zero indegree and thus won't be processed.

2. Step 2: Detect cycle by comparing processed nodes count

   If the count of processed nodes is less than total nodes, it means some nodes are stuck in a cycle and were never processed, indicating a cycle.

3. Final Answer:

   Check if the number of nodes processed is less than total nodes; if yes, a cycle exists -> Option D

4. Quick Check:

   Processed nodes < total nodes means cycle [OK]

Hint: Compare processed nodes count with total nodes to find cycles [OK]

Common Mistakes:

• Using visited set which is for DFS, not Kahn's Algorithm
• Using stack instead of queue incorrectly
• Comparing edges and nodes count wrongly