Solution Review 3: Topological Sorting of a Graph

This review provides a detailed analysis of the solution to topologically sort a graph.

We'll cover the following

Solution: Using Recursion

Press + to interact
main.py
graph.py
import graph as g
def helperFunction(myGraph, currentNode, visited, result) :
  visited[currentNode] = True # Mark the current node as visited
  
  # Recur for all the adjacent vertices of currentNode
  for i in myGraph.graph[currentNode] :
    if visited[i] == False :
      helperFunction(myGraph, i, visited, result)
  
  result.insert(0, currentNode) # Push current vertex to result
  
  
def topologicalSort(myGraph) :
  visited = [False] * myGraph.vertices  # Mark all the vertices as not visited
  result = [] # Our stack to store the result/output
  for currentNode in range(myGraph.vertices) :
    if visited[currentNode] == False :
      helperFunction(myGraph, currentNode, visited, result)
  return(result)
# Driver code 
# Create a graph given in the above diagram 
myGraph = g.Graph(5) 
myGraph.addEdge(0, 1) 
myGraph.addEdge(0, 3) 
myGraph.addEdge(1, 2) 
myGraph.addEdge(2, 3) 
myGraph.addEdge(2, 4) 
myGraph.addEdge(3, 4) 
print("Topological Sort")
print(topologicalSort(myGraph))

Explanation

We traverse the given graph starting from the first node. Since it is not visited, we call the helperFunction() for it.

In the helperFunction() this node is marked as visited and then we recursively call the helperFunction() for its adjacent but unvisited vertices.

In topological sorting, we use a temporary stack, in our case the variable result. We do not print the vertex immediately but after all its adjacent vertices have been visited. This is because each adjacent vertex implies that this task needs to be performed before the current task. Here, the stack data structure helps us keeping that order

A vertex is pushed to stack only when all of its adjacent vertices are already in the stack.

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

def helperFunction(u)
    # mark u visited
    for each vertex i with an edge from u to i
        helperFunction(i)

    # push u to head of result

def topologicalSort(graph)

  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 pseudocode can be mapped to the visualization below:

In the next lesson, we have a short quiz to test your concepts.