Breadth First Search Algorithm: Concepts, Applications, and Examples

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! 

What is the Breadth First Search Algorithm? Its Importance and Rules

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:

• Level-by-Level Exploration:
  BFS explores all nodes at one depth before moving to the next, ensuring no node is missed. It's ideal for tasks like finding connected components or systematically exploring networks.
• Shortest Path Guarantee:
  In unweighted graphs, BFS guarantees the shortest path, making it crucial for routing systems or solving mazes efficiently.
• Versatility Across Graph Types:
  BFS works with directed, undirected, and cyclic graphs. It’s used in social network analysis, web crawling, and communication networks to detect connections and bottlenecks.

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.

What is Graph Traversal? Basics

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:

• Breadth First Search (BFS): Explores nodes level by level, ensuring systematic traversal and the shortest path in unweighted graphs.
• Depth First Search (DFS): Delves as deep as possible into each branch before backtracking, making it suitable for tasks like cycle detection or topological sorting.

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.

What is Breadth First Search in AI?

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:

• Solving Puzzles:
  BFS is used in games like the 8-puzzle or Rubik’s Cube to explore all possible moves systematically. For example, in the 8-puzzle, BFS examines each possible tile movement step by step until the configuration matches the desired solution, ensuring the optimal sequence of moves is found.
• Pathfinding in Mazes:
  BFS ensures the shortest path from a starting point to a goal in maze-solving tasks. For instance, in a grid-based maze, BFS starts at the entry point and explores all reachable paths level by level until it finds the exit, guaranteeing the shortest route.
• Network Analysis:
  BFS is crucial for traversing social or communication networks. For example, it identifies the shortest connection between two people in a social network or detects clusters of closely connected individuals, enabling tasks like friend suggestions or identifying influencers.
• BFS in Natural Language Processing:

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.

• BFS in Game Development for AI Opponents:

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 in Web Crawling for Search Engine Optimization:

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.

Why is the BFS Algorithm in AI Important?

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:

• Completeness:
  BFS guarantees to find a solution if one exists, which is ideal for exploring decision trees or solving complex puzzles.
• Optimality:
  It always finds the shortest path in unweighted graphs, which is crucial for tasks like autonomous navigation or emergency response.
• Simplicity:
  BFS’s straightforward implementation and predictable results make it a go-to choice for reliable problem-solving in AI.

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.

What are the Rules in BFS Algorithm?

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

1. Start with a Source Node
   Select a starting point to initiate the traversal.
   Example: In a graph, begin at node A, which serves as the entry point for exploration.
2. Use a Queue for Traversal
   Add the starting node to a queue, following the first-in, first-out (FIFO) principle, and mark it as visited to prevent reprocessing.
   Example: Add node A to the queue: [A].
3. Explore Neighbors
   Dequeue the front node, visit all its unvisited neighbors, and enqueue them for subsequent exploration.
   Example: From node A, visit its neighbors B and C, adding them to the queue: [B, C].
4. Mark Nodes as Visited
   As each node is processed, mark it as visited to avoid cycles or redundant traversal.
   Example: Mark A, B, and C as visited while processing them.
5. Repeat Until Queue is Empty
   Continue dequeuing nodes, visiting their neighbors, and adding unvisited nodes to the queue until it is empty.
   Example: Add nodes D and E, process them, and empty the queue: [D, E] → [].

Visual Example Graph:

   A  
   / \  
  B   C  
 /       \  
D         E

Queue Progression:

• Start: [A]
• After visiting A: [B, C]
• After visiting B: [C, D]
• After visiting C: [D, E]
• Final State: []

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.

How Does Breadth First Search Algorithm Work? Step-by-Step Guide

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:

• Use a queue to manage the order of nodes to be explored (FIFO structure).
• Maintain a visited list or set to record nodes that have already been processed to avoid revisiting them.
  Example: Start with an empty queue and visited set:
• Queue: []
• Visited: {}

2. Start with the Source Node

Choose a starting node and initialize the traversal.

