algorithms/topo.py at main · jai2dev/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
from collections import defaultdict

class Graph:
	"""docstring for Graph"""
	def __init__(self,ver):
		# super(Graph, self).__init__()
		self.graph = defaultdict(list)
		self.ver=ver

	def addEdge(self,u,v):
		self.graph[u].append(v)

	def topoutil(self,v,visited,stack):

		visited[v]=True

		for i in self.graph[v]:
			if visited[i]==False:
				self.topoutil(i,visited,stack)

		stack.insert(0,v)


	def toppo(self):
		visited=[False]*self.ver
		stack=[]

		for i in range(self.ver):
			if visited[i]==False:
			    self.topoutil(i,visited,stack)

		return stack


if __name__ == '__main__':
	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(g.toppo())