Traverse
两种遍历
| DFS(深度优先) | BFS(广度优先) | |
|---|---|---|
| 数据结构 | 栈(递归 / 显式栈) | 队列 |
| 顺序 | 一条路走到底再回溯 | 一层一层扩散 |
| 找什么 | 路径、连通性、拓扑序 | 最短(少)步数 |
| 空间 |
核心区别:BFS 保证首次到达某点时,路径是最短的(边权全为 1 时)。DFS 不保证。
DFS
递归版
vector<bool> vis(n, false);
void dfs(int u) {
vis[u] = true;
// 处理 u(前序)
for (int v : g[u]) {
if (!vis[v]) dfs(v);
}
// 处理 u(后序)
}显式栈版(避免爆栈)
void dfs_iter(int s) {
stack<int> st;
st.push(s);
vis[s] = true;
while (!st.empty()) {
int u = st.top(); st.pop();
for (int v : g[u]) {
if (!vis[v]) { vis[v] = true; st.push(v); }
}
}
}注意:显式栈的遍历顺序和递归版不一定相同(取决于压栈顺序)。
DFS 的时间戳
DFS 能给出很多结构性信息:
int timer = 0, tin[N], tout[N];
void dfs(int u, int p) {
tin[u] = ++timer;
for (int v : g[u]) if (v != p) dfs(v, u);
tout[u] = timer;
}
// 判断 u 是否是 v 的祖先(在有根树中)
bool isAncestor(int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}原理:DFS 的进入/离开时间形成区间嵌套,u 的子树在 tin[u] 到 tout[u] 之间。
DFS 树上的边分类(有向图)
| 类型 | 含义 |
|---|---|
| 树边(Tree Edge) | DFS 树上的边(走向未访问点) |
| 回边(Back Edge) | 指向祖先的边 → 存在回边 ⟺ 有环 |
| 前向边(Forward Edge) | 指向后代但非树边 |
| 横叉边(Cross Edge) | 指向已访问完的无关节点 |
判环(有向图):DFS 时维护"在栈中"标记,遇到栈中的点就是回边 → 有环。
vector<int> color(n, 0); // 0=未访问, 1=在栈中, 2=已完成
bool hasCycle = false;
void dfs(int u) {
color[u] = 1;
for (int v : g[u]) {
if (color[v] == 1) { hasCycle = true; return; } // 回边
if (color[v] == 0) dfs(v);
}
color[u] = 2;
}三色标记是标准做法(白色未访问、灰色在栈、黑色已完成)。
BFS
vector<int> dist(n, -1);
queue<int> q;
void bfs(int s) {
dist[s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : g[u]) {
if (dist[v] != -1) continue;
dist[v] = dist[u] + 1; // 边权为 1
q.push(v);
}
}
}为什么 BFS 给出最短路:BFS 按距离递增的顺序访问(队列保证先处理距离 的,再处理 的),所以第一次到达某点时走的是最短路径。
条件:所有边权相等(通常为 1)。边权不等时用 Dijkstra。
0-1 BFS(边权只有 0 和 1)
用双端队列:边权 0 → push_front,边权 1 → push_back。
deque<int> dq;
vector<int> dist(n, INF);
dist[s] = 0; dq.push_front(s);
while (!dq.empty()) {
int u = dq.front(); dq.pop_front();
for (auto [v, w] : g[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (w == 0) dq.push_front(v);
else dq.push_back(v);
}
}
}复杂度,比 Dijkstra 的 快。
多源 BFS
多个起点同时入队,等价于加了一个"超级源点"。
queue<int> q;
for (int s : sources) { dist[s] = 0; q.push(s); }
// 然后正常 BFS典型:多火焰扩散、多个商家的最近距离。
双向 BFS
起点和终点同时 BFS,相遇时停止。
单向: O(b^d) b=分支因子, d=深度
双向: O(b^(d/2)) 两个方向各走一半搜索空间从 降到,指数级的改进。适用于"已知起点和终点求最短路径"且分支因子大的场景(如八数码、单词接龙)。
拓扑排序
对 DAG 给一个线性序,使得每条边的起点排在终点前面。
应用:任务依赖、编译顺序、课程安排、DP 的计算顺序。
Kahn 算法(BFS,最常用)
1. 统计所有点的入度
2. 入度为 0 的点入队
3. 取队首 u,输出;把 u 的所有出边 (u→v) 的入度减 1
4. 若 v 的入度变成 0,入队
5. 重复直到队空vector<int> topo(int n, vector<vector<int>>& g) {
vector<int> indeg(n, 0);
for (int u = 0; u < n; u++)
for (int v : g[u]) indeg[v]++;
queue<int> q;
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push(i);
vector<int> order;
while (!q.empty()) {
int u = q.front(); q.pop();
order.push_back(u);
for (int v : g[u])
if (--indeg[v] == 0) q.push(v);
}
return order.size() == n ? order : vector<int>(); // 空 = 有环
}判环:order.size() < n 说明有环(有些点的入度永远降不到 0)。
DFS 版
后序遍历的逆序就是拓扑序。
vector<int> order;
void dfs(int u) {
vis[u] = true;
for (int v : g[u]) if (!vis[v]) dfs(v);
order.push_back(u); // 后序加入
}
// 最后 reverse(order)为什么是逆序:后序保证"后继先被加入",反过来就变成"前驱在前"。
拓扑序上做 DP
DAG 上的最短路/最长路:
// 按拓扑序计算 dp[v] = min over u→v of (dp[u] + w)
for (int u : topoOrder)
for (auto [v, w] : g[u])
dp[v] = min(dp[v], dp[u] + w);复杂度,比 Dijkstra 快(因为 DAG 没有环,一次扫描就够)。
注意:DAG 最长路可以处理负权(因为没有环,不会无限松弛)。
连通性
无向图:连通分量
// 数有几个连通块
int cc = 0;
for (int i = 0; i < n; i++) {
if (!vis[i]) { cc++; dfs(i); } // 每次 dfs 遍历完一整个连通块
}或用并查集(动态加边场景更好)。
无向图:割点 / 桥(Tarjan)
dfn / low 两个数组:
dfn[u]: DFS 进入 u 的时间
low[u]: u 及其子树能到达的、dfn 最小(最早)的节点桥(割边)判定:边( 是 的父)是桥 ⟺ low[v] > dfn[u] ( 的子树无法绕回到 或更早,所以这条边一断就分离)
割点判定: 是割点 ⟺ 存在子节点 使 low[v] >= dfn[u] (对根节点,要求有 ≥2 个子树)
vector<int> dfn(n, 0), low(n, 0);
int timer = 0;
vector<int> isCut(n, false);
void tarjan(int u, int parent) {
dfn[u] = low[u] = ++timer;
int children = 0;
for (int v : g[u]) {
if (v == parent) continue; // 无向图跳过父边
if (!dfn[v]) {
children++;
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (parent != -1 && low[v] >= dfn[u]) isCut[u] = true;
} else {
low[u] = min(low[u], dfn[v]); // 回边(已在栈中)
}
}
if (parent == -1 && children > 1) isCut[u] = true; // 根的特判
}注意:无向图里,"已访问但不是父"的边就是回边,用 dfn[v] 更新 low[u]。
有向图:强连通分量(SCC)
强连通: 能到 且 能到。
Tarjan:
vector<int> dfn(n, 0), low(n, 0), inStack(n, false), sccId(n, -1);
stack<int> st;
int timer = 0, sccCnt = 0;
void tarjan(int u) {
dfn[u] = low[u] = ++timer;
st.push(u); inStack[u] = true;
for (int v : g[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (inStack[v]) {
low[u] = min(low[u], dfn[v]); // 关键:只用在栈中的
}
}
if (low[u] == dfn[u]) { // u 是 SCC 的根
while (true) {
int x = st.top(); st.pop();
inStack[x] = false;
sccId[x] = sccCnt;
if (x == u) break;
}
sccCnt++;
}
}为什么 low[u] == dfn[u] 就弹栈:说明 及其后代无法到达比 更早的节点 → 它们构成一个极大的强连通块。
inStack 的判断是关键:不在栈中的点属于已完成的 SCC,不能用它更新 low。
SCC 缩点
把每个 SCC 缩成一个点,得到的新图一定是 DAG。
原图 → 求 SCC → 每个 SCC 缩成一个点 → 建新图(DAG)→ 在 DAG 上做 DP/拓扑典型应用:
- 求"最少加几条边使图强连通"
- 2-SAT
- 有向图上的可达性统计
并查集(DSU)
处理动态连通性:加边、查询两点是否连通。
struct DSU {
vector<int> p, sz;
DSU(int n) : p(n), sz(n, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); } // 路径压缩
bool unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b); // 按大小合并
p[b] = a; sz[a] += sz[b];
return true;
}
bool same(int a, int b) { return find(a) == find(b); }
};两个优化缺一不可:
- 路径压缩:
find时把路径上所有点直接挂到根 - 按秩/大小合并:小树挂到大树下
两个都用时,复杂度近似(严格是,反阿克曼函数,实际永不超 5)。
应用:
- Kruskal 最小生成树
- 动态连通性
- 判环(加边时两点已连通 → 有环)
- 带权并查集(维护相对关系,如"食物链")
复杂度
| 操作 | 复杂度 |
|---|---|
| DFS / BFS | |
| 拓扑排序 | |
| Tarjan(割点/桥/SCC) | |
| 并查集( 次操作) | |
| 双向 BFS |
所有遍历都是——每个点访问一次,每条边检查常数次。
常见坑
- 忘记
vis标记:DFS 无限递归(尤其有环的图) vis标记时机:DFS 应在入栈/进入时标记,不是出栈时,否则重复访问- BFS 的
dist初值:用-1或INF表示未访问,别用 0(会和起点混淆) - 多组数据没清空:
g、vis、dist都要清 - Tarjan 里回边判断:无向图跳过
parent,有向图要看inStack - 无向图的重边导致 Tarjan 误判:用边的编号而不是顶点来判断父边
- 拓扑排序的入度统计:建图时就要统计,别漏
- 割点的根特判:根需要 ≥2 个子树才是割点
- 栈溢出: 的链式图,递归 DFS 会爆栈。改用显式栈或 BFS
- SCC 缩点后忘了去重边:不影响正确性,但会影响复杂度