About Us Services Blog Contact Us Learn

Breadth-First Search (BFS): A Layer-by-Layer Exploration


Breadth-First Search (BFS): A Layer-by-Layer Exploration

Welcome! Today, we're diving into Breadth-First Search (BFS), a fundamental algorithm used to traverse or search tree or graph data structures. It's a way of exploring, making sure you check all your immediate options before venturing further out.


What is BFS?

BFS is a graph traversal technique that explores all the neighbor nodes at the present depth (or "layer") prior to moving on to the nodes at the next depth level. Think of it as exploring a maze by first checking all paths directly accessible from your current spot, then systematically checking all paths one step further away, and so on. It searches breadth-wise.


How BFS Basically Works: The "Ripple Effect"

Before we get into the technical details of how we make a computer do this, let's build an intuition for what BFS does.

Imagine dropping a pebble into a calm pond. The ripples spread out in concentric circles, right? The first ripple is closest to the center, the second ripple is a bit further out, then the third, and so on. Each ripple represents a "layer."

BFS works in a very similar way when exploring a graph:

  1. You start at a chosen source node (the point where the pebble drops). This is your first "layer" (Layer 0).
  2. Then, BFS identifies all nodes that are directly connected to the source node. These form the next layer (Layer 1).
  3. Next, it finds all new nodes that are directly connected to any node in Layer 1 (and haven't been seen before). These form Layer 2.
  4. This process continues, systematically exploring the graph layer by layer, moving outwards from the source.

Consider a very simple social network:

  • You (Source)
  • Your direct friends (Layer 1)
  • Friends of your direct friends (whom you don't know directly) (Layer 2)
  • And so on...

BFS would first identify all your direct friends, then all their friends (excluding those already identified), and so forth. This ensures that you find the "closest" connections first. The core idea is this layer-by-layer traversal. We don't go deep down one path before exploring other options at the current "distance."


The Key Tool: Using a Queue FIFO

Now, how do we programmatically achieve this layer-by-layer exploration? We use a Queue!

A queue is a data structure that follows the First-In, First-Out (FIFO) principle. Imagine a checkout line at a grocery store: the first person in line is the first person to be served.

Why is FIFO crucial for BFS?

When we are at a certain node and discover its neighbors (which are part of the next layer), we add them to the back of the queue. To process the current layer completely before moving to the next layer, we always take the node from the front of the queue to explore next. This ensures that nodes are visited in the order they are discovered, maintaining the layer-by-layer progression.


How BFS Works: The Algorithm Steps

Let's break down the formal steps involved in a BFS traversal:

  1. Initialization:
    • Choose a starting node (source).
    • Create an empty queue.
    • Create a way to keep track of visited nodes (e.g., a boolean array or a set) to avoid processing the same node multiple times and getting stuck in infinite loops.
    • Mark the starting node as visited and enqueue it into the queue.
    • Optionally, you can keep track of the distance (number of edges or "layer") of each node from the source. The distance to the source node is 0.
  2. Traversal:
    • While the queue is not empty:
      • Dequeue a node from the front of the queue. Let's call this currentNode.
      • Process currentNode (e.g., print it, check if it's the target node you're searching for, etc.).
      • For each neighbor of currentNode:
        • If the neighbor has not been visited:
          • Mark the neighbor as visited.
          • (If tracking distance) Set distance[neighbor] = distance[currentNode] + 1.
          • Enqueue the neighbor into the queue.

Let's Walk Through an Example!

Consider the following graph structure (as suggested by your image's node numbering and connections):

      1
     /|\
    / | \
   2  3  4
   |  | \
   5  6  7
    

Edges: (1,2), (1,3), (1,4), (2,5), (3,6), (3,7).

Let's start BFS from node 1.

  1. Initialize:
    • Queue: [1]
    • Visited: {1}
    • Distances: dist[1] = 0 (Layer 0)
  2. Iteration 1:
    • Dequeue 1. (Output: 1)
    • Neighbors of 1 are 2, 3, 4.
    • Mark 2, 3, 4 as visited.
    • dist[2]=1, dist[3]=1, dist[4]=1 (All these are Layer 1 nodes)
    • Enqueue 2, then 3, then 4.
    • Queue: [2, 3, 4]
    • Visited: {1, 2, 3, 4}
  3. Iteration 2:
    • Dequeue 2. (Output: 2)
    • Neighbor of 2 is 5.
    • Node 5 is unvisited. Mark 5 as visited.
    • dist[5]=2 (Layer 2)
    • Enqueue 5.
    • Queue: [3, 4, 5]
    • Visited: {1, 2, 3, 4, 5}
  4. Iteration 3:
    • Dequeue 3. (Output: 3)
    • Neighbors of 3 are 6 and 7.
    • Node 6 is unvisited. Mark 6 as visited. dist[6]=2. Enqueue 6.
    • Node 7 is unvisited. Mark 7 as visited. dist[7]=2. Enqueue 7.
    • (Both 6 and 7 are Layer 2 nodes, discovered from a Layer 1 node)
    • Queue: [4, 5, 6, 7]
    • Visited: {1, 2, 3, 4, 5, 6, 7}
  5. Iteration 4:
    • Dequeue 4. (Output: 4)
    • Node 4 has no unvisited neighbors in this example.
    • Queue: [5, 6, 7]
  6. Iteration 5:
    • Dequeue 5. (Output: 5)
    • Node 5 has no unvisited neighbors.
    • Queue: [6, 7]
  7. Iteration 6:
    • Dequeue 6. (Output: 6)
    • Node 6 has no unvisited neighbors.
    • Queue: [7]
  8. Iteration 7:
    • Dequeue 7. (Output: 7)
    • Node 7 has no unvisited neighbors.
    • Queue: []

The queue is now empty, so the BFS traversal is complete!

The order of nodes visited (processed) layer by layer was: 1 (layer 0) -> 2, 3, 4 (layer 1) -> 5, 6, 7 (layer 2).

This step-by-step process shows how the queue ensures that we explore all nodes at one level (e.g., 2, 3, 4 are all direct neighbors of 1) before moving to the next level (e.g., 5, 6, 7).


Code Implementations

Below are the implementations in Java and C++.

JAVA


// Java program for BFS traversal from a given source node
import java.util.*;

public class BFSExample {
    public static void bfs(int V, List<List<Integer>> adj, int start) {
        boolean[] visited = new boolean[V];
        Queue<Integer> queue = new LinkedList<>();

        visited[start] = true;
        queue.add(start);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");

            for (int neighbor : adj.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        int V = 5;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());

        adj.get(0).add(1);
        adj.get(0).add(2);
        adj.get(1).add(3);
        adj.get(1).add(4);

        System.out.println("BFS traversal starting from node 0:");
        bfs(V, adj, 0);
    }
}
        

Time and Space Complexity Explained

Understanding the efficiency of an algorithm is crucial.

Time Complexity: O(V + E)

  • V: Number of vertices (nodes) in the graph.
  • E: Number of edges in the graph.

Let's break down why:

  1. Vertex Operations (Queueing): Each vertex in the graph is enqueued at most once. This is because we only enqueue a vertex if it has not been visited before, and then we mark it as visited. Similarly, each vertex is dequeued at most once. If there are V vertices, the total time for all enqueue and dequeue operations will be proportional to V, so O(V).
  2. Edge Exploration (Neighbor Scanning): When we dequeue a vertex u, we iterate through all its neighbors to see if they are unvisited. This means we look at each edge connected to u.
    • For an undirected graph, each edge (u, v) is considered twice: once when we process u and look at v, and once when we process v and look at u. So, the total number of times edges are examined is 2E.
    • For a directed graph, each edge (u, v) is considered once: when we process u and look at its outgoing edge to v. So, the total number of times edges are examined is E.
    In both cases, the total time spent exploring edges across all vertices is proportional to E, so O(E).
  3. Combining these: The total time complexity of BFS is the sum of the time spent on vertex operations and edge explorations, which is O(V) + O(E) = O(V + E). We visit every vertex and traverse every edge at most a constant number of times.

Space Complexity: O(V)

This refers to the additional memory the algorithm needs beyond the input graph itself.

  1. Queue Storage: In the worst-case scenario, the queue might need to hold a large number of vertices. Consider a graph where one node (the source) is connected to all other V-1 nodes. After processing the source, all V-1 neighbors will be added to the queue. Thus, the maximum size of the queue can be proportional to V. So, this contributes O(V) to the space complexity.
  2. Visited Set Storage: We need to store information about whether each vertex has been visited. This is typically done using a boolean array of size V or a hash set that could store up to V entries. This also contributes O(V) space.
  3. Distance Storage (Optional): If we are storing the distance of each node from the source, this would require an array of size V, contributing O(V) space.

Combining these factors, the dominant term for space complexity is O(V). The amount of memory needed scales linearly with the number of vertices in the graph.


Algorithm

Here's a concise summary of the BFS procedure:

  1. Pick a Starting Point: Select the initial node from which the search will begin.
  2. Prepare Your Tools:
    • Get a Queue (to keep track of nodes to visit).
    • Get a Visited List (to remember nodes already processed or in the queue, so you don't visit them again).
  3. Begin the Search:
    • Add the starting node to the Queue.
    • Add the starting node to the Visited List.
  4. Explore Layer by Layer:
    • As long as the Queue is not empty, repeat the following:
      • Take out the node from the front of the Queue (let's call it the current_node).
      • Do whatever you need to do with current_node (e.g., check if it's your target, print it, etc.).
      • Look at all the neighbors of the current_node.
      • For each neighbor:
        • If this neighbor is not on your Visited List:
          • Add it to the back of the Queue.
          • Add it to the Visited List.
  5. Finish: Once the Queue is empty, it means you've visited all reachable nodes in a breadth-first manner.

Conclusion

BFS is a powerful and efficient way to explore graphs when you need to find the shortest path in terms of the number of edges (for unweighted graphs) or when you want to explore nodes in order of their proximity to a starting point. It's a cornerstone algorithm in computer science!

Recent Posts

Breadth-First Search (BFS): A Layer-by-Layer Exploration

Breadth-First Search (BFS): A Layer-by-Layer Exploration

Intro What is BFS? The Ripple Effect Queue Concept Steps Example Key Insight Code Complexity Breadth-First Search (BFS): A Layer-by-Layer Exploration Welcome! Today, we're diving into Breadth-First Search (BFS), a fundamental algorithm used to traverse or search tree or graph data structures. It's a way of exploring,

Types of Binary Trees

Types of Binary Trees

Full Binary Tree Complete Binary Tree Perfect Binary Tree Balanced Binary Tree Degenerate Binary Tree Types of Binary Trees Welcome back to our tutorial series on Data Structures and Algorithms! So far, we've laid the groundwork by understanding the basics of Trees and Binary Trees and then delved into some key