What is Depth First Search in C++?

Can you explain what Depth First Search is in C++?

Depth First Search (DFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the root (or an arbitrary node) and explores as far as possible along each branch before backtracking.

How does DFS differ from Breadth First Search?

DFS explores as far down a branch as possible before backtracking, while Breadth First Search (BFS) explores all neighbors at the present depth prior to moving on to nodes at the next depth level.

Can you provide a simple C++ implementation of DFS?

Sure! Here's a simple implementation of DFS using recursion:

#include <iostream>
#include <vector>
using namespace std;

void DFS(int node, vector<bool> &visited, const vector<vector<int>> &adj) {
    visited[node] = true;
    cout << node << " ";
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            DFS(neighbor, visited, adj);
        }
    }
}

int main() {
    int n = 5; // number of nodes
    vector<vector<int>> adj(n);
    // Add edges
    adj[0] = {1, 2};
    adj[1] = {0, 3, 4};
    adj[2] = {0};
    adj[3] = {1};
    adj[4] = {1};

    vector<bool> visited(n, false);
    DFS(0, visited, adj);
    return 0;
}

This code performs DFS starting from node 0.

What are the time and space complexities of DFS?

The time complexity of DFS is O(V + E), where V is the number of vertices and E is the number of edges. The space complexity is O(V) due to the storage of the visited nodes and the recursion stack.