BFS and DFS
The fundamental graph traversals for reachability, layering, component discovery, and tree exploration.
BFS and DFS
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
BFS and DFS are the first graph routines worth internalizing. They are simple enough to write from memory and strong enough to sit inside many larger algorithms later: topological sort, SCC, bridges, tree DP, shortest paths on unweighted graphs, and more.
When to Use It
Use BFS or DFS when:
the graph structure itself is the problem,
you need reachability, connected components, or a traversal order,
the graph is a tree and you need parent/depth information.
Core Idea
DFS follows one path as far as it can before backtracking. BFS expands in layers from the starting node. Both visit every reachable vertex, but the order they expose is different and useful in different ways.
Key Insight
BFS is the right tool when distance in number of edges matters. DFS is the right tool when the recursion tree or entry / exit structure matters. A lot of graph problems become easy once that distinction is clear.
Operations / Main Technique
BFS from one source for unweighted shortest paths,
DFS for components, subtree structure, or cycle detection,
repeated traversal from unvisited nodes for a full graph decomposition.
Worked example.
On an unweighted graph, BFS from node \(s\) reaches every vertex at distance \(1\) before any vertex at distance \(2\). That is exactly why the first time a node is popped, its distance is final.
Correctness Intuition
DFS visits every edge leaving a reached vertex, so it eventually explores the whole reachable region. BFS keeps a queue ordered by layer, so nodes are expanded in nondecreasing distance from the source.
Complexity Analysis
With adjacency lists, both traversals run in \(O(n + m)\) time and \(O(n)\) extra memory.
Implementation
The code includes:
BFS distances on an adjacency list,
iterative DFS order collection,
a connected-components helper.
Common Pitfalls
Forgetting to clear the visited array between test cases.
Recursive DFS stack overflow on very deep graphs.
Using BFS when weighted edges invalidate the layer guarantee.
Mixing 0-indexed and 1-indexed graph input.
Variants / Extensions
Multi-source BFS.
0-1 BFS for edge weights \(0\) and \(1\).
DFS timestamps for bridges, SCC, or subtree intervals.
Practice Problems
Count connected components.
Shortest path in an unweighted graph.
Check whether a graph is bipartite with BFS coloring.
Gather subtree sizes in a rooted tree with DFS.
References
Code
Contest-ready reference implementation for the idea explained above.
vector<int> bfs_distances(const vector<vector<int>>& graph, int source) {
int n = (int)graph.size();
vector<int> dist(n, -1);
queue<int> q;
dist[source] = 0;
q.push(source);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int to : graph[v]) {
if (dist[to] == -1) {
dist[to] = dist[v] + 1;
q.push(to);
}
}
}
return dist;
}
vector<int> dfs_order(const vector<vector<int>>& graph, int source) {
vector<int> order;
vector<int> seen(graph.size(), 0);
vector<int> st = {source};
while (!st.empty()) {
int v = st.back();
st.pop_back();
if (seen[v]) continue;
seen[v] = 1;
order.push_back(v);
for (int i = (int)graph[v].size() - 1; i >= 0; --i) {
int to = graph[v][i];
if (!seen[to]) {
st.push_back(to);
}
}
}
return order;
}
vector<vector<int>> connected_components(const vector<vector<int>>& graph) {
int n = (int)graph.size();
vector<int> seen(n, 0);
vector<vector<int>> comps;
for (int start = 0; start < n; ++start) {
if (seen[start]) continue;
vector<int> comp;
stack<int> st;
st.push(start);
seen[start] = 1;
while (!st.empty()) {
int v = st.top();
st.pop();
comp.push_back(v);
for (int to : graph[v]) {
if (!seen[to]) {
seen[to] = 1;
st.push(to);
}
}
}
comps.push_back(comp);
}
return comps;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.