Implement a breadth-first search (BFS) on a graph.

Breadth-First Search (BFS) is graph traversal algorithm that explores a graph level by level, visiting all the neighbors of a vertex before moving on to the next level. BFS is often used to find the shortest path between two vertices and to determine the connected components of a graph.

BFS uses a queue to keep track of the vertices to be visited in a specific order. It starts with the initial vertex, visits its neighbors, and then moves on to the neighbors’ neighbors, exploring the graph level by level. The visited vector ensures that each vertex is processed only once.

BFS Implementation C++

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

class Graph {
private:
    int vertices;
    std::vector<std::vector<int>> adjacencyList;

public:
    Graph(int v) : vertices(v), adjacencyList(v) {}

    void addEdge(int u, int v) {
        adjacencyList[u].push_back(v);
        adjacencyList[v].push_back(u); // For an undirected graph
    }

    void bfs(int startVertex) {
        std::vector<bool> visited(vertices, false);
        std::queue<int> queue;

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

        while (!queue.empty()) {
            int currentVertex = queue.front();
            queue.pop();

            std::cout << currentVertex << " ";

            for (int neighbor : adjacencyList[currentVertex]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.push(neighbor);
                }
            }
        }
    }
};

int main() {
    // Create a sample graph
    Graph graph(7);
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 5);
    graph.addEdge(2, 6);

    // Perform BFS starting from vertex 0
    std::cout << "BFS starting from vertex 0: ";
    graph.bfs(0);
    std::cout << std::endl;

    return 0;
}

Output:

BFS starting from vertex 0: 0 1 2 3 4 5 6