Search⌘ K
AI Features
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))
...