• Add the source node to the queue.
• Mark it as visited to ensure it is not processed again.
  Example: Begin at node A:
• Queue: [A]
• Visited: {A}

3. Dequeue and Explore Neighbors

Process the node at the front of the queue:

• Remove the node from the queue.
• Explore all its unvisited neighbors, mark them as visited, and enqueue them.
  Example: Dequeue A, visit neighbors B and C, and add them to the queue:
• Queue: [B, C]
• Visited: {A, B, C}

4. Repeat for All Levels

Continue processing each node level by level:

• Dequeue the current node.
• Add its unvisited neighbors to the queue and mark them as visited.
  Example:
• Dequeue B, visit neighbor D, and enqueue it:
  • Queue: [C, D]
  • Visited: {A, B, C, D}
• Dequeue C, visit neighbor E, and enqueue it:
  • Queue: [D, E]
  • Visited: {A, B, C, D, E}

5. Terminate When Queue is Empty

Stop the traversal once the queue is empty, indicating that all nodes have been visited.
Final State:

• Queue: []
• Visited: {A, B, C, D, E}

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.

Breadth First Search Algorithm Explained with an Example

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

1. Start at the Source Node:
   Begin at node 1, add it to the queue, and mark it as visited.
   • Queue: [1]
   • Visited: {1}
2. Process the First Node:
   Dequeue node 1, visit its neighbors (2 and 3) and add them to the queue.
   • Queue: [2, 3]
   • Visited: {1, 2, 3}
3. Explore the Next Level:
   Dequeue node 2, visit its neighbor (4) and add it to the queue.
   • Queue: [3, 4]
   • Visited: {1, 2, 3, 4}
4. Continue Processing Nodes:
   Dequeue node 3, visit its neighbor (5),and add it to the queue.
   • Queue: [4, 5]
   • Visited: {1, 2, 3, 4, 5}
5. Finish the Traversal:
   Dequeue nodes 4 and 5. Both have no unvisited neighbors.
   • Queue: []
   • Visited: {1, 2, 3, 4, 5}

Final Output

The BFS traversal order is: 1 → 2 → 3 → 4 → 5.

How the Queue Changes at Each Step

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

1. Graph Definition:
   The graph is represented as a dictionary, where each key is a node, and the values are lists of its neighbors.
2. Function Initialization:
   The bfs function initializes:
   • A visited set to track processed nodes.
   • A queue (using deque) to manage nodes for traversal.
   • An order list to record the traversal order.
3. Traversal Logic:
   • While the queue is not empty, the first node is dequeued for processing.
   • If the node hasn’t been visited:
     • Mark it as visited.
     • Add it to the traversal order.
     • Add its neighbors to the queue.
4. Output:
   The function returns the order in which nodes are visited.
5. Visited Set 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.

Complexity of BFS Algorithm

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)

• Vertices (V): Each node is added to the queue and processed exactly once.
• Edges (E): Each edge is explored once when visiting a node’s neighbors.

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)

• Queue: Stores nodes for traversal; its size is proportional to the number of nodes at the widest level.
• Visited Set: Tracks explored nodes to prevent revisiting; its size grows linearly with the number of nodes.

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.

Pseudocode of Breadth First Search Algorithm

The breadth first search algorithm (BFS) uses a queue to explore nodes level by level. Here’s the step-by-step pseudocode for BFS:

1. Initialize:
   • Create a queue and add the starting node.
   • Mark the starting node as visited.
2. While the Queue is Not Empty:
   • Dequeue a node from the front of the queue.
   • For each unvisited neighbor of the dequeued node:
     • Mark the neighbor as visited.
     • Enqueue the neighbor.

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

1. Initialization: Start with a queue containing the starting node and mark it as visited to prevent revisits.
2. Traversal Loop: While the queue isn’t empty:
   • Dequeue the front node for processing.
   • Explore its unvisited neighbors, mark them as visited, and enqueue them for future traversal.
3. Completion: The process continues until the queue is empty, ensuring all reachable nodes are visited.

