Graphs: BFS and DFS
Representing graphs with adjacency lists, and exploring them with breadth-first and depth-first search.
A graph is a set of nodes connected by edges. The usual representation is an adjacency list: for each node, a list of its neighbors (std::vector<std::vector<int>>).
- Breadth-first search (BFS) uses a queue and visits nodes in order of distance, so it finds shortest paths when every edge has the same cost.
- Depth-first search (DFS) uses recursion or a stack and goes as deep as possible first; it's used for cycle detection and topological sorting.
Both mark nodes as visited so they're processed once, giving O(V + E) time.
Example
#include <iostream>
#include <queue>
#include <vector>
int main() {
std::vector<std::vector<int>> adj{{1, 2}, {3}, {3}, {4}, {}};
std::vector<int> dist(adj.size(), -1);
std::queue<int> q;
dist[0] = 0;
q.push(0);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
std::cout << "distance to 4: " << dist[4] << "\n";
return 0;
}
Output:
distance to 4: 3