Depth-First Search
GOALWalk a graph recursively and count its connected pieces.
Depth-first search means: go forward as far as you can, and back up when you cannot — like walking a maze with one hand on the wall. Written recursively it is very short. One thing you must not forget: MARK where you have been.
ON THIS PAGE
//THE EXAMPLE
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> adj;
vector<bool> seen;
void dfs(int v) {
seen[v] = true;
for (int to : adj[v]) {
if (!seen[to]) {
dfs(to);
}
}
}
int main() {
int n = 6;
adj.assign(n, {});
seen.assign(n, false);
adj[0].push_back(1); adj[1].push_back(0);
adj[1].push_back(2); adj[2].push_back(1);
adj[3].push_back(4); adj[4].push_back(3);
int groups = 0;
for (int v = 0; v < n; v++) {
if (!seen[v]) {
groups++;
dfs(v);
}
}
cout << groups << endl;
return 0;
}3
//LINE BY LINE
Watch it run
Six nodes and three edges. Nothing has been visited yet.
What DFS is good for
DFS does NOT find shortest paths. Do not use it for that. It is very good at questions about connection.
- Can these two nodes reach each other?
- How many separate groups are there?
- Is there a cycle?
- Counting every possible route.
For a shortest path, use BFS. A route found by DFS is a route, but nothing promises it is the shortest one.
Recursion depth is a real limit
Recursive DFS is short and readable, but its depth can equal the number of nodes. On a line-shaped graph of 100 000 nodes that is 100 000 nested calls.
C++ has no such setting. If the depth could be large you have to rewrite the recursion as a loop with your own stack.