图上算法 • CoderXL's Blog

图的遍历#

图的遍历是指从某个顶点出发，系统地访问图中的所有顶点，使得每个顶点恰好被访问一次。最基本的两种遍历方式是广度优先搜索 (BFS) 和 深度优先搜索 (DFS)。

BFS#

BFS 从源顶点出发，逐层向外扩展——先访问距离为 1 的所有邻居，再访问距离为 2 的所有邻居，依此类推。它本质上使用一个队列来维护待访问的顶点。

将源顶点入队，标记为已访问
当队列非空时，弹出队首顶点 $u$
遍历 $u$ 的所有未被访问的邻居，依次入队并标记
重复 2-3 直到队列为空

flowchart TD
    A((A)) --> B((B))
    A --> C((C))
    A --> D((D))
    B --> E((E))
    B --> F((F))
    C --> G((G))

C++
Python

void bfs(int start, int n, const vector<vector<int>>& adj) {
    vector<bool> vis(n, false);
    queue<int> q;
    q.push(start); vis[start] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (!vis[v]) {
                vis[v] = true;
                q.push(v);
            }
        }
    }
}

cpp

from collections import deque

def bfs(start, n, adj):
    vis = [False] * n
    q = deque([start])
    vis[start] = True
    while q:
        u = q.popleft()
        for v in adj[u]:
            if not vis[v]:
                vis[v] = True
                q.append(v)

python

DFS#

DFS 从源顶点出发，沿着一条路径尽可能深入，直到无法继续再回溯。它本质上使用递归栈（或显式的栈）来实现。

标记当前顶点 $u$ 为已访问
遍历 $u$ 的所有未被访问的邻居，对每个邻居递归调用 DFS
所有邻居处理完毕后回溯

C++
Python

void dfs(int u, const vector<vector<int>>& adj, vector<bool>& vis) {
    vis[u] = true;
    for (int v : adj[u]) {
        if (!vis[v]) dfs(v, adj, vis);
    }
}

cpp

def dfs(u, adj, vis):
    vis[u] = True
    for v in adj[u]:
        if not vis[v]:
            dfs(v, adj, vis)

python

DFS 在遍历过程中会将边分为树边（首次到达顶点的边）和非树边（回边、前向边、交叉边）。这个分类在后续的环检测、强连通分量等算法中至关重要。

flowchart TD
    A((A)) --> B((B))
    B --> C((C))
    C --> A
    B --> D((D))
    D --> A

DFS 判断环#

无向图：在 DFS 过程中，如果发现一条边连向一个已经访问过且不是当前顶点直接父亲的顶点，则该边是一条回边，说明图中存在环。

有向图：使用三色标记法——白色表示未访问，灰色表示正在递归栈中（尚未回溯），黑色表示已处理完毕。如果在 DFS 中遇到一条边指向灰色顶点，则说明存在回边，即存在环。

flowchart LR
    A((A)) --> B((B))
    B --> C((C))
    C --> B

Tarjan 求强连通分量#

在有向图中，如果任意两个顶点都互相可达，则称该图是强连通的。有向图的强连通分量 (SCC) 是指极大的强连通子图——即不能再加入更多顶点而保持强连通性。

Tarjan 算法是求 SCC 最经典的方法，它基于 DFS 一次遍历即可完成，时间复杂度 $O(V+E)$ .

核心概念#

算法维护两个关键数组：

dfn[u]：顶点 $u$ 在 DFS 中的访问时间戳（第几个被访问的）
low[u]：顶点 $u$ 通过其子树中的回边能到达的最早的祖先的 dfn 值

初始时 low[u] = dfn[u]. 在 DFS 回溯时更新：

如果 $v$ 是 $u$ 的树边子节点：low[u] = min(low[u], low[v])
如果 $v$ 已经在栈中（回边）：low[u] = min(low[u], dfn[v])

算法流程#

