Sep 28, 2025
diff --git a/Graphs/Kahn.js b/Graphs/Kahn.js
 /*
  Source:
    https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm
 */

 /*
   Kahn's Algorithm for Topological Sorting
   ----------------------------------------
   Works only on Directed Acyclic Graphs (DAGs).
   Idea:
    1. Compute indegree (number of incoming edges) for each node.
    2. Start with nodes having indegree = 0 (no dependencies).
    3. Repeatedly remove nodes with indegree = 0 and reduce indegree of their neighbors.
    4. If all nodes are processed, we have a valid topological order.
    5. If not, graph has a cycle.

   Time Complexity: O(V + E)  (V = vertices, E = edges)
   Space Complexity: O(V + E)
 */

 const KahnsAlgorithm = (numNodes, edges) => {
  // Input:
  //   numNodes: number of vertices in the graph (0..numNodes-1)
  //   edges: list of directed edges [u, v] meaning u -> v
  // Output:
  //   topoOrder: array of vertices in topological order
  //              OR empty array if graph contains a cycle

  // Step 1: Build adjacency list and indegree array
  const adj = Array.from({ length: numNodes }, () => [])
  const indegree = Array(numNodes).fill(0)

  for (const [u, v] of edges) {
    adj[u].push(v)
    indegree[v]++
  }

  // Step 2: Initialize queue with all nodes having indegree = 0
  const queue = []
  for (let i = 0; i < numNodes; i++) {
    if (indegree[i] === 0) queue.push(i)
  }

  const topoOrder = []

  // Step 3: Process queue
  while (queue.length > 0) {
    const node = queue.shift()
    topoOrder.push(node)

    for (const neighbor of adj[node]) {
      indegree[neighbor]--
      if (indegree[neighbor] === 0) {
        queue.push(neighbor)
      }
    }
  }

  // Step 4: Verify if topological order includes all nodes
  return topoOrder.length === numNodes ? topoOrder : []
 }

 export { KahnsAlgorithm }
diff --git a/Graphs/test/Kahn.test.js b/Graphs/test/Kahn.test.js
 import { KahnsAlgorithm } from '../Kahn.js'

 // Check if a given order is a valid topological sort
 function isValidTopologicalOrder(order, numNodes, edges) {
  if (order.length !== numNodes) return false

  const position = new Map()
  order.forEach((node, idx) => position.set(node, idx))

  for (const [u, v] of edges) {
    // u must come before v in topo order
    if (position.get(u) > position.get(v)) return false
  }
  return true
 }

 test('Test Case 1', () => {
  const numNodes = 6
  const edges = [
    [5, 2],
    [5, 0],
    [4, 0],
    [4, 1],
    [2, 3],
    [3, 1]
  ]
  const topoOrder = KahnsAlgorithm(numNodes, edges)

  expect(isValidTopologicalOrder(topoOrder, numNodes, edges)).toBe(true)
 })

 test('Test Case 2', () => {
  const numNodes = 4
  const edges = [
    [0, 1],
    [1, 2],
    [2, 3]
  ]
  const topoOrder = KahnsAlgorithm(numNodes, edges)

  // Only one valid order exists
  expect(topoOrder).toStrictEqual([0, 1, 2, 3])
 })

 test('Test Case 3 (Cycle Detection)', () => {
  const numNodes = 3
  const edges = [
    [0, 1],
    [1, 2],
    [2, 0]
  ]
  const topoOrder = KahnsAlgorithm(numNodes, edges)

  expect(topoOrder).toStrictEqual([])
 })
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,63 @@
		/*
		Source:
		https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm
		*/

		/*
		Kahn's Algorithm for Topological Sorting
		----------------------------------------
		Works only on Directed Acyclic Graphs (DAGs).
		Idea:
		1. Compute indegree (number of incoming edges) for each node.
		2. Start with nodes having indegree = 0 (no dependencies).
		3. Repeatedly remove nodes with indegree = 0 and reduce indegree of their neighbors.
		4. If all nodes are processed, we have a valid topological order.
		5. If not, graph has a cycle.

		Time Complexity: O(V + E) (V = vertices, E = edges)
		Space Complexity: O(V + E)
		*/

		const KahnsAlgorithm = (numNodes, edges) => {
		// Input:
		// numNodes: number of vertices in the graph (0..numNodes-1)
		// edges: list of directed edges [u, v] meaning u -> v
		// Output:
		// topoOrder: array of vertices in topological order
		// OR empty array if graph contains a cycle

		// Step 1: Build adjacency list and indegree array
		const adj = Array.from({ length: numNodes }, () => [])
		const indegree = Array(numNodes).fill(0)

		for (const [u, v] of edges) {
		adj[u].push(v)
		indegree[v]++
		}

		// Step 2: Initialize queue with all nodes having indegree = 0
		const queue = []
		for (let i = 0; i < numNodes; i++) {
		if (indegree[i] === 0) queue.push(i)
		}

		const topoOrder = []

		// Step 3: Process queue
		while (queue.length > 0) {
		const node = queue.shift()
		topoOrder.push(node)

		for (const neighbor of adj[node]) {
		indegree[neighbor]--
		if (indegree[neighbor] === 0) {
		queue.push(neighbor)
		}
		}
		}

		// Step 4: Verify if topological order includes all nodes
		return topoOrder.length === numNodes ? topoOrder : []
		}

		export { KahnsAlgorithm }
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,55 @@
		import { KahnsAlgorithm } from '../Kahn.js'

		// Check if a given order is a valid topological sort
		function isValidTopologicalOrder(order, numNodes, edges) {
		if (order.length !== numNodes) return false

		const position = new Map()
		order.forEach((node, idx) => position.set(node, idx))

		for (const [u, v] of edges) {
		// u must come before v in topo order
		if (position.get(u) > position.get(v)) return false
		}
		return true
		}

		test('Test Case 1', () => {
		const numNodes = 6
		const edges = [
		[5, 2],
		[5, 0],
		[4, 0],
		[4, 1],
		[2, 3],
		[3, 1]
		]
		const topoOrder = KahnsAlgorithm(numNodes, edges)

		expect(isValidTopologicalOrder(topoOrder, numNodes, edges)).toBe(true)
		})

		test('Test Case 2', () => {
		const numNodes = 4
		const edges = [
		[0, 1],
		[1, 2],
		[2, 3]
		]
		const topoOrder = KahnsAlgorithm(numNodes, edges)

		// Only one valid order exists
		expect(topoOrder).toStrictEqual([0, 1, 2, 3])
		})

		test('Test Case 3 (Cycle Detection)', () => {
		const numNodes = 3
		const edges = [
		[0, 1],
		[1, 2],
		[2, 0]
		]
		const topoOrder = KahnsAlgorithm(numNodes, edges)

		expect(topoOrder).toStrictEqual([])
		})