Depth-First Search (DFS)

Algorithm Explanation

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It can be implemented recursively or iteratively using a stack.

Time and Space Complexity

• Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges.
• Space Complexity: O(V), due to the visited array and the recursion stack.

Easy Problems

1. DFS Traversal of a Graph

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

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

int main() {
    int V = 5;
    vector<vector<int>> adj(V);
    adj[0] = {1, 2};
    adj[1] = {0, 3, 4};
    adj[2] = {0};
    adj[3] = {1};
    adj[4] = {1};

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

2. Detect Cycle in an Undirected Graph

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

bool DFS(int v, int parent, vector<bool>& visited, vector<vector<int>>& adj) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u]) {
            if (DFS(u, v, visited, adj)) return true;
        } else if (u != parent) {
            return true;
        }
    }
    return false;
}

bool hasCycle(int V, vector<vector<int>>& adj) {
    vector<bool> visited(V, false);
    for (int v = 0; v < V; ++v) {
        if (!visited[v]) {
            if (DFS(v, -1, visited, adj)) return true;
        }
    }
    return false;
}
  

Intermediate Problems

1. Count Connected Components in a Graph

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

void DFS(int v, vector<bool>& visited, vector<vector<int>>& adj) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u]) {
            DFS(u, visited, adj);
        }
    }
}

int countComponents(int V, vector<vector<int>>& adj) {
    vector<bool> visited(V, false);
    int count = 0;
    for (int v = 0; v < V; ++v) {
        if (!visited[v]) {
            DFS(v, visited, adj);
            count++;
        }
    }
    return count;
}
  

2. Topological Sort of a DAG

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

void DFS(int v, vector<bool>& visited, stack<int>& Stack, vector<vector<int>>& adj) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u]) {
            DFS(u, visited, Stack, adj);
        }
    }
    Stack.push(v);
}

void topologicalSort(int V, vector<vector<int>>& adj) {
    stack<int> Stack;
    vector<bool> visited(V, false);
    for (int v = 0; v < V; ++v) {
        if (!visited[v]) {
            DFS(v, visited, Stack, adj);
        }
    }
    while (!Stack.empty()) {
        cout << Stack.top() << " ";
        Stack.pop();
    }
}
  

Hard Problem

Find All Paths from Source to Target in a DAG

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

void DFS(int v, int target, vector<vector<int>>& adj, vector<int>& path, vector<vector<int>>& allPaths) {
    path.push_back(v);
    if (v == target) {
        allPaths.push_back(path);
    } else {
        for (int u : adj[v]) {
            DFS(u, target, adj, path, allPaths);
        }
    }
    path.pop_back();
}

vector<vector<int>> findAllPaths(int V, vector<vector<int>>& adj, int source, int target) {
    vector<vector<int>> allPaths;
    vector<int> path;
    DFS(source, target, adj, path, allPaths);
    return allPaths;
}