从某个未访问的顶点开始 DFS，维护一个全局时间戳 timer 和一个栈
进入顶点 $u$ 时，设 dfn[u] = low[u] = ++timer，并将 $u$ 压入栈
对 $u$ $u$ 的每个邻居 $v$ $v$ ：
- 如果 $v$ 未访问，递归 DFS( $v$ )，回溯后 low[u] = min(low[u], low[v])
- 如果 $v$ 已在栈中，low[u] = min(low[u], dfn[v])
当 low[u] == dfn[u] 时，说明 $u$ 是一个 SCC 的根：从栈中不断弹出顶点直到弹出 $u$ ，这些顶点构成一个 SCC

void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    stk.push(u); in_stk[u] = true;
    for (int v : adj[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stk[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        // 弹出一个 SCC
        int v;
        do {
            v = stk.top(); stk.pop();
            in_stk[v] = false;
            // v 属于当前 SCC
        } while (u != v);
    }
}

cpp

flowchart TD
    A((0)) --> B((1))
    B --> C((2))
    C --> A
    B --> D((3))
    D --> C
    D --> E((4))
    E --> D

正确性分析#

Tarjan 算法的正确性基于以下观察：

每个 SCC 在 DFS 树中形成一棵子树（可能不完整，但根一定在其中）
low[u] 本质上在追踪 $u$ 所在的 SCC 中 dfn 最小的顶点
当 low[u] == dfn[u] 时，说明 $u$ 就是该 SCC 的根——因为从 $u$ 出发无法通过任何回边到达更早的顶点
栈保证了 SCC 按照 DFS 完成顺序被识别，不会出现跨越 SCC 的遗漏

最小生成树（Minimum Spanning Tree, MST）#

给定一个连通无向赋权图 $G=(V,E)$ ，其最小生成树 (MST) 是包含所有顶点的一棵树（即 $V$ 的子集， $|V|-1$ 条边），使得边的权值之和最小。

Kruskal#

Kruskal 算法的思想非常直观：贪心地从小到大考虑边，如果加入这条边不会形成环，就把它加入 MST。

将所有边按权值从小到大排序
依次考虑每条边 $(u, v)$ $(u, v)$ ：
- 如果 $u$ 和 $v$ 当前不在同一个连通分量中，加入这条边并合并两个分量
- 否则跳过（会形成环）
当 MST 中已有 $|V|-1$ 条边时停止

算法的核心数据结构是并查集 (Disjoint Set Union, DSU)，用于高效地查询和合并连通分量。

struct Edge { int u, v, w; };
bool operator<(const Edge& a, const Edge& b) { return a.w < b.w; }

int find(int x, vector<int>& parent) {
    return parent[x] == x ? x : parent[x] = find(parent[x], parent);
}

int kruskal(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end());
    vector<int> parent(n);
    iota(parent.begin(), parent.end(), 0);
    int mst_weight = 0, edges_cnt = 0;
    for (auto& e : edges) {
        int ru = find(e.u, parent), rv = find(e.v, parent);
        if (ru != rv) {
            parent[ru] = rv;
            mst_weight += e.w;
            if (++edges_cnt == n - 1) break;
        }
    }
    return mst_weight;
}

cpp

时间复杂度： $O(E \log E)$ （排序占主导，并查集操作近似 $O(1)$ ）

空间复杂度： $O(V + E)$

Prim#

Prim 算法从任意一个顶点出发，逐步扩展 MST。它维护一个「已在 MST 中的顶点集合」 $S$ ，每一步选择连接 $S$ 和 $V \setminus S$ 的权值最小的边，将其另一端点加入 $S$ .

任选起点 $s$ ，初始化所有顶点到 $S$ 的距离为 $\infty$ （ $s$ 为 $0$ ）
用优先队列维护每个顶点到 $S$ 的最小边权
每次取出距离最小的顶点 $u$ ，将其加入 $S$
对 $u$ 的每个邻居 $v$ ，如果 $(u,v)$ 的权值比 $v$ 当前的距离更小，则更新并加入优先队列
重复 3-4 直到所有顶点都加入 $S$

