Topological sort in TS

topSort.ts

function transposeGraph(arr: number[][]) {
	const graph: Map<number, number[]> = new Map();

	for (let index = 0; index < arr.length; index++) {
		if (!graph.has(index)) {
			graph.set(index, []);
		}

		const deps = arr[index];
		for (const dep of deps) {
			if (!graph.has(dep)) {
				graph.set(dep, []);
			}

			graph.get(dep)!.push(index);
		}
	}

	return graph;
}

function topologicalSort(arr: number[][]) {
	const graph = transposeGraph(arr);

	const indegrees = [...arr].map((deps) => deps.length);
	const zeroIndegree = indegrees.reduce((acc, length, index) => {
		if (length === 0) acc.push(index);
		return acc;
	}, [] as number[]);

	const order = [] as number[];

	while (zeroIndegree.length !== 0) {
		const node = zeroIndegree.pop()!;
		order.push(node);

		for (const neighbor of graph.get(node)!) {
			indegrees[neighbor] -= 1;
			if (indegrees[neighbor] === 0) {
				zeroIndegree.push(neighbor);
			}
		}
	}

	return order;
}

const sorted = topologicalSort([[2], [3], [], [0, 2], [3, 6], [3, 2], [5, 1]])
console.log(sorted); // [2, 0, 3, 5, 1, 6, 4]