Traverse

两种遍历

DFS(深度优先)BFS(广度优先)
数据结构栈(递归 / 显式栈)队列
顺序一条路走到底再回溯一层一层扩散
找什么路径、连通性、拓扑序最短(少)步数
空间O(深度)O(\text{深度})O(宽度)O(\text{宽度})

核心区别: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 按距离递增的顺序访问(队列保证先处理距离dd 的,再处理d+1d+1 的),所以第一次到达某点时走的是最短路径。

条件:所有边权相等(通常为 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);
        }
    }
}

复杂度O(n+m)O(n + m),比 Dijkstra 的O(mlog⁡n)O(m \log n) 快。

多源 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))  两个方向各走一半

搜索空间从bdb^d 降到bd/2b^{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);

复杂度O(n+m)O(n+m),比 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 最小(最早)的节点

桥(割边)判定:边(u,v)(u, v)(uu 是vv 的父)是桥 ⟺ low[v] > dfn[u] (vv 的子树无法绕回到uu 或更早,所以这条边一断就分离)

割点判定:uu 是割点 ⟺ 存在子节点vv 使 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)

强连通:uu 能到vv 且vv 能到uu。

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] 就弹栈:说明uu 及其后代无法到达比uu 更早的节点 → 它们构成一个极大的强连通块。

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 时把路径上所有点直接挂到根
  • 按秩/大小合并:小树挂到大树下

两个都用时,复杂度近似O(1)O(1)(严格是O(α(n))O(\alpha(n)),反阿克曼函数,实际永不超 5)。

应用:

  • Kruskal 最小生成树
  • 动态连通性
  • 判环(加边时两点已连通 → 有环)
  • 带权并查集(维护相对关系,如"食物链")

复杂度

操作复杂度
DFS / BFSO(n+m)O(n + m)
拓扑排序O(n+m)O(n + m)
Tarjan(割点/桥/SCC)O(n+m)O(n + m)
并查集(qq 次操作)O((n+q)α(n))O((n+q)\alpha(n))
双向 BFSO(bd/2)O(b^{d/2})

所有遍历都是O(n+m)O(n+m)——每个点访问一次,每条边检查常数次。

常见坑

  • 忘记 vis 标记:DFS 无限递归(尤其有环的图)
  • vis 标记时机:DFS 应在入栈/进入时标记,不是出栈时,否则重复访问
  • BFS 的 dist 初值:用 -1 或 INF 表示未访问,别用 0(会和起点混淆)
  • 多组数据没清空:g、vis、dist 都要清
  • Tarjan 里回边判断:无向图跳过 parent,有向图要看 inStack
  • 无向图的重边导致 Tarjan 误判:用边的编号而不是顶点来判断父边
  • 拓扑排序的入度统计:建图时就要统计,别漏
  • 割点的根特判:根需要 ≥2 个子树才是割点
  • 栈溢出:n=105n = 10^5 的链式图,递归 DFS 会爆栈。改用显式栈或 BFS
  • SCC 缩点后忘了去重边:不影响正确性,但会影响复杂度