Breadth First Search & Depth First Search Algorithm

Breadth First Search (BFS)

Problem Statement:

Implement depth first search algorithm and Breadth First Search algorithm, Use an undirected

graph and develop a recursive algorithm for searching all the vertices of a graph or tree data

structure.

Objectives:

1. To study the various Search Algorithms.

2. To study the depth first search algorithm.

3. To study the breadth first search algorithm.

Theory:

Uninformed Search Algorithms:

The search algorithms in this section have no additional information on the goal node other

than the one provided in the problem definition. The plans to reach the goal state from the start

state differ only by the order and/or length of actions. Uninformed search is also called Blind

search.The following uninformed search algorithms are discussed in this section.

1. Depth First Search

2. Breadth First Search

3. Uniform Cost Search 

Each of these algorithms will have: 

 A problem graph, containing the start node S and the goal node G. 

 A strategy, describing the manner in which the graph will be traversed to get to G. 

 A fringe, which is a data structure used to store all the possible states (nodes) that you cango from the current states. 

 A tree that results while traversing to the goal node.

 A solution plan, which the sequence of nodes from S to G. 

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a‘search key’), and explores all of the neighbor nodes at the present depth prior to moving on tothe nodes at the next depth level. 

d = the depth of the shallowest 

solution.n i = number of nodes in level . 

Algorithm/Flowchart:

Step 1 – Insert start node in Queue, mark it visited.
Step 2 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a
queue.
Step 3 − If no adjacent vertex is found, remove the first vertex from the queue.
Step 4 − Repeat Step 3 and Step 4 until the queue is empty.

 from collections import defaultdict  
 class Graph:  
   def __init__(self):  
     self.graph = defaultdict(list)  
   def addEdge(self,u,v):  
     self.graph[u].append(v)  
   def BFS(self, s):  
     visited = [False] * (max(self.graph) + 1)  
     queue = []  
     queue.append(s)  
     visited[s] = True  
     while queue:  
       s = queue.pop(0)  
       print (s, end = " ")  
       for i in self.graph[s]:  
         if visited[i] == False:  
           queue.append(i)  
           visited[i] = True  
 g = Graph()  
 g.addEdge(0, 1)  
 g.addEdge(0, 2)  
 g.addEdge(1, 2)  
 g.addEdge(2, 0)  
 g.addEdge(2, 3)  
 g.addEdge(3, 3)  
 print ("Following is Breadth First Traversal"  
          " (starting from vertex 2)")  
 g.BFS(2)  

Depth First Search:

Depth First Search: Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case ofa graph) and explores as far as possible along each branch before backtracking. 

Algorithm/Flowchart:

Step 1 – Push a starting node on stack, mark it visited. 

Step 2 - Visit the adjacent unvisited vertex of start node. Mark it as visited. Display it. Pushit in a stack. Step 3 − If no adjacent vertex is found, pop up a vertex from the stack. Repeat Step 2 

Step 4 − Repeat Step 2 and Step 3 until the stack is empty.

Conclusion: We have successfully implemented depth first search and breadth first search algorithm for a graph.

 from collections import defaultdict  
 class Graph:  
   def __init__(self):  
     self.graph = defaultdict(list)  
   def addEdge(self, u, v):  
     self.graph[u].append(v)  
   def DFSUtil(self, v, visited):  
     visited.add(v)  
     print(v, end=' ')  
     for neighbour in self.graph[v]:  
       if neighbour not in visited:  
         self.DFSUtil(neighbour, visited)  
   def DFS(self, v):  
     visited = set()  
     self.DFSUtil(v, visited)  
 g = Graph()  
 g.addEdge(0, 1)  
 g.addEdge(0, 2)  
 g.addEdge(1, 2)  
 g.addEdge(2, 0)  
 g.addEdge(2, 3)  
 g.addEdge(3, 3)  
 print("Following is DFS from (starting from vertex 2)")  
 g.DFS(2)