Breadth First Search Algorithm in Python
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.
Learn DSA
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
FAQs
The Breadth First Search Algorithm in Python is a graph traversal technique that visits all nodes at the current depth before moving to the next level. It uses a queue and is ideal for finding the shortest path in unweighted graphs.
Breadth First Search in Python explores neighbors level by level using a queue, while Depth First Search uses a stack (or recursion) to go deep into a path before backtracking. BFS is better for shortest path problems in unweighted graphs.
Breadth First Search in Python is used in GPS navigation systems, social network analysis, web crawlers, and AI for solving puzzles and games, where level wise traversal or shortest path is essential.
To implement the Breadth First Search Algorithm in Python, represent the graph as an adjacency list (dictionary), use a queue to manage nodes to visit, and a set or boolean list to track visited nodes.
The Breadth First Search Algorithm in Python has a time complexity of O(V + E) and space complexity of O(V), where V is vertices and E is edges, making it efficient for traversing large and sparse graphs.
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