from collections import deque
graph=[
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
def DFS(graph,v,visited):
visited[v]=True
print(v,end=' ')
for i in graph[v]:
if visited[i] != True:
visited[i]=True
DFS(graph,i,visited)
def BFS(graph, v0, visited):
queue=deque([v0])
visited[v0]=True
while queue:
v1=queue.popleft()
print(v1, end=' ')
for i in graph[v1]:
if visited[i] != True:
queue.append(i)
visited[i]=True
visited=[False]*9
print('DFS=')
DFS(graph,1,visited)
print('')
print('BFS=')
BFS(graph,1,visited)
o BFS (Breadth First Search)
from collections import deque
visited = [0]*(n+1)
def BFS(graph, v, visited):
q=deque([v])
visited[v]=True
while q:
v=q.popleft()
print(v, end=" ")
for i in graph[v]:
if visited[v]!=True:
q.append[i]
visited[i]=True
BFS(graph, 1, visited)
o DFS (Depth First Search)
visited = [0]*(n+1)
def DFS(graph, v, visited):
visited[v]=True
print[v, end=" "]
for i in graph[v]:
if not in graph[v]:
def(graph, i, visited)