Topological Ordering

Given a directed graph, find the topological ordering of its vertices.

Input: Vertices=4, Edges=[3, 2], [3, 0], [2, 0], [2, 1]

Output: Following are the two valid topological sorts for the given graph:

• 3, 2, 0, 1
• 3, 2, 1, 0

function topological_sort(vertices, edges) {
  const sortedOrder = [];
  const inDegree = new Array(vertices).fill(0);
  const graph = new Map();

  // Build the graph and in-degree array
  for (const [parent, child] of edges) {
    if (!graph.has(parent)) {
      graph.set(parent, []);
    }
    graph.get(parent).push(child);
    inDegree[child]++;
  }

  // Initialize sources (vertices with zero in-degree)
  const sources = new Set();
  for (let i = 0; i < vertices; i++) {
    if (inDegree[i] === 0) {
      sources.add(i);
    }
  }

  let visitedCount = 0;

  // Process vertices with zero in-degree
  while (sources.size > 0) {
    const vertex = sources.values().next().value; // Get an arbitrary source

    sources.delete(vertex); // Remove from sources
    sortedOrder.push(vertex);
    visitedCount++;

    if (graph.has(vertex)) {
      console.log(vertex);

      for (const child of graph.get(vertex)) {
        inDegree[child]--;
        if (inDegree[child] === 0) {
          sources.add(child);
        }
      }
    }
  }

  // Check if all vertices are visited
  if (visitedCount !== vertices) {
    return []; // Cycle detected or not all vertices processed
  }

  return sortedOrder;
}

console.log(
  `Topological sort: ${topological_sort(4, [
    [3, 2],
    [3, 0],
    [2, 0],
    [2, 1],
  ])}`,
);

Time Complexity O(V+E)/Space Complexity O(V+E), where ‘V’ is the total number of vertices and ‘E’ is the total number of edges in the graph.