graph

from collections import defaultdict 

class Graph:
	def __init__(self,V):
		self.V = V
		self.adj  = [[] for i in range(V)]

	def addEdge(self,v, w):
		self.adj[v].append(w)

	def DFS(self,s, goal):
		visited = [False for i in range(self.V)]
    
		stack = []
		stack.append(s)
	
		while(len(stack)):
			s = stack[-1]
			stack.pop()
			if (not visited[s]):
				print(s,end=' ')
				visited[s] = True
				if goal == s:
					break
  
			for node in self.adj[s]:
				if (not visited[node]):
					stack.append(node)

	def BFS(self, s, goal):
		visited = [False for i in range(self.V)]

		queue = []
		queue.append(s)
		visited[s] = True

		while queue:
			s = queue.pop(0)
			print(s, end = " ")
			if goal == s:
				break

			for i in self.adj[s]:
				if visited[i] == False:
					queue.append(i)
					visited[i] = True  
  
  
#Main

g = Graph(10);  
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(0, 3)
g.addEdge(1, 4)
g.addEdge(1, 5)
g.addEdge(2, 6)
g.addEdge(3, 7)
g.addEdge(7, 8)
g.addEdge(7, 9)
"""		  0
	   /  \  \
      1    2  3
	 / \   |   \
	4   5  6   7
	          / \
			 8   9
"""    
print("Depth First Search:-")  
g.DFS(0,9)
print("\n")
print("Breadth First Search")
g.BFS(0,9)