C++ Program: Breadth-First Search (BFS)

This C++ program demonstrates the Breadth-First Search (BFS) algorithm in a graph. The BFS algorithm is used to traverse or search tree or graph data structures. It starts at a given node (often called the ‘root’ node) and explores all of the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.

Program Explanation

The program includes a Graph class which represents the graph structure and contains methods to add edges and perform BFS traversal.

Key components of the program include:

• The Graph class which uses an array of vectors to represent the adjacency list of each vertex.
• The addEdge method to add edges between vertices in the graph.
• The BFS method to perform the BFS traversal starting from a given vertex.
• The main method to create the graph, add edges, and initiate the BFS traversal.

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

/**
 * Class to represent a graph using an adjacency list.
 */
class Graph {
    int numVertices;
    vector<list> adjLists;

public:
    // Constructor
    Graph(int vertices);

    // Function to add an edge to the graph
    void addEdge(int src, int dest);

    // Function to perform BFS
    void BFS(int startVertex);
};

// Constructor to initialize the graph
Graph::Graph(int vertices) {
    numVertices = vertices;
    adjLists.resize(vertices);
}

/**
 * Function to add an edge to the graph.
 * @param src - The source vertex.
 * @param dest - The destination vertex.
 */
void Graph::addEdge(int src, int dest) {
    adjLists[src].push_back(dest);
    adjLists[dest].push_back(src); // For undirected graph, add this line
}

/**
 * Function to perform BFS traversal from a given vertex.
 * @param startVertex - The starting vertex for BFS traversal.
 */
void Graph::BFS(int startVertex) {
    vector visited(numVertices, false);
    queue q;

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

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

        for (auto i = adjLists[currentVertex].begin(); i != adjLists[currentVertex].end(); ++i) {
            int adjVertex = *i;
            if (!visited[adjVertex]) {
                visited[adjVertex] = true;
                q.push(adjVertex);
            }
        }
    }
}

int main() {
    Graph g(6);

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 4);
    g.addEdge(3, 4);
    g.addEdge(3, 5);

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

    return 0;
}