Solution Review 3: Topological Sorting of a Graph

Solution: Using Recursion

Let’s have a look at the algorithm to solve this problem:

function helperFunction(currentNode) {
  // mark currentNode visited
  for (each vertex v that has an edge from currentNode to v) {
    helperFunction(v);
  }
  // push currentNode to head of result
}

function topologicalSort(graph) {
  var result = []; // Empty stack that will contain the sorted vertices

  while there are unvisited vertices do {
    // select an unvisited vertex "currentNode"
    helperFunction(currentNode);
  }
  return(result)
}

The code will be as follows: