Lecture 372:- Depth First Search

Depth-First Search (DFS) is a graph traversal algorithm used to explore all the vertices of a graph in depthward motion. It starts at a specified source vertex and explores as far as possible along each branch before backtracking. DFS is implemented using recursion or a stack data structure to keep track of the vertices that need to be visited.

The steps to perform DFS on a graph are as follows:

1. Initialize a boolean array to keep track of visited vertices.
2. Call the DFS function starting from the source vertex.
3. In the DFS function, mark the current vertex as visited and process it.
4. For each unvisited neighbor of the current vertex, recursively call the DFS function.

DFS can be implemented using two approaches:

1. Recursive DFS: In the recursive approach, we define a separate recursive function that performs the DFS. The function is called with the source vertex, and it, in turn, calls itself for each unvisited neighbor.

cppCopy code

#include <iostream> #include <vector> using namespace std; 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; }

1. Iterative DFS using Stack: In the iterative approach, we use a stack data structure to simulate the function call stack in the recursive version. The stack stores the vertices to be processed, and we repeatedly pop a vertex from the stack, mark it as visited, and push its unvisited neighbors onto the stack.

cppCopy code

#include <iostream> #include <vector> #include <stack> using namespace std; void dfs(vector<vector<int>>& graph, vector<bool>& visited, int source) {    stack<int> stk;    stk.push(source);    while (!stk.empty()) {        int current = stk.top();        stk.pop();        if (!visited[current]) {            visited[current] = true;            cout << current << " "; // Process the current vertex (print it)            for (int neighbor : graph[current]) {                if (!visited[neighbor]) {                    stk.push(neighbor);                }            }        }    } } int main() {    // Similar to the recursive approach above    // ... }

Both approaches are valid for implementing DFS, and the choice between them depends on the preference and requirements of the specific use case. The time complexity of DFS is O(V + E), where V is the number of vertices and E is the number of edges in the graph, as it visits each vertex and each edge exactly once. The space complexity is O(V) for the recursive approach and O(V) + O(V) = O(V) for the iterative approach due to the use of the boolean array and the stack.