CPP Program to Implement Breadth First Search (BFS)

by

Introduction

Breadth-First Search (BFS) is a fundamental graph traversal algorithm that explores all the vertices of a graph layer by layer. It starts at a given source vertex and explores all its neighboring vertices before moving on to their neighbors. BFS is widely used in various applications, such as finding the shortest path in unweighted graphs, solving puzzles, and network broadcasting. This article will guide you through the implementation of BFS in C++, providing detailed explanations and examples to help you understand this essential algorithm.

Prerequisites

Before diving into the implementation, it’s important to have a basic understanding of the following concepts:

  • Graph: A collection of nodes (vertices) and edges connecting some or all of them.
  • Queue: A linear data structure that follows the First-In-First-Out (FIFO) principle.
  • Visited Array: An array to keep track of the vertices that have been visited to avoid processing a vertex more than once.

Familiarity with C++ programming, including standard libraries like <iostream>, <vector>, and <queue>, will be beneficial.

Implementing Breadth First Search (BFS)

To implement BFS, we will use the following steps:

  1. Initialize a queue and a visited array.
  2. Mark the starting vertex as visited and enqueue it.
  3. Dequeue a vertex from the queue and process it.
  4. Enqueue all adjacent vertices of the dequeued vertex that have not been visited.
  5. Repeat steps 3 and 4 until the queue is empty.

Pseudocode for BFS

  1. Initialize a queue and a visited array.
  2. Mark the starting vertex as visited and enqueue it.
  3. While the queue is not empty:
    • Dequeue a vertex from the queue.
    • Process the dequeued vertex.
    • Enqueue all adjacent vertices of the dequeued vertex that have not been visited.

Example: BFS in an Undirected Graph

Graph Representation

Consider a simple undirected graph:

    0
   / \
  1   2
  |   |
  3---4

C++ Program

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Graph {
    int V; // Number of vertices
    vector<vector<int>> adjList;

public:
    Graph(int V);
    void addEdge(int v, int w);
    void BFS(int start);
};

Graph::Graph(int V) {
    this->V = V;
    adjList.resize(V);
}

void Graph::addEdge(int v, int w) {
    adjList[v].push_back(w);
    adjList[w].push_back(v); // For undirected graph
}

void Graph::BFS(int start) {
    vector<bool> visited(V, false);
    queue<int> q;

    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int vertex = q.front();
        cout << vertex << " ";
        q.pop();

        for (int i : adjList[vertex]) {
            if (!visited[i]) {
                visited[i] = true;
                q.push(i);
            }
        }
    }
}

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 4);
    g.addEdge(3, 4);

    cout << "Breadth First Traversal starting from vertex 0:" << endl;
    g.BFS(0);

    return 0;
}

Output

Breadth First Traversal starting from vertex 0:
0 1 2 3 4

Additional Examples

Example 1: BFS in a Directed Graph

Graph Representation

Consider a directed graph:

    0 → 1
    ↓   ↓
    2 → 3

C++ Program

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Graph {
    int V;
    vector<vector<int>> adjList;

public:
    Graph(int V);
    void addEdge(int v, int w);
    void BFS(int start);
};

Graph::Graph(int V) {
    this->V = V;
    adjList.resize(V);
}

void Graph::addEdge(int v, int w) {
    adjList[v].push_back(w);
}

void Graph::BFS(int start) {
    vector<bool> visited(V, false);
    queue<int> q;

    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int vertex = q.front();
        cout << vertex << " ";
        q.pop();

        for (int i : adjList[vertex]) {
            if (!visited[i]) {
                visited[i] = true;
                q.push(i);
            }
        }
    }
}

int main() {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(2, 3);
    g.addEdge(1, 3);

    cout << "Breadth First Traversal starting from vertex 0:" << endl;
    g.BFS(0);

    return 0;
}

Output

Breadth First Traversal starting from vertex 0:
0 1 2 3

Example 2: BFS in a Larger Graph

Graph Representation

Consider a larger graph:

    0---1
   /|   |\
  2 3   4 5

C++ Program

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Graph {
    int V;
    vector<vector<int>> adjList;

public:
    Graph(int V);
    void addEdge(int v, int w);
    void BFS(int start);
};

Graph::Graph(int V) {
    this->V = V;
    adjList.resize(V);
}

void Graph::addEdge(int v, int w) {
    adjList[v].push_back(w);
    adjList[w].push_back(v);
}

void Graph::BFS(int start) {
    vector<bool> visited(V, false);
    queue<int> q;

    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int vertex = q.front();
        cout << vertex << " ";
        q.pop();

        for (int i : adjList[vertex]) {
            if (!visited[i]) {
                visited[i] = true;
                q.push(i);
            }
        }
    }
}

int main() {
    Graph g(6);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(0, 3);
    g.addEdge(1, 4);
    g.addEdge(1, 5);

    cout << "Breadth First Traversal starting from vertex 0:" << endl;
    g.BFS(0);

    return 0;
}

Output

Breadth First Traversal starting from vertex 0:
0 1 2 3 4 5

Conclusion

Breadth-First Search (BFS) is a versatile algorithm for traversing or searching through graph data structures. It is particularly useful for finding the shortest path in unweighted graphs and for exploring all nodes reachable from a given node