How BFS Visits Nodes

Here is a quick look at how BFS visits nodes:

• Level 0: Start with the root node.
• Level 1: Visit all neighbors of the root.
• Level 2: Visit neighbors of Level 1 nodes, and so on.

Example Table:

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.

Difference Between Breadth First Search and Depth First Search

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

• Traversal Approach
  BFS explores nodes level by level, ensuring a systematic and breadth-oriented traversal using a queue. In contrast, DFS delves as deep as possible along a branch before backtracking, relying on a stack or recursion.
  Example: BFS spreads outward from a source node, while DFS tunnels into one branch before exploring others. 
• Shortest Path
  BFS guarantees the shortest path in unweighted graphs by exploring all nodes at the current depth before moving deeper. DFS, however, does not ensure the shortest path since it prioritizes depth over breadth.
  Example: For an unweighted graph, BFS is optimal for pathfinding, whereas DFS may take longer or find a suboptimal path.
• Space Complexity
  BFS requires more space as it stores all nodes at the current level in a queue, which can grow significantly in large graphs. DFS, using a stack or recursion, consumes less space but may require more depth-specific memory.
  Example: For graphs with wide levels, BFS can consume more memory, while DFS is more efficient for deep, narrow graphs.

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

• BFS:
  • Use BFS for shortest-path problems in unweighted graphs, level-order traversal, and scenarios requiring systematic exploration.
    Example: BFS is ideal for finding the shortest route in a city’s road network.
• DFS:
  • Use DFS for tasks like cycle detection, topological sorting, or pathfinding in weighted graphs.
    Example: DFS works well for exploring hierarchical structures like folder systems or solving puzzles.

Example Problem

• BFS: Solves a maze by exploring all possible paths level by level, ensuring the shortest path is found efficiently.
• DFS: Explores one path to its end before backtracking, which can help in uncovering hidden paths or detecting cycles.

Use Cases Where BFS is Better Suited Compared to DFS

BFS is ideal for scenarios where exploring nodes level by level is critical.

• Unweighted Shortest Paths: BFS finds the shortest path in unweighted graphs, perfect for tasks like the shortest route in a city grid.
• Level-wise Traversal: BFS is beneficial for social media recommendations or job scheduling, where nodes need to be processed layer by layer.
• Finding All Connections: BFS ensures that all reachable nodes are explored, making it useful for network analysis or web crawling.

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.

• Shortest Path in Unweighted Graphs: DFS may miss the shortest path, whereas BFS always guarantees it, as seen in finding the shortest route in a map.
• Deeply Nested Structures: BFS is more efficient for solving puzzles that require shallow paths, unlike DFS which may explore deeper, less efficient paths.
• Graph with Multiple Solutions: BFS finds the optimal solution in mazes or pathfinding problems, while DFS may get stuck in deeper, non-optimal paths.

Understanding the differences between BFS and DFS lays the foundation for evaluating the specific strengths and limitations of BFS as an algorithm.

Advantages and Disadvantages of Breadth First Search 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:

• Shortest Path
  BFS guarantees the shortest path between two nodes in unweighted graphs. This is particularly useful in applications like navigation systems and network routing.
  Example: Finding the shortest route between two cities on a map of unweighted roads.
• Completeness
  BFS ensures all nodes are visited if a solution exists, making it reliable for solving connectivity problems and exhaustive searches.
  Example: Identifying connected components in a network graph.
• Systematic Traversal
  BFS explores nodes level by level, ensuring no node is missed. This is ideal for level-order analysis or problems that require exploring all possibilities.
  Example: Traversing a tree to analyze nodes at each depth.

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:

• High Space Complexity
  BFS requires a queue to store all nodes at the current level, which can grow significantly in large graphs. This makes it memory-intensive, especially for wide or densely connected graphs.
  Example: Traversing a graph with millions of nodes may exhaust available memory.
• Not Suitable for Weighted Graphs
  BFS does not account for edge weights, making it ineffective for weighted graph problems. Algorithms like Dijkstra’s or A* are better suited for such cases.
  Example: Finding the shortest path in a graph with varying travel times between nodes.
