Lecture 373:- Program for DFS

here's a C++ program for Depth-First Search (DFS) using the recursive approach:

cppCopy code

#include <iostream> #include <vector> using namespace std; // Function to perform DFS on the graph void dfs(vector<vector<int>>& graph, vector<bool>& visited, int current) {    visited[current] = true;    cout << current << " "; // Process the current vertex (print it)    for (int neighbor : graph[current]) {        if (!visited[neighbor]) {            dfs(graph, visited, 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 DFS: ";    cin >> source;    cout << "DFS 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 function dfs performs the DFS 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 DFS 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 DFS from multiple source vertices to explore all the connected components.