Lecture 374:- Let's Code BFS & DFS

here's a C++ program for both Breadth-First Search (BFS) and Depth-First Search (DFS) using the iterative approach (using a queue and a stack, respectively):

cppCopy code

#include <iostream> #include <vector> #include <queue> #include <stack> using namespace std; // Function to perform BFS on the graph void bfs(vector<vector<int>>& graph, vector<bool>& visited, int source) {    queue<int> q;    q.push(source);    visited[source] = true;    while (!q.empty()) {        int current = q.front();        q.pop();        cout << current << " "; // Process the current vertex (print it)        for (int neighbor : graph[current]) {            if (!visited[neighbor]) {                visited[neighbor] = true;                q.push(neighbor);            }        }    } } // Function to perform DFS on the graph void dfs(vector<vector<int>>& graph, vector<bool>& visited, int source) {    stack<int> stk;    stk.push(source);    visited[source] = true;    while (!stk.empty()) {        int current = stk.top();        stk.pop();        cout << current << " "; // Process the current vertex (print it)        for (int neighbor : graph[current]) {            if (!visited[neighbor]) {                visited[neighbor] = true;                stk.push(neighbor);            }        }    } } int main() {    int vertices, edges;    cout << "Enter the number of vertices and edges: ";    cin >> vertices >> edges;    vector<vector<int>> graph(vertices);    vector<bool> visited(vertices, false);    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 and DFS: ";    cin >> source;    cout << "BFS Traversal starting from vertex " << source << ": ";    bfs(graph, visited, source);    // Reset the visited array for DFS    for (int i = 0; i < vertices; ++i) {        visited[i] = false;    }    cout << "\nDFS Traversal starting from vertex " << source << ": ";    dfs(graph, visited, source);    return 0; }

In this program, we represent the undirected graph using an adjacency list, where graph is a vector of vectors. The functions bfs and dfs perform BFS and DFS traversals starting from the specified source vertex and print the order of visited vertices. The user inputs the number of vertices, edges, and the edges between vertices to construct the graph. The BFS and DFS traversals are started from the specified source vertex. The program uses a queue for BFS and a stack for DFS to keep track of the vertices that need to be visited.