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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kahn's Algorithm on a Simple DAG

What is the output of the following JavaScript code that performs topological sort using Kahn's Algorithm on the given graph?

DSA Javascript

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

function kahnTopologicalSort(graph) {
  const inDegree = {};
  for (const node in graph) {
    inDegree[node] = 0;
  }
  for (const node in graph) {
    for (const neighbor of graph[node]) {
      inDegree[neighbor]++;
    }
  }

  const queue = [];
  for (const node in inDegree) {
    if (inDegree[node] === 0) queue.push(node);
  }

  const topoOrder = [];
  while (queue.length > 0) {
    const current = queue.shift();
    topoOrder.push(current);
    for (const neighbor of graph[current]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  return topoOrder;
}

console.log(kahnTopologicalSort(graph));

A ["0", "1", "2", "3"]

B ["1", "2", "0", "3"]

C ["0", "2", "1", "3"]

D ["3", "1", "2", "0"]

💡 Hint

Start with nodes having zero incoming edges and process neighbors by reducing their in-degree.

The algorithm starts with node 0 because it has zero incoming edges. Then it processes nodes 1 and 2, which become zero in-degree after removing edges from 0. Finally, node 3 is processed last.

❓ Predict Output

intermediate

Detecting Cycle with Kahn's Algorithm Output

What will be the output of the following code when Kahn's Algorithm is applied to a graph with a cycle?

DSA Javascript

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

function kahnTopologicalSort(graph) {
  const inDegree = {};
  for (const node in graph) {
    inDegree[node] = 0;
  }
  for (const node in graph) {
    for (const neighbor of graph[node]) {
      inDegree[neighbor]++;
    }
  }

  const queue = [];
  for (const node in inDegree) {
    if (inDegree[node] === 0) queue.push(node);
  }

  const topoOrder = [];
  while (queue.length > 0) {
    const current = queue.shift();
    topoOrder.push(current);
    for (const neighbor of graph[current]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  if (topoOrder.length !== Object.keys(graph).length) {
    return "Cycle detected, topological sort not possible";
  }
  return topoOrder;
}

console.log(kahnTopologicalSort(graph));

A ["0", "1", "2"]

B "Cycle detected, topological sort not possible"

C ["2", "1", "0"]

D []

💡 Hint

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

Kahn's Algorithm cannot process all nodes because of the cycle. The queue remains empty after initialization, so the topoOrder is empty and cycle is detected.

🔧 Debug

advanced

Identify the Bug in Kahn's Algorithm Implementation

The following code attempts to perform topological sort using Kahn's Algorithm but produces incorrect output. What is the bug?

DSA Javascript

function kahnTopologicalSort(graph) {
  const inDegree = {};
  for (const node in graph) {
    inDegree[node] = 0;
  }
  for (const node in graph) {
    for (const neighbor of graph[node]) {
      inDegree[node]++;
    }
  }

  const queue = [];
  for (const node in inDegree) {
    if (inDegree[node] === 0) queue.push(node);
  }

  const topoOrder = [];
  while (queue.length > 0) {
    const current = queue.shift();
    topoOrder.push(current);
    for (const neighbor of graph[current]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  return topoOrder;
}

A The graph is not iterated correctly using Object.keys.

B The queue initialization is missing nodes with zero in-degree.

C The topoOrder array is not returned at the end.

D The in-degree increment is done on 'node' instead of 'neighbor' inside the nested loop.

💡 Hint

Check which node's in-degree is incremented inside the nested loop.

The bug is that in-degree is incremented for 'node' instead of 'neighbor'. This causes wrong in-degree counts and incorrect topological order.

🚀 Application

advanced

Order of Courses to Take Using Kahn's Algorithm

Given the course prerequisites graph below, which is a valid order to complete all courses using Kahn's Algorithm?

DSA Javascript

const courses = {
  'Math': ['Physics'],
  'Physics': ['Chemistry'],
  'Chemistry': [],
  'English': ['History'],
  'History': []
};

A ["English", "History", "Math", "Physics", "Chemistry"]

B ["Math", "Physics", "Chemistry", "English", "History"]

C ["History", "English", "Chemistry", "Physics", "Math"]

D ["Physics", "Math", "Chemistry", "History", "English"]

💡 Hint

Start with courses that have no prerequisites and process dependent courses after their prerequisites.

Courses 'English' and 'History' form one chain, and 'Math', 'Physics', 'Chemistry' form another. Both chains can be completed independently. Option A respects prerequisites order.

🧠 Conceptual

expert

Maximum Number of Nodes in Queue at Once in Kahn's Algorithm

In Kahn's Algorithm for topological sorting, what determines the maximum number of nodes that can be in the queue at the same time during execution?

A The maximum out-degree of any node in the graph.

B The total number of nodes in the graph.

C The maximum number of nodes with zero in-degree at any point during the algorithm.

D The length of the longest path in the graph.

💡 Hint

Think about when nodes are added to the queue during the algorithm.

The queue holds nodes with zero in-degree waiting to be processed. The maximum size is the largest set of nodes that simultaneously have zero in-degree.

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