C++ graphs: BFS, DFS, and connected components
A graph is a set of nodes joined by edges. An adjacency list stores, for every node, the list of its neighbours, which uses O(V + E) memory and is the usual choice for sparse graphs. Breadth-first search (BFS) visits nodes in layers using a queue, and finds shortest paths in unweighted graphs. Depth-first search (DFS) goes as deep as possible before backtracking, using recursion or an explicit stack.
C++
#include <iostream>
#include <queue>
#include <vector>
void dfs(const std::vector<std::vector<int>>& g, int node, std::vector<bool>& seen) {
seen[node] = true;
std::cout << " " << node;
for (int next : g[node]) {
if (!seen[next]) {
dfs(g, next, seen);
}
}
}
int main() {
std::vector<std::vector<int>> g(7);
auto edge = [&](int a, int b) {
g[a].push_back(b);
g[b].push_back(a);
};
edge(0, 1); edge(0, 2); edge(1, 3); edge(2, 3); edge(4, 5);
std::vector<bool> seen(7, false);
std::queue<int> pending;
pending.push(0);
seen[0] = true;
std::cout << "bfs from 0:";
while (!pending.empty()) {
int node = pending.front();
pending.pop();
std::cout << " " << node;
for (int next : g[node]) {
if (!seen[next]) {
seen[next] = true;
pending.push(next);
}
}
}
std::cout << "\n";
std::vector<bool> visited(7, false);
std::cout << "dfs from 0:";
dfs(g, 0, visited);
std::cout << "\n";
std::vector<bool> marked(7, false);
int components = 0;
for (int start = 0; start < 7; ++start) {
if (!marked[start]) {
++components;
std::queue<int> q;
q.push(start);
marked[start] = true;
while (!q.empty()) {
int node = q.front();
q.pop();
for (int next : g[node]) {
if (!marked[next]) {
marked[next] = true;
q.push(next);
}
}
}
}
}
std::cout << "components: " << components << "\n";
}