int prim(int n, const vector<vector<pair<int,int>>>& adj) {
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    vector<int> min_cost(n, INT_MAX);
    vector<bool> in_mst(n, false);
    int mst_weight = 0, cnt = 0;
    
    min_cost[0] = 0;
    pq.push({0, 0}); // {cost, vertex}
    
    while (!pq.empty() && cnt < n) {
        auto [cost, u] = pq.top(); pq.pop();
        if (in_mst[u]) continue;
        in_mst[u] = true;
        mst_weight += cost; cnt++;
        for (auto& [v, w] : adj[u]) {
            if (!in_mst[v] && w < min_cost[v]) {
                min_cost[v] = w;
                pq.push({w, v});
            }
        }
    }
    return mst_weight;
}

cpp

时间复杂度： $O(E \log V)$ （优先队列）
空间复杂度： $O(V + E)$

正确性证明（贪心选择性）#

MST 算法的贪心策略之所以能得到最优解，基于以下关键定理：

Cut Property（割性质）：将顶点集 $V$ 任意划分为 $S$ 和 $V \setminus S$ ，设 $(u, v)$ 是跨越这个割的所有边中权值最小的那条（其中 $u \in S, v \in V \setminus S$ ），则 $(u, v)$ 一定在 MST 中。

证明（反证法）：假设存在一棵 MST $T$ 不包含 $(u, v)$ . 将 $(u, v)$ 加入 $T$ 会形成唯一的一个环，这个环中必然存在另一条跨越割的边 $(u', v')$ . 因为 $(u, v)$ 是最小跨越边，有 $w(u, v) \leq w(u', v')$ . 从 $T$ 中移除 $(u', v')$ 加入 $(u, v)$ 得到一棵新生成树 $T'$ ，其总权值不超过 $T$ ，因此 $T'$ 也是 MST——且包含 $(u, v)$ . $\square$

Kruskal：每条被选中的边都是其对应时刻某个割的最小边
Prim：每次选择的边都是割 $(S, V \setminus S)$ 的最小边

最短路#

Dijkstra#

Dijkstra 算法求解非负权图的单源最短路问题。它的思想和 Prim 非常相似：维护一个「已确定最短路的顶点集合」 $S$ ，每一步从剩余的顶点中选出离源点最近的顶点加入 $S$ ，然后用它更新邻居的距离。

初始化源点距离 $d[s]=0$ ，其余顶点 $d[v]=\infty$
用优先队列按距离从小到大维护所有顶点
取出距离最小的顶点 $u$ （这就是贪心的关键： $u$ 的最短路已经确定）
对 $u$ 的每个邻居 $v$ ，执行松弛操作：如果 $d[u]+w(u,v) < d[v]$ ，则更新 $d[v] = d[u]+w(u,v)$
重复 3-4 直到队列为空