• Performance Issues on Large Graphs
  BFS processes every node and edge, which can be slow for graphs with a high number of vertices and edges. This affects its scalability in real-time or large-scale systems.
  Example: Social network analysis with billions of connections may become computationally expensive.

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.

Applications of Breadth First Search Algorithms

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.

Best Practices for Efficient BFS Algorithm Implementation

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.

Practice Problems - BFS Questions

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.

1. Cloudy Days (Easy)

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.

Input Format

• A 2D grid of size m × n, where each cell is either 0 (cloudy) or 1 (sunny).
• Start at any cell marked 0.

Output Format

• Minimum number of days to reach a sunny day (1).
• If no sunny day is reachable, return -1.

Constraints

• 1≤m,n≤100
• Grid cells are either 0 or 1.

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:

Explanation:

• BFS starts by adding all sunny cells (1) to the queue.
• It iteratively explores all the neighboring cells of the current node.
• Every time BFS reaches a new level (a new day), it marks those cells as visited and adds them to the queue.
• The process continues until all cloudy cells (0) are converted to sunny cells (1) or until no more sunny cells are reachable.

2. Station Pairs (Hard)

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.

Input Format

• Number of stations n.
• List of roads connecting the stations.
• Start station A and target station B.

Output Format

• Minimum transfers needed to reach station B from station A.

Constraints

• 1≤n≤10⁵
• Each station is connected by 1 or more roads.

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:

• The city’s road network is represented as a graph.
• BFS calculates the minimum number of transfers from station A to station B.
• Starting from station A, BFS explores all directly connected stations, marking them as visited.
• The algorithm counts how many transfers are required to reach station B.

3. Reach Quickly (Hard)

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.

Input Format

• Number of friends n.
• List of connections between friends.
• Starting friend and target friend.

Output Format

• Minimum number of connections to reach the target friend.

Constraints

• 1≤n≤10⁴
• Connections are bidirectional.

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:

• BFS is applied to find the shortest path (in terms of connections) between the starting friend and the target friend.
• Each connection represents a single level in BFS.
• The number of levels traversed gives the minimum number of connections needed to reach the target friend.

4. Vaccine Distribution (Hard)

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.

Input Format

• Number of cities n.
• List of roads connecting the cities.
• Starting city where the vaccine is available.

Output Format

• Minimum number of days required to distribute the vaccine to all cities.

Constraints

• 1≤n≤10⁵

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:

• BFS propagates the vaccine from the starting city to all other cities.
• Each BFS level corresponds to one day of distribution.
• The algorithm ensures the vaccine reaches all cities in the minimum number of days.

5. Flip Grid (Medium)

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.

Input Format

• A 2D grid of size m × n containing only 0 and 1.

Output Format

• Minimum number of flips required to convert all 0s to 1s.

Constraints

• 1≤m,n≤100
• Flips can only affect connected regions.

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:

• BFS is used to explore all connected regions of 0s in the grid.
• Each connected region of 0s is flipped in one move.
• BFS ensures all the 0s are flipped in the fewest moves by visiting each connected region level by level.

6. Two Gold Mines (Medium)

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.

Input Format

• A 2D grid of size m × n where each cell contains gold nuggets or 0 (no gold).

Output Format

• Maximum number of nuggets collectible from connected gold mines.

Constraints

• 1≤m,n≤100
• Moves are allowed to adjacent cells only.

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:

• BFS is used to traverse the grid and calculate the maximum gold nuggets collected by visiting connected gold mines.
• It explores each connected component of mines.
• The BFS sums the gold nuggets in each connected region, giving the maximum number of nuggets collected.

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.

How can upGrad Help You Advance Your Career in Coding/Programming?

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:

• Full Stack Development Bootcamp
• Post Graduate Certificate in Machine Learning & NLP (Executive)
• Post Graduate Certificate in Data Science & AI (Executive)
• Executive Diploma in Data Science & AI

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.