DFS.py

from collections import defaultdict

class Graph():

	#initial declaration 
	def __init__(self):
		self.graph = defaultdict(list)

	#add edge between two vertices
	def addedge(self,src,dist):
		#output of the graph look like
		#defaultdict(<type 'list'>, {0: [2, 1], 1: [2], 2: [0, 3, 4], 3: [3], 4: [5], 5: [6]})
		self.graph[src].append(dist)
		
	#DFS
	def DFS(self,src):
		#to keep track of visited list
		visited = [False]*(len(self.graph))
		#create queue for DFS traversal
		queue = []
		#main logic starts here
		queue.append(src)

		visited[src] = True

		while queue:
			src = queue.pop(0)
			print(src)
			for i in self.graph[src]:
				#if not visited take the connection
				if visited[i] == False:
					queue.append(i)
					visited[i] = True

if __name__ == '__main__':
	#graph
	g = Graph()

	print("The format of the graph look like:\n")

 	g.addedge(0,2)
 	g.addedge(0,1)
 	g.addedge(2,0)
 	g.addedge(1,2)
 	g.addedge(2,3)
 	g.addedge(3,3)
 	g.addedge(2,4)
 	g.addedge(4,5)
 	g.addedge(5,6)
 	#DFS
 	#graph start from 2
 	print("Depth First Traversal Algorithm is:\n")
 	g.DFS(2)