vector<int> dijkstra(int n, const vector<vector<pair<int,int>>>& adj, int s) {
    vector<int> dist(n, INT_MAX);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    dist[s] = 0;
    pq.push({0, s});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;  // 过时条目
        for (auto& [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

cpp

时间复杂度： $O(E \log V)$ （优先队列实现）
空间复杂度： $O(V + E)$

Bellman-Ford#

Bellman-Ford 算法可以处理含负权边的最短路问题，并且能够检测负权环。

算法的核心操作是松弛 (Relaxation)：对边 $(u, v)$ 权值为 $w$ ，如果 $d[u]+w < d[v]$ ，则更新 $d[v] = d[u]+w$ .

初始化 $d[s]=0$ ，其余 $d[v]=\infty$
对所有边执行松弛操作，重复 $|V|-1$ 轮
再执行一轮松弛：如果还有距离可以被更新，说明存在负权环

bool bellman_ford(int n, int s, const vector<tuple<int,int,int>>& edges, vector<int>& dist) {
    fill(dist.begin(), dist.end(), INT_MAX);
    dist[s] = 0;
    for (int i = 0; i < n - 1; i++) {
        bool changed = false;
        for (auto& [u, v, w] : edges) {
            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                changed = true;
            }
        }
        if (!changed) break;  // 提前终止
    }
    // 检查负环
    for (auto& [u, v, w] : edges) {
        if (dist[u] != INT_MAX && dist[u] + w < dist[v])
            return false;  // 存在负环
    }
    return true;
}

cpp

时间复杂度： $O(VE)$
空间复杂度： $O(V + E)$

正确性：在没有负环的情况下，任意两点间的最短路径最多经过 $|V|-1$ 条边（否则有环）。因此 $|V|-1$ 轮松弛足以让所有最短路收敛。如果第 $|V|$ 轮还能松弛，说明存在可以无限缩短的路径——即负权环。

SPFA (Shortest Path Faster Algorithm)#

SPFA 是 Bellman-Ford 的一种队列优化版本。它的核心思想是：只有那些在上一轮中被更新了距离的顶点，才有可能在下一轮中更新它们的邻居。

初始化 $d[s]=0$ ，其余 $\infty$ ，将 $s$ 入队
当队列非空时，弹出队首 $u$
对 $u$ 的每个邻居 $v$ ，执行松弛；如果 $d[v]$ 被更新且 $v$ 不在队列中，则入队
如果某个顶点入队次数超过 $|V|$ 次，说明存在负权环

Floyd#

Floyd-Warshall 算法求解所有点对的最短路问题（APSP）。它基于动态规划，代码极其简洁。

定义 $d^{(k)}[i][j]$ 为「只允许经过前 $k$ 个顶点作为中间节点时， $i$ 到 $j$ 的最短距离」。状态转移方程：

$d^{(k)}[i][j] = \min(d^{(k-1)}[i][j],\ d^{(k-1)}[i][k] + d^{(k-1)}[k][j])$

可以优化掉 $k$ 这一维，直接在原数组上更新：

def floyd_warshall(n, graph):
    dist = [row[:] for row in graph]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    # 检查负环：如果 dist[i][i] < 0 则存在负环
    return dist

python

时间复杂度： $O(V^3)$
空间复杂度： $O(V^2)$

Johnson#

当图含有负权边但没有负环时，如果需要对每一对顶点求最短路，Dijkstra 跑 $|V|$ 次会失败，Floyd 又太慢（ $O(V^3)$ ）。Johnson 算法巧妙地结合了 Bellman-Ford 和 Dijkstra：

新建一个虚拟源点 $s$ ，从 $s$ 向每个顶点连一条权值为 $0$ 的边
从 $s$ 运行 Bellman-Ford，得到每个顶点 $v$ 的最短距离 $h(v)$
重新赋权：将每条边 $(u, v)$ 的权值改为 $w'(u,v) = w(u,v) + h(u) - h(v)$ . 可以证明 $w'(u,v) \geq 0$
在新的非负权图上对每个顶点运行一次 Dijkstra
将 Dijkstra 得到的距离还原： $d(u,v) = d'(u,v) - h(u) + h(v)$

时间复杂度： $O(VE \log V)$ （优先队列实现 Dijkstra）

拓扑排序#

拓扑排序是针对有向无环图（DAG）的一种排序：将顶点排成一个线性序列，使得对于任意有向边 $u \to v$ ， $u$ 在序列中都出现在 $v$ 之前。

Kahn 算法（基于入度）#

统计每个顶点的入度
将所有入度为 $0$ 的顶点入队
每次弹出队首 $u$ ，加入拓扑序列
将 $u$ 的所有邻居的入度减 $1$ ；如果某个邻居入度变为 $0$ ，入队
重复 3-4 直到队列为空
如果拓扑序列中的顶点数小于 $|V|$ ，说明图中存在环（无法拓扑排序）

vector<int> topological_sort(int n, const vector<vector<int>>& adj) {
    vector<int> indeg(n, 0);
    for (int u = 0; u < n; u++)
        for (int v : adj[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 : adj[u]) {
            if (--indeg[v] == 0) q.push(v);
        }
    }
    return order.size() == n ? order : vector<int>();  // 空表示有环
}

cpp

DFS 方法#

另一种方法是利用 DFS 的后序遍历（post-order）：对每个未访问的顶点执行 DFS，在回溯时将顶点压入栈（或列表头部）。最终栈的逆序就是拓扑排序。

时间复杂度：两种方法都是 $O(V + E)$ .

网络流#

最大流#

给定一个流网络——有向图 $G=(V, E)$ ，源点 $s$ ，汇点 $t$ ，每条边有一个非负容量 $c(u, v)$ . 一个流 $f$ 是赋予每条边的值，满足：

容量限制： $0 \leq f(u, v) \leq c(u, v)$
流量守恒：除 $s$ 和 $t$ 外，每个顶点的流入总量等于流出总量

最大流问题：求从 $s$ 到 $t$ 的最大可能的总流量。

Ford-Fulkerson 方法#

Ford-Fulkerson 是一个框架而非具体算法：

从零流开始
在残量网络中找到一条从 $s$ 到 $t$ 的增广路径
沿这条路径增加尽可能多的流量（等于路径上残量的最小值）
重复 2-3 直到找不到增广路径为止

Edmonds-Karp 是基于 BFS 实现的 Ford-Fulkerson 方法，此外还有改进的算法 Dinic.

// Edmonds-Karp：用 BFS 找最短增广路
int edmonds_karp(int n, vector<vector<int>>& cap, int s, int t) {
    int max_flow = 0;
    while (true) {
        // BFS 找增广路
        vector<int> parent(n, -1);
        queue<int> q;
        q.push(s); parent[s] = s;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v = 0; v < n; v++) {
                if (parent[v] == -1 && cap[u][v] > 0) {
                    parent[v] = u; q.push(v);
                }
            }
        }
        if (parent[t] == -1) break;  // 没有增广路
        int flow = INT_MAX;
        for (int v = t; v != s; v = parent[v])
            flow = min(flow, cap[parent[v]][v]);
        for (int v = t; v != s; v = parent[v]) {
            cap[parent[v]][v] -= flow;
            cap[v][parent[v]] += flow;
        }
        max_flow += flow;
    }
    return max_flow;
}

cpp

Edmonds-Karp 时间复杂度： $O(VE^2)$

最小割#

割的定义：将顶点集 $V$ 划分为 $S$ 和 $T = V \setminus S$ ，其中 $s \in S$ ， $t \in T$ . 割的容量是所有从 $S$ 到 $T$ 的边的容量之和。

最小割问题：找到容量最小的 $s$ - $t$ 割。

最大流最小割定理：在任何流网络中，最大流的值等于最小割的容量。

证明思路：

任意可行流的值 $\leq$ 任意割的容量（显然，因为流必须穿过割）

当 Ford-Fulkerson 终止时，残量网络中没有 $s \to t$ 的路径。令 $S$ 为残量网络中从 $s$ 可达的顶点集合， $T = V \setminus S$ .

此时从 $S$ 到 $T$ 的所有原边都已满流（残量为 $0$ ），从 $T$ 到 $S$ 的所有边都为零流。

因此当前流的值恰好等于这个割的容量。由上面的不等式，这既是最大流也是最小割。 $\square$

图着色问题#

图着色：为无向图 $G=(V, E)$ 的每个顶点分配一种颜色，使得相邻顶点颜色不同。色数 $\chi(G)$ 是最少需要的颜色数。

图着色问题是经典的 NP-complete 问题。求解方法包括：

贪心着色：按某种顺序依次为顶点着色，每个顶点选当前可用的最小颜色编号。最坏情况下可能需要 $\Delta+1$ 种颜色（ $\Delta$ 为最大度）
Welsh-Powell 算法：按度数从大到小排序后再贪心着色，通常效果优于简单贪心
回溯搜索：精确求解色数，但指数时间复杂度

Euler 路径/回路问题#

Euler 回路：经过每条边恰好一次且回到起点的闭合迹。
Euler 路径：经过每条边恰好一次但不一定回到起点的迹。

判定条件#

	Euler 回路	Euler 路径
无向连通图	所有顶点度为偶数	恰好 0 或 2 个顶点度为奇数
有向强连通图	每个顶点入度 = 出度	至多一个顶点出度 = 入度+1（起点），至多一个顶点入度 = 出度+1（终点），其余入度 = 出度

Hamilton 路径/回路问题#

Hamilton 回路：经过每个顶点恰好一次且回到起点的回路。
Hamilton 路径：经过每个顶点恰好一次的路径。

与 Euler 路径不同（判边），Hamilton 路径判顶点，这导致了本质上的困难：

判定 Hamilton 回路是否存在是 NP-complete 的
旅行商问题 (TSP) 是 Hamilton 回路的加权优化版本，同样是 NP-hard
目前最好的精确算法仍然是指数时间复杂度

可平面图#

可平面图：可以画在平面上，使得任意两条边只在端点处相交（即没有交叉边）。

欧拉公式#

对于连通的简单平面图，设顶点数为 $V$ ，边数为 $E$ ，面数为 $F$ ，则：

$V - E + F = 2$

由此可以推出一些必要条件：

若 $V \geq 3$ ，则 $E \leq 3V - 6$
若图中没有三角形（最短环长 $\geq 4$ ），则 $E \leq 2V - 4$
平均度 $\frac{2E}{V} < 6$ ，即必然存在度数不超过 $5$ 的顶点

Kuratowski 定理#

一个图是可平面的 充要条件：它不包含 $K_5$ （5 个顶点的完全图）或 $K_{3,3}$ （两部各 3 个顶点的完全二分图）的细分。

细分：在边上插入度为 $2$ 的新顶点，把一条边替换为一条路径。反过来说，如果反复「平滑」度为 $2$ 的顶点后能得到 $K_5$ 或 $K_{3,3}$ ，则原图不可平面。

flowchart LR
    A((1)) --- B((2))
    B --- C((3))
    A --- D((4))
    B --- D
    C --- D
    A ---- C

$K_4$ 是可平面的

flowchart LR
    A((1)) --- B((2))
    B --- C((4))
    A --- D((3))
    D --- B
    D --- C
    A ---- C
	A --- E((5))
	B --- E
	C --- E
	D --- E

$K_5$ 是不可平面的

中心度（Centrality）#

中心度用于量化图中顶点的「重要性」，不同的中心度从不同角度定义重要性：

度中心度 (Degree Centrality)#

$C_D(v) = \frac{d(v)}{n-1}$

度最高的节点最「中心」。例如社交网络中的「社交达人」、疫情中的超级传播者。

接近中心度 (Closeness Centrality)#

$C_C(v) = \frac{n-1}{\sum_{u \neq v} d(v, u)}$

到其他节点平均距离最短的节点最「中心」。适合选址问题，如医院、消防站的位置选择。

介数中心度 (Betweenness Centrality)#

$C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}$

其中 $\sigma_{st}$ 是 $s$ 到 $t$ 的最短路径总数， $\sigma_{st}(v)$ 是经过 $v$ 的最短路径数。介数高的节点是网络中的「守门人」或瓶颈，例如交通枢纽。

特征向量中心度 (Eigenvector Centrality)#

$\lambda x_v = \sum_{u \in N(v)} x_u$

一个节点的重要性不仅取决于邻居的数量，还取决于邻居的重要性。这是 Google PageRank 的基础：

PageRank：在特征向量中心度的基础上增加了随机跳转（阻尼因子 $d$ ），解决了悬挂节点（没有出链的页面）和循环吸收的问题
公式： $PR(p_i) = \frac{1-d}{N} + d \sum_{p_j \in M(p_i)} \frac{PR(p_j)}{L(p_j)}$

中心度	核心思想	典型场景
度	邻居多	社交达人、超级传播者
接近	离大家近	选址：医院、消防站
介数	必经之路	交通枢纽、信息守门人
特征向量	重要的人认为我重要	PageRank、论文影响力