第42章图论进阶

课程目录第42章图论进阶

第42章图论进阶：强连通分量、割点与桥、二分图匹配

图论学到这个阶段，咱们已经能处理不少实际问题了。但说实话，前面那些基础遍历和最短路径，在真实项目中往往不够用。我记得有一次做社交网络分析，需要找出用户群体中哪些人是「铁杆小圈子」——互相都关注的那种。这不就是强连通分量吗？

这一章，我带你啃下四个硬骨头：Tarjan算法、Kosaraju算法、割点与桥，还有二分图匹配。每个都是面试高频，也是工程实战利器。

1. 强连通分量：Tarjan算法

强连通分量（SCC），说白了就是有向图里的一群节点，它们之间任意两点都能互相到达。我当年第一次写Tarjan时，被那个low数组绕晕了好几天。后来想通了——low[u]记录的是u能回溯到的最早祖先，就这么简单。

核心思想：DFS遍历时给每个节点打上时间戳dfn，同时维护一个low值。当dfn[u] == low[u]时，说明找到了一个SCC的根。

// Tarjan算法求SCC —— C语言实现
#define MAXN 10005
int dfn[MAXN], low[MAXN], idx;
int stack[MAXN], top, in_stack[MAXN];
int scc_id[MAXN], scc_cnt;
vector<int> G[MAXN];

void tarjan(int u) {
    dfn[u] = low[u] = ++idx;
    stack[++top] = u;
    in_stack[u] = 1;
    
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);  // 回溯更新
        } else if (in_stack[v]) {
            low[u] = min(low[u], dfn[v]);  // 后向边
        }
    }
    
    if (dfn[u] == low[u]) {
        scc_cnt++;
        int v;
        do {
            v = stack[top--];
            in_stack[v] = 0;
            scc_id[v] = scc_cnt;
        } while (v != u);
    }
}

我的小技巧：调试Tarjan时，我习惯打印每个节点的dfn和low值。如果发现某个节点的low值一直等于dfn，那它八成就是SCC的根节点。

2. Kosaraju算法：另一种思路

Kosaraju的思路更直白——先对原图做一次DFS记录出栈顺序，再对反图按出栈逆序做DFS。每次DFS找到的就是一个SCC。

我个人更喜欢Tarjan，因为一次DFS搞定，代码量小。但Kosaraju也有优势：思路好理解，不容易写错。

// Kosaraju算法框架
void dfs1(int u) {
    visited[u] = 1;
    for each v in G[u]:
        if (!visited[v]) dfs1(v);
    order.push_back(u);  // 记录出栈顺序
}

void dfs2(int u) {
    scc[u] = scc_cnt;
    for each v in revG[u]:
        if (!scc[v]) dfs2(v);
}

// 主流程
for each u in V:
    if (!visited[u]) dfs1(u);
for each u in reverse(order):
    if (!scc[u]) scc_cnt++, dfs2(u);

注意：Kosaraju需要存储反向图，空间开销翻倍。如果图特别大（比如上百万节点），Tarjan更省内存。

3. 割点与桥：Tarjan的变体

割点和桥解决的是无向图问题。割点就是删掉后图不连通的节点，桥就是删掉后图不连通的边。

判断条件其实就两条：

割点：对于根节点，有至少两个子节点；对于非根节点，存在子节点v使得low[v] >= dfn[u]
桥：对于边(u,v)，如果low[v] > dfn[u]，那么这条边就是桥

嗯，这里要注意——桥的判断没有等号。为什么？因为如果有等号，说明v还能绕回u，那这条边就不是唯一的连接了。

// 求割点
void cut_point(int u, int parent) {
    dfn[u] = low[u] = ++idx;
    int child = 0;
    
    for each v in G[u]:
        if (!dfn[v]) {
            child++;
            cut_point(v, u);
            low[u] = min(low[u], low[v]);
            if (parent != -1 && low[v] >= dfn[u])
                is_cut[u] = 1;  // u是割点
        } else if (v != parent) {
            low[u] = min(low[u], dfn[v]);
        }
    
    if (parent == -1 && child > 1)
        is_cut[u] = 1;  // 根节点特判
}

避坑指南：我曾经在求桥时把条件写成了low[v] >= dfn[u]，结果把一堆普通边也标记成了桥。调试了一下午才发现是等号的问题。记住：桥是严格大于，割点才是大于等于。

4. 二分图判定与最大匹配

二分图判定其实很简单——用染色法。从任意节点开始，给相邻节点染不同颜色，如果出现冲突就不是二分图。

最大匹配用的是匈牙利算法。核心思想就一句话：能匹配就匹配，匹配不了就尝试让之前的匹配对象换一个。

// 匈牙利算法求最大匹配
int match[MAXN], vis[MAXN];

int dfs(int u) {
    for each v in G[u]:
        if (!vis[v]) {
            vis[v] = 1;
            if (match[v] == -1 || dfs(match[v])) {
                match[v] = u;
                return 1;
            }
        }
    return 0;
}

int hungarian() {
    int res = 0;
    memset(match, -1, sizeof(match));
    for (int i = 1; i <= n; i++) {
        memset(vis, 0, sizeof(vis));
        if (dfs(i)) res++;
    }
    return res;
}

我的经验：匈牙利算法的时间复杂度是O(VE)，对于稀疏图表现很好。但如果图比较稠密，建议用Hopcroft-Karp算法，能快到O(E√V)。

5. 四种算法的对比

算法	解决的问题	时间复杂度	空间复杂度	我的推荐指数
Tarjan SCC	有向图强连通分量	O(V+E)	O(V)	⭐⭐⭐⭐⭐
Kosaraju	有向图强连通分量	O(V+E)	O(V+E)	⭐⭐⭐⭐
Tarjan 割点/桥	无向图割点与桥	O(V+E)	O(V)	⭐⭐⭐⭐⭐
匈牙利算法	二分图最大匹配	O(VE)	O(V+E)	⭐⭐⭐⭐

说实话，这四个算法在面试中出现的频率非常高。尤其是Tarjan，几乎成了大厂图论题的标配。我建议你把Tarjan的模板背熟，理解low数组的更新逻辑，遇到类似问题就能举一反三了。

总结一下：这一章我们学了四种图论进阶算法。Tarjan和Kosaraju解决的是有向图的「连通性」问题，割点和桥解决的是无向图的「脆弱性」问题，匈牙利算法解决的是「配对」问题。每个算法都有它独特的应用场景，理解它们的核心思想比死记代码更重要。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录