Question

Language: Python

Create a graph and then set initial and goal states such that the number of nodes visited for BFS is smaller than that in DFS. Now modify the initial and goal state such that the number of nodes visited for BFS is larger than that in DFS.

Answer 1

Consider the following graph:

Two searches are done

0 to 1 and 0 to 4

PYTHON CODE:

def BFS(graph,start,goal):
       n=len(graph[0])
       list=[]
       list.append(start)
       visited=[]
       for i in range(0,n):
              visited.append(False)
       while True:
              count=0
              for i in range(0,n):
                     if visited[i]==True:
                            count=count+1
              if count==n:
                     break
              for i in range(0,n):
                     if visited[i]==False and graph[list[0]][i]==1:
                            list.append(i)
              visited[list[0]]=True
              if list[0]==goal:
                     print("Founded ",goal)
                     return
              else:
                     print("Visited ",list[0])
              list.pop(0)

def DFS(graph,start,goal):
       n=len(graph[0])
       list=[]
       list.append(start)
       visited=[]
       for i in range(0,n):
              visited.append(False)
       while True:
              count=0
              for i in range(0,n):
                     if visited[i]==True:
                            count=count+1
              if count==n:
                     break
              p=list.pop()
              for i in range(0,n):
                     if visited[i]==False and graph[p][i]==1:
                            list.append(i)
              visited[p]=True
              if p==goal:
                     print("Founded ",goal)
                     return
              else:
                     print("Visited ",p)

#Adjacency representation of graph
graph=[[0,1,1,0,0],
       [1,0,0,0,0],
       [1,0,0,1,1],
       [0,0,1,0,0],
       [0,0,1,0,0]]
print("No. of nodes visited in BFS smaller than DFS")
print("BFS")
BFS(graph,0,1)
print("DFS")
DFS(graph,0,1)
print("No. of nodes visited in BFS larger than DFS")
print("BFS")
BFS(graph,0,4)
print("DFS")
DFS(graph,0,4)

OUTPUT: