Topological Sort

Here’s an example implementation of Topological Sort algorithm:


from collections import defaultdict
# making a Class for representing a graph
class Graph:
	def __init__(self, vertices):
    	# dictionary that contains adjacency List
		self.graph = defaultdict(list)
        # number of vertices
		self.V = vertices 
	# function for adding an edge to graph
	def addEdge(self, u, v):
	# A recursive function used by topologicalSort
	def topologicalSortUtil(self, v, visited, stack):
		# Marking the current node as visited.
		visited[v] = True
		for i in self.graph[v]:
			if visited[i] == False:
				self.topologicalSortUtil(i, visited, stack)
		# Pushing current vertex to stack that stores result
	# Topological Sort function.
	def topologicalSort(self):
		# Marking all the vertices as not visited
		visited = [False]*self.V
		stack = []
		# the sort starts from all vertices one by one
		for i in range(self.V):
			if visited[i] == False:
				self.topologicalSortUtil(i, visited, stack)
		# Printing contents of the stack

g = Graph(6)
g.addEdge(5, 2)
g.addEdge(5, 0)
g.addEdge(4, 0)
g.addEdge(4, 1)
g.addEdge(2, 3)
g.addEdge(3, 1)
print ("The topological sort of the given graph is as")