Depth-first search

DFS follows one branch deeply before returning. It is useful for reachability, tree structure, and graph decomposition.

Prerequisites: Basic C++ input/output, vectors, loops, and the preceding graph lessons.

Build the idea

1. Mark a vertex when you enter it.
2. Visit every unvisited neighbor recursively.
3. The recursive call returns when that branch has no unexplored neighbors.
4. To traverse a disconnected graph, start DFS from each still-unvisited vertex.
5. seen prevents revisiting a vertex through a cycle. Each recursive call completely explores its branch before returning; the final printing loop only changes the presentation order.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: seen prevents revisiting a vertex through a cycle. Each recursive call completely explores
// its branch before returning; the final printing loop only changes the presentation order.
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
using namespace std;
void dfs(int v,const vector<vector<int>>&g,vector<bool>&seen){
    seen[v]=true;
    for(int u:g[v]){
        if(!seen[u]){
            dfs(u,g,seen);
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,source;
    cin>>n>>m>>source;
    vector<vector<int>>graph(n+1);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    vector<bool>seen(n+1,false);
    dfs(source,graph,seen);
    for(int vertex=1;vertex<=n;vertex++){
        if(seen[vertex]){
            cout<<vertex<<'\n';
        }
    }
}

Complexity analysis

O(V + E) time, O(V) stack and visited space.

Example input and output

Read n m source, then m undirected edges. Use 1≤n≤2000 for this recursive teaching implementation. Print reachable labels in increasing order; this output order is not the DFS discovery order.

Input

5 3 1
1 2
2 3
4 5

Output

1
2
3

The recursive calls discover the component containing 1. Printing the visited array afterward lists its three labels.

Practical applications

Use DFS for component exploration, traversal trees, and decompositions. Use an explicit stack when recursion depth may be large.

Check your understanding

What prevents DFS from looping forever around a cycle?

Put it into practice

Print all vertices reachable from a chosen source.