DFS Algorithm

Description

Depth-First Search (DFS) is an algorithm used for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

C++ Code

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

void DFSUtil(int v, vector<bool>& visited, const vector<vector<int>>& adj) {
    visited[v] = true;
    cout << v << " ";

    for (int i = 0; i < adj[v].size(); ++i) {
        if (!visited[adj[v][i]]) {
            DFSUtil(adj[v][i], visited, adj);
        }
    }
}

void DFS(int V, const vector<vector<int>>& adj) {
    vector<bool> visited(V, false);

    for (int v = 0; v < V; ++v) {
        if (!visited[v]) {
            DFSUtil(v, visited, adj);
        }
    }
}

int main() {
    int V = 5;
    vector<vector<int>> adj(V);

    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[1].push_back(0);
    adj[1].push_back(3);
    adj[1].push_back(4);
    adj[2].push_back(0);
    adj[3].push_back(1);
    adj[4].push_back(1);

    DFS(V, adj);

    return 0;
}

Time and Space Complexity

Operation	Time Complexity	Space Complexity
DFS Algorithm	O(V + E)	O(V)

Where:

• V: Number of vertices.
• E: Number of edges.

← Back to Homepage