C++ Program to Implement Breadth-First Search (BFS) In a Graph

1. Introduction

Breadth-First Search (BFS) is a well-known algorithm used for traversing or searching through tree and graph data structures. Starting from an initial or source node, it explores all the neighbor nodes at the present depth prior to moving on to nodes at the next depth level. BFS is commonly employed in a variety of scenarios, like finding the shortest path in unweighted graphs or for network broadcasting.

2. Program Overview

The program will:

1. Establish a Graph class that uses an adjacency list to depict the graph.

2. Introduce methods within the Graph class to:

- Add edges to the graph.

- Execute BFS commencing from a particular vertex.

3. Showcase the BFS traversal process within the main function.

3. Code Program

#include<iostream>
#include<list>
using namespace std;

// Define the Graph class
class Graph {
    int V;  // Number of vertices
    list<int> *adj;  // Pointer to an array constituting adjacency lists

public:
    // Graph class constructor
    Graph(int V) {
        this->V = V;
        adj = new list<int>[V];
    }

    // Function to add an edge to the graph
    void addEdge(int v, int w) {
        adj[v].push_back(w);  // Add w to v’s list
    }

    // BFS traversal function starting from source vertex s
    void BFS(int s) {
        // Create a boolean array to mark all vertices as not visited
        bool *visited = new bool[V];
        for(int i = 0; i < V; i++) {
            visited[i] = false;
        }

        // Create a queue for BFS
        list<int> queue;

        // Mark the source node as visited and enqueue it
        visited[s] = true;
        queue.push_back(s);

        while(!queue.empty()) {
            // Dequeue a vertex from queue and output it
            s = queue.front();
            cout << s << " ";
            queue.pop_front();

            // Traverse all adjacent vertices of the dequeued vertex
            for(auto i = adj[s].begin(); i != adj[s].end(); ++i) {
                if (!visited[*i]) {
                    visited[*i] = true;
                    queue.push_back(*i);
                }
            }
        }
    }
};

// Main function
int main() {
    Graph g(4);  // Construct a graph with 4 vertices
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);

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

    return 0;
}

Output:

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

4. Step By Step Explanation

1. We utilize an adjacency list (STL list) for the Graph class representation.

2. A boolean array is employed to keep track of visited nodes, ensuring we don't revisit nodes.

3. The BFS function employs a queue, which is essential for BFS traversal. It helps in visiting nodes layer by layer, ensuring all nodes at the present depth are visited before progressing to the next depth.

4. In our example within the main function, we create a simple graph, introduce some edges, and then perform BFS starting from vertex 2.

The added comments in the code aim to make the implementation clearer and easier to follow.