Lecture 371:- Program for BFS

here's a simple C++ program to perform Breadth-First Search (BFS) on an undirected graph represented using an adjacency list:

cppCopy code

#include <iostream> #include <vector> #include <queue> using namespace std; // Function to perform BFS on the graph void bfs(vector<vector<int>>& graph, int source) {    int vertices = graph.size();    vector<bool> visited(vertices, false);    queue<int> q;    // Mark the source vertex as visited and enqueue it    visited[source] = true;    q.push(source);    while (!q.empty()) {        int current = q.front();        q.pop();        cout << current << " "; // Process the current vertex (print it)        // Enqueue all unvisited neighbors of the current vertex        for (int neighbor : graph[current]) {            if (!visited[neighbor]) {                visited[neighbor] = true;                q.push(neighbor);            }        }    } } int main() {    int vertices, edges;    cout << "Enter the number of vertices and edges: ";    cin >> vertices >> edges;    vector<vector<int>> graph(vertices);    cout << "Enter the edges (source and destination):" << endl;    for (int i = 0; i < edges; ++i) {        int src, dest;        cin >> src >> dest;        graph[src].push_back(dest);        graph[dest].push_back(src); // For undirected graph    }    int source;    cout << "Enter the source vertex for BFS: ";    cin >> source;    cout << "BFS Traversal starting from vertex " << source << ": ";    bfs(graph, source);    return 0; }

In this program, we represent the undirected graph using an adjacency list, where graph is a vector of vectors. The function bfs performs the BFS traversal starting from the specified source vertex and prints the order of visited vertices. The user inputs the number of vertices, edges, and the edges between vertices to construct the graph. The BFS traversal is started from the specified source vertex.

Note: This program assumes that the input graph is connected. If the graph is not connected, you may need to perform BFS from multiple source vertices to explore all the connected components.