by Jasleen Chhabra | Updated on 24 August 2024

Introduction

Breadth-First Search (BFS) is a fundamental algorithm used to explore the vertices of a graph or nodes of a tree in breadthward motion. It is commonly employed for searching and traversing through graph structures and is particularly effective for finding the shortest path in an unweighted graph.

How BFS Works

BFS starts from a given source vertex and explores all its neighboring vertices at the present depth prior to moving on to the vertices at the next depth level. This exploration continues until all vertices at the current level have been explored. BFS utilizes a queue data structure to keep track of the vertices that need to be explored.

Algorithm Steps

1. Initialization:
   • Create a queue to hold the vertices that need to be explored.
   • Mark the starting vertex as visited.
   • Enqueue the starting vertex into the queue.
2. Exploration:
   • While the queue is not empty:
     • Dequeue a vertex from the front of the queue.
     • Process the vertex (e.g., print its value).
     • For each unvisited neighboring vertex:
       • Mark it as visited.
       • Enqueue it into the queue.
3. Termination:
   • The algorithm terminates when all vertices reachable from the starting vertex have been processed.

BFS Algorithm in Pseudocode

BFS(Graph, start_vertex):

    create a queue Q

    create a set to track visited vertices

    enqueue start_vertex into Q

    mark start_vertex as visited

 

    while Q is not empty:

        current_vertex = dequeue from Q

        process(current_vertex)  // e.g., print the vertex

 

        for each neighbor of current_vertex:

            if neighbor is not in visited:

                mark neighbor as visited

                enqueue neighbor into Q

BFS Example

Let's consider a simple undirected graph for illustration:

mathematica

Copy code

       A

      / \

     B   C

    / \   \

   D   E   F

• Starting from vertex A, the BFS traversal would visit the vertices in the following order: A, B, C, D, E, F.

---

C++ Implementation

Here’s a sample implementation of the BFS algorithm in C++ using an adjacency list representation for the graph:

#include <iostream>

#include <vector>

#include <queue>

#include <unordered_set>

 

using namespace std;

 

class Graph {

    int V; // Number of vertices

    vector<vector<int>> adj; // Adjacency list

 

public:

    Graph(int V) {

        this->V = V;

        adj.resize(V);

    }

 

    void addEdge(int u, int v) {

        adj[u].push_back(v);

        adj[v].push_back(u); // For undirected graph

    }

 

    void BFS(int start) {

        unordered_set<int> visited; // Set to keep track of visited vertices

        queue<int> Q; // Queue for BFS

 

        visited.insert(start); // Mark the start vertex as visited

        Q.push(start); // Enqueue the start vertex

 

        while (!Q.empty()) {

            int current = Q.front(); // Get the front vertex

            Q.pop(); // Remove it from the queue

            cout << current << " "; // Process the current vertex

 

            // Explore all adjacent vertices

            for (int neighbor : adj[current]) {

                if (visited.find(neighbor) == visited.end()) { // If not visited

                    visited.insert(neighbor); // Mark as visited

                    Q.push(neighbor); // Enqueue the neighbor

                }

            }

        }

    }

};

 

int main() {

    Graph g(6); // Create a graph with 6 vertices

    g.addEdge(0, 1); // A - B

    g.addEdge(0, 2); // A - C

    g.addEdge(1, 3); // B - D

    g.addEdge(1, 4); // B - E

    g.addEdge(2, 5); // C - F

 

    cout << "BFS traversal starting from vertex A (0): ";

    g.BFS(0); // Start BFS from vertex A (0)

 

    return 0;

}

---

Explanation of the C++ Code

1. Graph Class: Represents the graph using an adjacency list. It has methods for adding edges and performing BFS.
2. addEdge Method: Adds an undirected edge between vertices u and v.
3. BFS Method: Implements the BFS algorithm:
   • It uses an unordered set to track visited vertices and a queue for exploring the graph.
   • It processes each vertex, prints it, and enqueues its unvisited neighbors.
4. Main Function: Creates a graph, adds edges, and calls the BFS method starting from vertex A (0).

---

Conclusion

Breadth-First Search is a powerful and straightforward algorithm for exploring graphs. Its applications range from pathfinding to network analysis, making it a fundamental tool in computer science and programming. In subsequent articles, we will explore additional graph algorithms, such as Depth-First Search (DFS) and various pathfinding algorithms.

---