Search⌘ K
Home
Courses
Recursion for Coding Interviews in Python

Solution Review 3: Topological Sorting of a Graph

Explore how to use recursion for topological sorting of a graph by traversing vertices, marking them visited, and using a stack to maintain task order. Understand the algorithm and how it ensures dependencies are respected during sorting.

We'll cover the following...

Solution: Using Recursion

Python 3.5
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 beginning with the first node. Since the first node has not been marked visited yet, we call the helperFunction() for it. In the ...