Breadth-First Search is another algorithm like Depth First Search which is used to search a particular vertex. It is also Known as Breadth-First Traversal because with its help we can traverse through any graph data structures. As we know that all tree structures are graph structures so the BFS algorithm can also be applied to the tree data structure to traverse and finding operations. BFS was initially invented by Konrad Zuse in 1945 and reinvented by Edward F. Moore in1959. The main purpose of inventing the BFS to find the short path between two points or vertices.
What is a Breadth-First Search?
Breadth-First Search is a Searching and Traversing algorithm applied on trees or Graph data structure for search and traversing operation. The main purpose of BFS to find the shortest path between two vertices and many real-world problems work on this algorithm. This algorithm could be implemented using recursive or iterative statements, the recursive implementation could be very tricky so most of the time we implement the BFS using iterative methods. Up to an extent the implementation and algorithm of Breadth-First Search are akin to Depth-First search, the only difference here we use the Queue data structure along with the main BFS algorithm. It is known as breadth-first search because its visiting approach is from left to right, unlike DFS which is top to bottom. There is one more major difference between DFS and BFS, DFS used to explore a node until it reaches its leaf node and then uses backtracking to visit all the explored node, but BFS explore and visit all the node of its neighbour nodes and then move to the next level. The BFS algorithm starts to traversing from the root node and first explore its all neighbouring nodes, then it selects one of the visited nearest nodes and start to explore its all node, the approach of selecting the nearest node make it more effective than DFS to find the shortest path.
BFS Pseudocode:
procedure BFS(G,start_v):
let Q be a queue
label start_v as discovered
Q.enqueue(start_v)
while Q is not empty
v = Q.dequeue()
if v is the goal:
return v
for all edges from v to w in G.adjacentEdges(v) do
if w is not labeled as discovered:
label w as discovered
w.parent = v
Q.enqueue(w)
BFS Algorithm
- Step 1: Define a Queue
- Step 2: Select the root node of the Graph as a starting point for the traversal
- Step 3: Visit all the adjacent node of the root node and inserted them into the Queue.
- Step 4: If the node inserted in the queue has its adjacent nodes than insert them also in the queue from the rear point or else delete the node.
- Step 5: Repeat Step 3 and 4 until the queue becomes empty or the node is founded.
Breadth-First Search Applications
There are many real-world problems have been solved using the Breadth-First Search algorithm.
- Cheney’s algorithm to copying garbage collection
- To find the shortest path between two nodes.
- Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the tree to be reconstructed efficiently.
- Construction of the failure function of the Aho-Corasick pattern matcher.
- Testing bipartiteness of a graph.
BFS Advantages and disadvantages:
Advantages:
- It is more efficient than the DFS algorithm to find out the shortest path between two nodes.
- Always find an Optimal solution
- If there is more than one solution it would find the minimal one.
- It does not visit the useless path, explore nodes level by level.
Disadvantage:
- The main disadvantage of BFS is its memory requirement.
- It takes a lot of time to provide the optimal solution.
Breadth-First Search for Graph Implementation:
Python:
from collections import defaultdict
class Graph:
# Constructor
def __init__(self):
self.graph = defaultdict(list)
def addEdge(self,u,v):
self.graph[u].append(v)
def BFS(self, s):
visited = [False] * (len(self.graph))
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() # Create a 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 ("BFS Traverses")
g.BFS(1)
Output
BFS Traverses 1 2 0 3
People are also reading: