Topological Sort

Topological Sort of a directed graph is a linear ordering of its vertices such that for every directed edge (U, V) from vertex U to vertex v , U comes before V in the 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 
1) 3, 2, 0, 1
2) 3, 2, 1, 0

The basic idea behind the topological sort is to provide a partial ordering among the vertices of the graph such that if there is an edge from U to V , then U ≤ V. Here are a few fundamental concepts related to topological sort:

• 1 Source: Any node that has no incoming edge and has only outgoing edge is called a source
• 2 Sink: Any node that has only incoming edges and no outgoing edge is called a sink
• 3 We can say that a topological ordering starts with one of the sources and ends at one of the sinks
• 4 A topological ordering is possible only when the graph has no directed cycles. i.e if the graph is a Directed Acyclic Graph. If the graph has a cycle, some vertices will have cyclic dependencies which makes it impossible to find a linear ordering among vertices.

To find the topological sort of a graph we can traverse the graph in a Breadth First Search (BFS) way. We will start with all the sources, and in a stepwise fashion, save all sources to a sorted list. We will then remove all sources and their edges from the graph. After the removal of the edges, we will have new sources, so we will repeat the above process until all vertices are visited.

function topologicalSort(vertices, edges) {
  const sortedOrder = [];
  if (vertices <= 0) {
    return sortedOrder;
  }
// a. Initialize the graph
  const inDegree = Array(vertices).fill(0);
  const graph = Array(vertices).fill(0).map(() => Array());
// b. Build the graph
  edges.forEach(edge => {
    let parent = edge[0];
    let child = edge[1];
    graph[parent].push(child);
    inDegree[child]++;
  });
// c. Find all sources
  const sources = [];
  for (let i = 0; i < inDegree.length; i++) {
    if (inDegree[i] === 0) {
      sources.push(i);
    }
  }
// d. For each source, add it to the sortedOrder and subtract one from all all of its children's in-degrees
// if a child's in-degree becomes zero, add it to the sources queue
while (sources.length > 0) {
  const vertex = sources.shift();
  sortedOrder.push(vertex);
  graph[vertex].forEach(child => {
    inDegree[child] -= 1;
    if (inDegree[child] === 0) {
      sources.push(child);
    }
  });
}
if (sortedOrder.length !== vertices) {
  return [];
}
return sortedOrder;
}