Breadth First Search Algorithm
Introduction to Breadth First Search algorithm
Breadth First Search (BFS) algorithm is a fundamental graph traversal algorithm used to explore and analyze the structure of a graph or tree. It is a systematic method for visiting all the vertices and edges of a graph, starting from a specific source vertex and moving outward in layers.
Breadth First Search is a simple and intuitive algorithm that is primarily used for two main tasks: Exploration of Graphs and Connectivity Analysis.
What is Breadth First Search?
Breadth First Search (BFS) is a graph traversal algorithm used to explore and analyze the structure of a graph or tree.
- It systematically visits all the vertices and edges of a graph, starting from a specific source vertex and moving outward in layers.
- BFS employs a queue data structure to maintain the order of traversal, ensuring that it visits vertices in order of their distance from the source.
- It is often used to find the shortest path in unweighted graphs, perform network analysis, determine graph connectivity, and solve various graph-related problems.
Breadth First Search Algorithm
The algorithm follows these basic steps:
Start with a source vertex.
Initialize a queue (FIFO data structure) to keep track of the vertices to be visited.
Mark the source vertex as visited and enqueue it.
While the queue is not empty, do the following: a. Dequeue a vertex from the queue. b. Visit and process the dequeued vertex. c. Enqueue all the unvisited neighbors of the dequeued vertex.
Continue this process until the queue is empty.
Implementation of BFS
Here’s a Python implementation of the Breadth First Search algorithm for traversing a graph. In this example, we assume the graph is represented as an adjacency list.
from collections import deque
def bfs(graph, start_vertex):
visited = set() # To keep track of visited vertices
queue = deque() # Initialize a queue for BFS
visited.add(start_vertex) # Mark the start_vertex as visited
queue.append(start_vertex) # Enqueue the start_vertex
while queue:
current_vertex = queue.popleft() # Dequeue the vertex and process it
print(current_vertex) # Print or process the current_vertex as needed
for neighbor in graph[current_vertex]:
if neighbor not in visited:
visited.add(neighbor) # Mark the neighbor as visited
queue.append(neighbor) # Enqueue the neighbor
# Define a sample graph as an adjacency list
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
start_vertex = 'A' # Starting vertex for BFS
print("Breadth First Search starting from vertex A:")
bfs(graph, start_vertex)
Output :
Breadth First Search starting from vertex A: A B C D E F
Explanation :
The Python code implements the Breadth First Search (BFS) algorithm for graph traversal. It begins at a specified starting vertex (‘A’ in this case) and explores the graph systematically. A queue is employed to manage the order of exploration, and a set keeps track of visited vertices to prevent revisiting. The code prints or processes each visited vertex and its neighbors. The BFS algorithm ensures that vertices are visited in layers, making it useful for tasks like finding the shortest path.
BFS Algorithm Pseudocode
Pseudocode for the Breadth First Search algorithm:
BFS(graph, start_vertex):
queue = create_queue()
mark start_vertex as visited
enqueue start_vertex into the queue
while the queue is not empty:
current_vertex = dequeue from the queue
process current_vertex
for each unvisited neighbor of current_vertex:
mark neighbor as visited
enqueue neighbor into the queue
Breadth First Search Algorithm in AI
An overview of the Breadth-First Search (BFS) algorithm in the context of Artificial Intelligence (AI):
Applications of Breadth First Search Algorithm
To Wrap it up:
Breadth First Search is a versatile and powerful algorithm for exploring and analyzing graphs. Its simplicity and efficiency make it a fundamental tool in computer science, enabling a wide range of applications, from pathfinding to network analysis and more. Understanding the BFS algorithm is essential for anyone working with graphs or graph-like data structures.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Question 1.
How does BFS differ from Depth First Search (DFS)?
BFS explores a graph layer by layer, while DFS explores one branch as deeply as possible before backtracking. BFS is often used for finding the shortest path, while DFS is used for tasks like topological sorting and cycle detection.
Question 2.
What data structures are commonly used in BFS?
BFS typically uses a queue data structure to maintain the order of traversal and a set (or other data structure) to keep track of visited vertices.
Question 3.
What is the time complexity of BFS?
The time complexity of BFS is O(V + E), where V is the number of vertices, and E is the number of edges in the graph.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment