Breadth First Search Algorithm: Concepts, Applications, and Examples
Updated on Feb 26, 2025 | 27 min read | 7.4k views
Share:
For working professionals
For fresh graduates
More
Updated on Feb 26, 2025 | 27 min read | 7.4k views
Share:
Table of Contents
The Breadth First Search (BFS) algorithm is a fundamental graph traversal technique used to explore nodes and edges systematically. BFS operates by visiting all nodes at the current depth level before moving to the next level. It is an essential tool in various applications like shortest path finding and level-order traversal.
This blog gets into the breadth-first search algorithm, its step-by-step process, and its pivotal role in fields such as AI, where BFS is leveraged for problem-solving and state exploration. Learn how the BFS algorithm in AI is applied through practical examples and real-world scenarios!
The breadth first search algorithm (BFS) systematically explores graphs by visiting all nodes at the current level before moving to the next. This makes BFS ideal for finding the shortest path in unweighted graphs. It can operate on directed, undirected, weighted, and unweighted graphs, ensuring flexibility in its application.
Let us have a closer look at some of the major plus points of BFS:
Importance of Breadth First Search (BFS)
Breadth First Search’s (BFS) structured approach ensures thorough exploration, making it highly effective in a variety of applications.
Below are the key aspects that highlight its importance:
BFS’s structured and predictable approach makes it indispensable for both theoretical graph problems and practical applications across industries.
With a clear understanding of the BFS algorithm, it’s important to step back and explore the broader concept of graph traversal, its basics, and how BFS fits into the larger picture.
Graph traversal systematically visits all graph nodes and is key to searching, finding optimal paths, and analyzing graph structures. It underpins algorithms for tasks like navigating networks and solving puzzles.
There are two types of graph traversals:
Types of Graph Traversal
Graph traversal can be broadly categorized into two main types, each with its unique approach and use cases:
Understanding these traversal techniques provides the groundwork for tackling complex graph-based problems effectively.
Why BFS is Important in Graph Theory?
BFS is vital in graph theory for its level-by-level traversal, ensuring all nodes are explored. It guarantees the shortest path in unweighted graphs, making it ideal for routing and pathfinding. Its versatility ensures it can address challenges in diverse graph-based systems..
Also Read: Top 10 Data Visualization Techniques for Successful Presentations
With its versatility and efficiency, BFS extends beyond graph theory into real-world applications. Let’s explore how BFS is utilized in AI to solve complex problems.
The Breadth First Search (BFS) algorithm is a key tool in AI, used as an uninformed search method for systematic state exploration. Its level-by-level traversal makes it ideal for decision-making and pathfinding problems.
Some applications of the BFS algorithm in AI include:
BFS can be used for parsing sentences in natural language processing, where the algorithm traverses the sentence structure to identify dependencies and relationships between words.
In AI-driven games, BFS helps characters find the shortest path to a target, such as navigating through a maze or a game map.
BFS is used by search engines to systematically crawl websites, ensuring that all links are visited in an organized manner, starting from the root page and moving through all subsequent pages.
Also Read: Types of Graphs in Data Structure & Applications
Now that you understand how BFS is applied in AI let’s delve into why it’s such a critical algorithm for solving complex AI problems and ensuring efficient decision-making.
The BFS algorithm is essential in AI for solving problems requiring systematic exploration and guaranteed solutions. Its structured traversal ensures reliability in applications like pathfinding, puzzles, and network analysis, making it key to efficient AI systems.
Key Reasons for BFS's Importance in AI include:
Also Read: Computer Networking Basics: Network Types, Technologies, Topologies, Pros and Cons
Understanding the structured rules of BFS is crucial, as they directly contribute to its effectiveness in applications such as pathfinding and decision-making in AI. Let’s explore these rules step by step.
The breadth first search algorithm (BFS) operates under a structured set of rules to ensure efficient and systematic traversal of a graph. These rules maintain the order of exploration, prevent redundant processing, and guarantee complete traversal.
Here’s a detailed breakdown:
Rules for BFS Algorithm
Visual Example Graph:
A
/ \
B C
/ \
D E
Queue Progression:
Traversal Order: A → B → C → D → E
Now that you know the rules of BFS, let’s see how the algorithm works in practice with a step-by-step guide to implementing it effectively.
The breadth first search algorithm (BFS) traverses graphs level by level, starting from a source node and systematically exploring all its neighbors before moving to the next level. This approach ensures that the shortest path in an unweighted graph is found. Here’s a step-by-step guide to understanding how BFS works.
Steps to Perform BFS
1. Initialize the Data Structures
Set up the necessary data structures to keep track of the traversal process:
2. Start with the Source Node
Choose a starting node and initialize the traversal.
3. Dequeue and Explore Neighbors
Process the node at the front of the queue:
4. Repeat for All Levels
Continue processing each node level by level:
5. Terminate When Queue is Empty
Stop the traversal once the queue is empty, indicating that all nodes have been visited.
Final State:
Now that you understand the step-by-step process of how BFS works let’s see it in action with a practical example to solidify the concept.
To understand how the breadth first search algorithm (BFS) works, let’s walk through a simple example using a graph. BFS systematically traverses the graph level by level, visiting all nodes at the current depth before moving to the next.
Sample Graph
1
/ \
2 3
/ \
4 5
Step-by-Step BFS Walkthrough
Final Output
The BFS traversal order is: 1 → 2 → 3 → 4 → 5.
How the Queue Changes at Each Step
Step |
Queue |
Visited Nodes |
Processed Node |
1 | [1] | {1} | None |
2 | [2, 3] | {1, 2, 3} | 1 |
3 | [3, 4] | {1, 2, 3, 4} | 2 |
4 | [4, 5] | {1, 2, 3, 4, 5} | 3 |
5 | [] | {1, 2, 3, 4, 5} | 4, 5 |
Python Code Example
Here is an example of the same using Python.
from collections import deque
# Define the graph
graph = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['E'],
'D': [],
'E': []
}
def bfs(graph, start):
visited = set()
queue = deque([start])
order = []
while queue:
node = queue.popleft()
if node not in visited:
visited.add(node)
order.append(node)
queue.extend(graph[node])
return order
# Perform BFS
print("BFS Order:", bfs(graph, 'A'))
Output:
BFS Order: ['A', 'B', 'C', 'D', 'E']
Python Code Example: BFS Explanation
The visited set ensures that each node is processed only once, preventing infinite loops and unnecessary reprocessing of nodes. By checking if a node is in the visited set before processing it, we ensure efficient and correct traversal.
Result:
For the given graph, BFS starts at A and visits nodes in the order: A → B → C → D → E. This ensures all nodes are explored level by level.
Now that you’ve seen how BFS works with an example let’s break down its efficiency by exploring its time and space complexity.
Understanding the complexity of the breadth first search algorithm (BFS) is crucial for evaluating its efficiency, especially when applied to large graphs. BFS’s performance depends on the number of nodes and edges, as well as the data structures used for traversal.
Here’s a breakdown of its time and space complexity.
Time Complexity
The time complexity of BFS is determined by the total number of nodes (V) and edges (E) in the graph:
O(V+E)
This makes BFS highly efficient for graphs with sparse connections and manageable for densely connected graphs.
Example: In a graph with 5 nodes and 4 edges, BFS processes 5 nodes and 4 edges, making it run in O(5+4)=O(9)
Space Complexity
The space complexity of BFS is:
O(V)
This means BFS requires memory proportional to the number of nodes, making it suitable for graphs with moderate sizes but potentially memory-intensive for very large graphs.
Example: For a graph with 5 nodes, BFS may store up to 5 nodes in the queue and visited set, requiring O(5) space.
Now that the complexity of BFS has been analyzed, let’s look at its pseudocode to understand how the algorithm is structured and implemented.
The breadth first search algorithm (BFS) uses a queue to explore nodes level by level. Here’s the step-by-step pseudocode for BFS:
Pseudocode in Steps
BFS(Graph, StartNode):
Initialize Queue with StartNode
Mark StartNode as Visited
While Queue is not Empty:
Node = Dequeue()
Process(Node)
For each Neighbor of Node:
If Neighbor is not Visited:
Mark Neighbor as Visited
Enqueue(Neighbor)
Explanation of BFS Pseudocode
How BFS Visits Nodes
Here is a quick look at how BFS visits nodes:
Example Table:
Step |
Queue |
Visited Nodes |
Processed Node |
1 | [A] | {A} | None |
2 | [B, C] | {A, B, C} | A |
3 | [C, D] | {A, B, C, D} | B |
4 | [D, E] | {A, B, C, D, E} | C |
5 | [] | {A, B, C, D, E} | D, E |
With the pseudocode in mind, it’s helpful to compare BFS with Depth First Search (DFS) to understand their differences and where each is best applied.
Breadth First Search (BFS) and Depth First Search (DFS) are fundamental graph traversal algorithms with distinct approaches and applications. Understanding their differences is crucial for choosing the right method based on the problem at hand.
Below are the key aspects that set them apart and guide their usage.
Key Differences
Also Read: DFS vs BFS: Difference Between DFS and BFS
Now that you know the differences between BFS and DFS, let’s explore when to use each algorithm based on specific problem requirements.
When to Use BFS Over DFS
Example Problem
Use Cases Where BFS is Better Suited Compared to DFS
BFS is ideal for scenarios where exploring nodes level by level is critical.
Along with these, there are cases where DFS may fail but BFS succeeds. Let’s explore those situations.
Scenarios Where DFS Fails but BFS Succeeds
In some cases, DFS struggles, while BFS guarantees optimal outcomes due to its level-wise nature.
Understanding the differences between BFS and DFS lays the foundation for evaluating the specific strengths and limitations of BFS as an algorithm.
The breadth first search algorithm (BFS) is widely recognized for its versatility and systematic approach. However, like any algorithm, it comes with specific strengths and limitations.
Let’s have a look at the pros and cons of BFS.
Advantages of BFS
BFS is a robust algorithm with several features that make it highly effective for many graph traversal problems. Here are some of these features:
While BFS offers several advantages in terms of systematic traversal and completeness, it’s important to also consider its limitations. Let’s take a look at some of the disadvantages of BFS.
Disadvantages of BFS
Despite its strengths, BFS has notable limitations that affect its performance in certain scenarios:
Also Read: Graphs in Data Structure: Types, Storing & Traversal
Having explored the pros and cons of BFS, let’s delve into its real-world applications to see how it’s used across various domains.
BFS is a foundational graph traversal technique in computer science, ideal for problems requiring systematic exploration and guaranteed solutions.
Here are its key applications:
1. Shortest Path in Unweighted Graphs:
BFS ensures the shortest path between two nodes by exploring all paths level by level.
Example: Finding the shortest route between cities with roads of equal weight to optimize travel or delivery.
2. Solving Puzzles:
BFS guarantees the optimal solution in puzzles like the 8-puzzle or Rubik’s Cube by exploring all moves systematically.
Example: Generating valid board configurations in the 8-puzzle to find the shortest move sequence.
3. Web Crawling:
BFS explores links level by level, efficiently indexing pages closest to the start first.
Example: Indexing a website starting from its homepage for comprehensive coverage.
4. Social Network Analysis:
BFS identifies shortest paths, connections, and key influencers in social networks.
Example: Finding the shortest path between users on LinkedIn or detecting influential individuals.
5. Graph Connectivity:
BFS algorithm checks if all nodes are connected or identifies components in disconnected graphs.
Example: Ensuring communication networks are fully connected or locating isolated sub-networks.
6. BFS in Social Media Recommendation Systems:
BFS helps recommend friends or content by exploring social network connections level by level.
Example: BFS suggests new followers based on mutual connections.
7. BFS for Emergency Response Systems:
BFS identifies the shortest evacuation routes to ensure quick and safe paths during emergencies.
Example: BFS finds the quickest exit route during a fire evacuation.
Also Read: Top 26 Web Scraping Projects for Beginners and Professionals
To maximize the benefits of BFS in practical scenarios, it’s essential to follow best practices for its efficient implementation. Let’s explore these in detail.
Implementing BFS effectively requires thoughtful design and optimization, especially when dealing with large graphs or complex networks. Following these best practices ensures that BFS runs reliably, efficiently, and scales well with different types of input data.
1. Use a Queue for Exploration
BFS relies on a queue (FIFO structure) to maintain the order of nodes for level-by-level traversal.
Why: A queue ensures nodes are explored systematically in the correct sequence.
Example: Start with the source node in the queue and add neighbors as you process each node.
2. Track Visited Nodes
Maintain a set or boolean array to track visited nodes, ensuring that nodes are not revisited.
Why: This avoids infinite loops, especially in cyclic graphs, and reduces redundant processing.
Example: Mark a node as visited before enqueuing it.
3. Use an Adjacency List
Represent the graph with an adjacency list instead of an adjacency matrix for sparse graphs.
Why: Adjacency lists are more memory-efficient for graphs with fewer edges.
Example: Store each node’s neighbors in a dictionary or list format.
4. Optimize Space Complexity
Minimize the memory footprint by using lightweight data structures and storing only essential information.
Why: BFS can be memory-intensive, especially for large graphs with many levels or nodes.
Example: For large graphs, consider storing edges dynamically rather than preloading the entire graph.
5. Stop Early if Possible
Terminate the BFS traversal as soon as the target node is found in specific use cases like pathfinding.
Why: Saves unnecessary computation and speeds up the process.
Example: Stop searching once the shortest path to the target is identified.
6. Handle Edge Cases
Account for scenarios like disconnected graphs, empty graphs, or cycles during implementation.
Why: Ensures robustness and prevents errors in edge cases.
Example: Check for isolated nodes before starting traversal or handle graphs with no edges appropriately.
By adhering to these practices, BFS becomes a powerful, scalable tool capable of handling complex problems in graph theory, AI, and computational tasks.
With these best practices in mind, let’s put your understanding to the test with some practice problems designed to strengthen your BFS implementation skills.
Now that you’re familiar with BFS, it’s time to apply your knowledge through practical problems. Below are some BFS-related questions designed to enhance your understanding and problem-solving skills.
Problem:
Given a grid representing a map of cloudy (0) and sunny (1) days, determine the minimum number of days required to reach the first sunny day from any cloudy day using BFS.
Code:
from collections import deque
def min_days_to_sunny(grid):
rows, cols = len(grid), len(grid[0])
queue = deque([(r, c) for r in range(rows) for c in range(cols) if grid[r][c] == 1])
visited = set(queue)
days = 0
while queue:
for _ in range(len(queue)):
r, c = queue.popleft()
for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited and grid[nr][nc] == 0:
queue.append((nr, nc))
visited.add((nr, nc))
days += 1
return days if len(visited) == rows * cols else -1
# Example Grid
grid = [
[0, 0, 1],
[0, 0, 0],
[1, 0, 0]
]
print(min_days_to_sunny(grid)) # Output: 2
Output:
2
Diagram:
Day |
Queue |
Visited |
Updated Grid |
0 | [(0, 2), (2, 0)] | {A, C} | 0 0 1 → 0 1 1 |
1 | [(1, 2), (0, 1), (1, 0)] | {A, B, C, D} | 1 1 1 → |
2 | [(1, 1), (0, 0)] | {A, B, C, D, E} |
Explanation:
Problem:
In a city with several stations connected by roads, find the minimum number of transfers required to travel from station A to station B. Each station is connected to others.
Code:
from collections import deque
def min_transfers_to_target(stations, roads, start, target):
graph = {i: [] for i in range(1, stations + 1)}
for road in roads:
graph[road[0]].append(road[1])
graph[road[1]].append(road[0])
visited = [False] * (stations + 1)
queue = deque([(start, 0)]) # (station, number of transfers)
visited[start] = True
while queue:
station, transfers = queue.popleft()
if station == target:
return transfers
for neighbor in graph[station]:
if not visited[neighbor]:
visited[neighbor] = True
queue.append((neighbor, transfers + 1))
return -1 # Target station is unreachable
# Example: City with 5 stations and 6 roads
stations = 5
roads = [(1, 2), (2, 3), (3, 4), (4, 5), (2, 5), (3, 5)]
start = 1
target = 5
print(min_transfers_to_target(stations, roads, start, target)) # Output: 2
Output:
2
Diagram:
1 -- 2 -- 3 -- 4
\ /
5
Explanation:
Problem:
You are given a network of friends, where each friend is connected to others. Find the quickest way to meet a friend located a certain distance away using BFS.
Code:
from collections import deque
def min_connections_to_friend(friends, connections, start, target):
graph = {i: [] for i in range(1, friends + 1)}
for conn in connections:
graph[conn[0]].append(conn[1])
graph[conn[1]].append(conn[0])
visited = [False] * (friends + 1)
queue = deque([(start, 0)]) # (friend, number of connections)
visited[start] = True
while queue:
friend, connections_count = queue.popleft()
if friend == target:
return connections_count
for neighbor in graph[friend]:
if not visited[neighbor]:
visited[neighbor] = True
queue.append((neighbor, connections_count + 1))
return -1 # Target friend is unreachable
# Example: 5 friends, connections between them
friends = 5
connections = [(1, 2), (2, 3), (3, 4), (4, 5)]
start = 1
target = 5
print(min_connections_to_friend(friends, connections, start, target)) # Output: 4
Output:
4
Diagram:
1 -- 2 -- 3 -- 4 -- 5
Explanation:
Problem:
A vaccine is distributed among several cities connected by roads. Determine the minimum number of days required to distribute the vaccine to all cities, considering one city can distribute it to its neighbors in one day.
Code:
from collections import deque
def min_days_to_distribute_vaccine(cities, roads, start):
graph = {i: [] for i in range(1, cities + 1)}
for road in roads:
graph[road[0]].append(road[1])
graph[road[1]].append(road[0])
visited = [False] * (cities + 1)
queue = deque([(start, 0)]) # (city, number of days)
visited[start] = True
max_days = 0
while queue:
city, days = queue.popleft()
max_days = max(max_days, days)
for neighbor in graph[city]:
if not visited[neighbor]:
visited[neighbor] = True
queue.append((neighbor, days + 1))
return max_days
# Example: 5 cities and 5 roads
cities = 5
roads = [(1, 2), (2, 3), (3, 4), (4, 5)]
start = 1
print(min_days_to_distribute_vaccine(cities, roads, start)) # Output: 4
Output:
4
Diagram:
1 -- 2 -- 3 -- 4 -- 5
Explanation:
Problem:
Given a binary grid (0’s and 1’s), flip all the 0’s to 1’s with the minimum number of flips by flipping a connected region of cells in one move.
Code:
from collections import deque
def min_flips_to_flip_grid(grid):
rows, cols = len(grid), len(grid[0])
visited = set()
queue = deque()
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
queue.append((r, c))
visited.add((r, c))
flips = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while queue:
flips += 1
for _ in range(len(queue)):
r, c = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited and grid[nr][nc] == 0:
queue.append((nr, nc))
visited.add((nr, nc))
return flips
# Example Grid
grid = [
[0, 1, 0],
[0, 1, 0],
[1, 0, 1]
]
print(min_flips_to_flip_grid(grid)) # Output: 2
Output:
2
Diagram:
Grid:
0 1 0
0 1 0
1 0 1
Flips Required: 2
Explanation:
Problem:
You are given a 2D grid representing a map of gold mines. Each gold mine is represented by a cell containing gold nuggets. Determine the maximum number of gold nuggets you can collect by traveling from one mine to another using BFS.
Code:
from collections import deque
def max_gold_collected(grid):
rows, cols = len(grid), len(grid[0])
visited = set()
max_gold = 0
def bfs(start):
queue = deque([start])
visited.add(start)
gold_collected = 0
while queue:
r, c = queue.popleft()
gold_collected += grid[r][c]
for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:
visited.add((nr, nc))
queue.append((nr, nc))
return gold_collected
for r in range(rows):
for c in range(cols):
if grid[r][c] > 0 and (r, c) not in visited:
max_gold = max(max_gold, bfs((r, c)))
return max_gold
# Example Grid
grid = [
[0, 0, 1],
[1, 2, 0],
[0, 1, 0]
]
print(max_gold_collected(grid)) # Output: 3
Output:
3
Diagram:
Grid:
0 0 1
1 2 0
0 1 0
Max Gold Collected: 3
Explanation:
After tackling BFS problems, take the next step in your learning journey with upGrad's expert-led programs to advance your skills in coding and programming.
Explore AI Tutorial with Advantages and Disadvantages
upGrad offers hands-on training, real-world projects, and personalized mentorship to help you excel in coding and programming. With courses designed by top universities, you'll gain both theoretical knowledge and practical experience.
Here are a few courses to get you started:
Expand your expertise with the best resources available. Browse the programs below to find your ideal fit in Best Machine Learning and AI Courses Online.
Discover in-demand Machine Learning skills to expand your expertise. Explore the programs below to find the perfect fit for your goals.
Discover popular AI and ML blogs and free courses to deepen your expertise. Explore the programs below to find your perfect fit.
Get Free Consultation
By submitting, I accept the T&C and
Privacy Policy
Top Resources