C++ Program for DFS (Depth First Search) with Example

A C++ program for DFS uses a recursive function to visit nodes starting from a source, marking visited nodes with visited[node] = true and recursively calling DFS on unvisited neighbors; for example, void dfs(int node) { visited[node] = true; for (auto v : graph[node]) if (!visited[v]) dfs(v); }.

Examples

InputGraph edges: 0-1, 0-2, 1-2, 2-0, 2-3, 3-3; Start node: 2

OutputVisited nodes in order: 2 0 1 3

InputGraph edges: 0-1, 1-2, 2-3; Start node: 0

OutputVisited nodes in order: 0 1 2 3

InputGraph edges: 0-1; Start node: 1

OutputVisited nodes in order: 1

How to Think About It

To perform DFS, think of starting at a node and exploring as far as possible along each branch before backtracking. Use a list to keep track of visited nodes to avoid repeating. For each node, mark it visited, then visit all its neighbors recursively if they are not visited yet.

Algorithm

1

Initialize a visited array to false for all nodes.

2

Start DFS from the given start node.

3

Mark the current node as visited and print it.

4

For each neighbor of the current node, if it is not visited, recursively call DFS on it.

5

Repeat until all reachable nodes are visited.

Code

cpp

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

vector<vector<int>> graph;
vector<bool> visited;

void dfs(int node) {
    visited[node] = true;
    cout << node << " ";
    for (int v : graph[node]) {
        if (!visited[v]) dfs(v);
    }
}

int main() {
    int n = 4; // number of nodes
    graph.resize(n);
    visited.resize(n, false);

    // edges
    graph[0] = {1, 2};
    graph[1] = {2};
    graph[2] = {0, 3};
    graph[3] = {3};

    dfs(2);
    return 0;
}

Output

2 0 1 3 

Dry Run

Let's trace DFS starting from node 2 on the example graph.

1

Start DFS at node 2

Mark visited[2] = true, print 2

2

Visit neighbors of 2

Neighbors are 0 and 3; 0 not visited, call dfs(0)

3

DFS at node 0

Mark visited[0] = true, print 0; neighbors 1 and 2; 1 not visited, call dfs(1)

4

DFS at node 1

Mark visited[1] = true, print 1; neighbor 2 already visited, return

5

Back to node 2

Next neighbor 3 not visited, call dfs(3)

6

DFS at node 3

Mark visited[3] = true, print 3; neighbor 3 already visited, return

Step	Current Node	Visited Array	Output
1	2	[false, false, true, false]	2
2	0	[false, false, true, false]	2
3	0	[true, false, true, false]	2 0
4	1	[true, false, true, false]	2 0
5	1	[true, true, true, false]	2 0 1
6	3	[true, true, true, false]	2 0 1
7	3	[true, true, true, true]	2 0 1 3

Why This Works

Step 1: Mark node visited

We set visited[node] = true to avoid visiting the same node multiple times.

Step 2: Print current node

We print the node when we first visit it to show the order of traversal.

Step 3: Recursive calls on neighbors

For each neighbor, if it is not visited, we call DFS recursively to explore deeper.

Alternative Approaches

Iterative DFS using stack

cpp

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

int main() {
    int n = 4;
    vector<vector<int>> graph(n);
    graph[0] = {1, 2};
    graph[1] = {2};
    graph[2] = {0, 3};
    graph[3] = {3};

    vector<bool> visited(n, false);
    stack<int> s;
    s.push(2);

    while (!s.empty()) {
        int node = s.top();
        s.pop();
        if (!visited[node]) {
            visited[node] = true;
            cout << node << " ";
            for (auto it = graph[node].rbegin(); it != graph[node].rend(); ++it) {
                if (!visited[*it]) s.push(*it);
            }
        }
    }
    return 0;
}

Uses a stack instead of recursion; good for avoiding stack overflow on large graphs.

DFS with adjacency matrix

cpp

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

vector<vector<int>> graph;
vector<bool> visited;

void dfs(int node, int n) {
    visited[node] = true;
    cout << node << " ";
    for (int v = 0; v < n; v++) {
        if (graph[node][v] == 1 && !visited[v]) dfs(v, n);
    }
}

int main() {
    int n = 4;
    graph = vector<vector<int>>(n, vector<int>(n, 0));
    visited = vector<bool>(n, false);

    graph[0][1] = 1; graph[0][2] = 1;
    graph[1][2] = 1;
    graph[2][0] = 1; graph[2][3] = 1;
    graph[3][3] = 1;

    dfs(2, n);
    return 0;
}

Uses adjacency matrix instead of list; simpler for dense graphs but uses more memory.

Complexity: O(V + E) time, O(V) space

Time Complexity

DFS visits each vertex once and explores all edges once, so time is proportional to vertices plus edges.

Space Complexity

Space is used for the visited array and recursion stack, both proportional to number of vertices.

Which Approach is Fastest?

Recursive and iterative DFS have similar time complexity; iterative avoids recursion overhead but code is slightly more complex.

Approach	Time	Space	Best For
Recursive DFS	O(V + E)	O(V)	Simple code, small to medium graphs
Iterative DFS	O(V + E)	O(V)	Large graphs to avoid recursion stack overflow
Adjacency Matrix DFS	O(V^2)	O(V^2)	Dense graphs where edges are many