w wyl123ly 的博客
MD

算法-图算法

58 KB 2026.10.11 原文件

算法-图算法

这篇笔记讲什么

图算法是「把现实问题翻译成点和边」之后的一整套工具箱。本篇按问题类型组织:遍历(BFS/DFS)→ 最短路(Dijkstra / Bellman-Ford / Floyd / A\*)→ 连通性(并查集 / Tarjan 强连通分量)→ 生成树(Kruskal / Prim)→ 依赖顺序(拓扑排序)→ 网络流与匹配(Edmonds-Karp / 匈牙利算法),并在最后给出选型速查表。

读完你应该能:拿到一个图论问题先判断它属于哪一类、选对算法、说清每个算法的前提与失效条件(尤其是 Dijkstra 为什么怕负权边),并手写出主要算法的 Python 实现。

一、是什么:图与图算法的分类

图(Graph) 由顶点集 和边集 组成。边可以带方向(有向图)或不带(无向图),可以带权(weight)或不带。

图算法的四大类:

类别要回答的问题代表算法
遍历与连通性能不能到?有几块?有没有环?是不是二分图?BFS、DFS、并查集、Tarjan
最短路径从 到 的最小代价是多少?Dijkstra、Bellman-Ford、Floyd-Warshall、A\*
生成树用最小总代价把所有点连起来Kruskal、Prim
流与匹配最大能同时满足多少约束?Ford-Fulkerson、Edmonds-Karp、匈牙利算法

二、为什么需要它 / 适用条件

图的表示方式决定了算法的复杂度,这是最容易忽略的前置选择:

表示空间判断 遍历 的邻居适用
邻接矩阵 adj[u][v]稠密图、、需要快速查边
邻接表 graph[u] = [...]稀疏图、绝大多数场景的默认选择
边列表 edges = [(u,v,w)]Kruskal、Bellman-Ford

读题先看数据范围,再选算法

- :随便写,Floyd 也扛得住。

- 、 接近 (稠密):朴素 Dijkstra 或 Prim 。

- :优先队列 Dijkstra 、Kruskal 。

- 边权可能为负:不能用 Dijkstra,改用 Bellman-Ford / SPFA / Floyd。

- 且要「访问所有点」:状压 DP(见 算法-动态规划与贪心 的 TSP)。

图论建模四步法

图论题的难点 90% 在建模,而不是算法本身。拿到题先回答四个问题:

  1. 点是什么?(城市、状态、任务、格子、人)
  2. 边是什么?(能直接到达、依赖关系、冲突关系、可以配对)
  3. 边权是什么?(距离、时间、代价、容量;没有权就是「经过一条边算一步」)
  4. 求什么?(可达性 → 遍历;最小代价 → 最短路;最小连通代价 → MST;最大同时满足量 → 最大流/匹配;顺序 → 拓扑排序)

常见建模套路:

原问题建图方式
网格中从起点到终点最少步数每个格子是点,上下左右相邻是边,BFS
单词接龙(每次改一个字母)单词是点,只差一个字母的两个单词连边,BFS
课程先修关系能否完成课程是点,先修关系是边,拓扑排序 / 判环
判断两个人是否是朋友的朋友人是点,朋友关系是边,并查集
最少需要几门课并行课程是点,依赖是边,拓扑排序 + 分层计数
状态转移的最少操作次数状态是点,一次操作是边,BFS(隐式图)
任务分配 / 课程与老师配对二分图,左边任务右边资源,匈牙利算法

「状态是点」是图论建模最高频的一招

当题目问「从初始状态到目标状态最少需要多少步操作」时,把每个状态当成一个点、一次操作当成一条边,问题立刻变成无权图最短路,直接 BFS。例如「打开转盘锁」「单词接龙」「倒水问题」都属此类。图的规模可能极大(状态数爆炸),此时必须靠剪枝或双向 BFS。

三、核心内容:BFS / DFS 及其典型应用

广度优先搜索(Breadth-First Search, BFS) 按「距离起点的层数」逐层扩展,用队列实现;深度优先搜索(Depth-First Search, DFS) 沿一条路走到底再回退,用栈(递归)实现。

维度BFSDFS
数据结构队列(FIFO)栈 / 递归
访问顺序按层,距离非递减沿分支深入
无权图最短路✅ 首次到达即最短❌ 不保证
空间,最坏 ,最坏
天然用途最短路、层序、扩散连通块、环检测、拓扑序、回溯
实现复杂度稍繁(需队列)简单(递归)

3.1 连通块计数

from collections import deque

def count_components(n, edges):
    """无向图连通块计数(DFS 洪水填充)。O(V + E)"""
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    seen = [False] * n
    count = 0

    def dfs(start):
        stack = [start]
        seen[start] = True
        while stack:                       # 显式栈,避免递归深度限制
            u = stack.pop()
            for v in graph[u]:
                if not seen[v]:
                    seen[v] = True         # 入栈时立刻标记,防止重复入栈
                    stack.append(v)

    for i in range(n):
        if not seen[i]:                    # 每发现一个未访问点就是一个新连通块
            count += 1
            dfs(i)
    return count

网格版(LeetCode 200 岛屿数量):把二维网格隐式地看成图,每格与上下左右相邻。连通块计数就是「数有几块陆地」。

def num_islands(grid):
    """LeetCode 200 岛屿数量:网格 DFS 洪水填充。O(mn)"""
    if not grid or not grid[0]:
        return 0
    m, n = len(grid), len(grid[0])
    count = 0

    def sink(sr, sc):
        """把与 (sr, sc) 相连的陆地全部「沉掉」,避免重复计数"""
        stack = [(sr, sc)]
        grid[sr][sc] = "0"
        while stack:
            r, c = stack.pop()
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == "1":
                    grid[nr][nc] = "0"     # 标记已访问,直接改原数组省空间
                    stack.append((nr, nc))

    for i in range(m):
        for j in range(n):
            if grid[i][j] == "1":
                count += 1
                sink(i, j)
    return count

3.2 无权图最短路径

def bfs_dist(graph, start):
    """无权图单源最短路:BFS 首次访问即最短。返回 {节点: 距离}"""
    dist = {start: 0}
    q = deque([start])
    while q:
        u = q.popleft()
        for v in graph[u]:
            if v not in dist:              # 首次到达 = 最短距离已确定
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

为什么 BFS 首次到达就是最短

BFS 出队顺序保证「距离 的节点一定在距离 的节点之前全部出队」。设首次访问 时距离为 ,若存在更短的路径 ,那条路径上的前驱会在更早的层被处理并把 入队,矛盾。这个论证只在边权相等(都为 1)时成立——一旦边权不同,"层" 的概念就不存在了,必须用 Dijkstra。

3.3 环检测

无向图:DFS 时若遇到一个「已访问且不是自己父亲」的邻居,就存在环。有向图不能用这一招(两条不同路径汇合不算环),要用三色标记法。

def has_cycle_undirected(n, edges):
    """无向图环检测:DFS + 记录父亲节点。O(V + E)"""
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    seen = [False] * n

    def dfs(u, parent):
        seen[u] = True
        for v in graph[u]:
            if not seen[v]:
                if dfs(v, u):
                    return True
            elif v != parent:              # 已访问且不是父亲 → 找到了环
                return True
        return False

    return any(not seen[i] and dfs(i, -1) for i in range(n))


def has_cycle_directed(n, edges):
    """有向图环检测:三色标记 DFS。
    白色 = 未访问,灰色 = 在当前递归栈上,黑色 = 全部后继已处理完"""
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)

    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n

    def dfs(u):
        color[u] = GRAY
        for v in graph[u]:
            if color[v] == GRAY:           # 指向递归栈上的节点 → 有向环
                return True
            if color[v] == WHITE and dfs(v):
                return True
        color[u] = BLACK
        return False

    return any(color[i] == WHITE and dfs(i) for i in range(n))

无向图环检测的另一个办法:并查集

依次处理每条边 :若 find(u) == find(v),说明 、 早已连通,这条边就构成一个环;否则 union(u, v)。这个写法比 DFS 更短,且天然支持动态加边(LeetCode 684 冗余连接就是这一招)。

3.4 二分图判定

二分图(Bipartite Graph):顶点可分成两个集合,使每条边的两个端点分属不同集合。等价于「图中不存在长度为奇数的环」。

def is_bipartite(graph):
    """二分图判定:BFS 二染色。O(V + E)"""
    color = {}
    for s in range(len(graph)):
        if s in color:
            continue
        color[s] = 0                       # 未染色节点任取一色
        q = deque([s])
        while q:
            u = q.popleft()
            for v in graph[u]:
                if v not in color:
                    color[v] = color[u] ^ 1         # 染成相反色
                    q.append(v)
                elif color[v] == color[u]:
                    return False                    # 相邻同色 → 出现奇环
    return True

四、最短路算法

4.1 Dijkstra:单源、非负权

核心思想:贪心。维护一个「已确定最短距离」的集合 ,每轮从 中取出 最小的点 加入 ,并用 松弛它的邻居。正确性依赖边权非负:只有这样,「当前 最小的未确定点,其距离不可能再被后续路径改小」。

(1)朴素实现(邻接矩阵 + 线性找最小):。

def dijkstra_dense(n, adj, src):
    """朴素 Dijkstra(邻接矩阵)。adj[u][v] = 权或 INF。O(V^2),适合稠密图"""
    INF = float("inf")
    dist = [INF] * n
    used = [False] * n
    dist[src] = 0
    for _ in range(n):
        u = -1
        for i in range(n):                 # 线性扫描找未确定的最小 dist
            if not used[i] and (u == -1 or dist[i] < dist[u]):
                u = i
        if u == -1 or dist[u] == INF:
            break                          # 剩余点都不可达,提前结束
        used[u] = True                     # u 的最短距离就此确定
        for v in range(n):
            if adj[u][v] < INF and dist[u] + adj[u][v] < dist[v]:
                dist[v] = dist[u] + adj[u][v]
    return dist

(2)优先队列实现(堆优化):。

import heapq

def dijkstra(n, graph, src):
    """堆优化 Dijkstra。graph[u] = [(v, w), ...]。O((V + E) log V)"""
    INF = float("inf")
    dist = [INF] * n
    dist[src] = 0
    pq = [(0, src)]                        # (当前距离, 节点)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                       # 过期条目(懒惰删除),跳过
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))     # 同一节点允许多次入队
    return dist

分步推演:图有顶点 ,边 权 1, 权 4, 权 1, 权 1。求从 0 出发的最短路。

轮次出堆dist说明
初始—[0, ∞, ∞, ∞]起点入堆
1[0, 1, 4, ∞]松弛 、
2[0, 1, 2, ∞]走 比 更短,更新为 2
3[0, 1, 2, 3]松弛
4[0, 1, 2, 3]无出边

Dijkstra 为什么不能处理负权边

Dijkstra 的正确性建立在一条贪心断言上:「当前 最小的未确定点,其距离已经不可能再变小」。这条断言要求「后续任何路径的代价都不会减少」——即边权非负。一旦有负权边,绕远路反而可能更便宜,断言失效。

反例:三个顶点 ,边 权 , 权 , 权 。

- Dijkstra 的执行:从 0 出发,、;堆中最小的是 ,于是把顶点 1 标记为已确定(此后不再更新它)。接着处理顶点 2,发现 ,但顶点 1 已被「确定」,更新被跳过。

- 结果:Dijkstra 返回 ,而真实最短距离是 。

修法:改用 Bellman-Ford / SPFA(能处理负权,还能判负环);或先用 Johnson 算法做势能重标定(reweighting)把所有边权变成非负,再跑 Dijkstra。

变体:边权只有 0 和 1 时用 0-1 BFS

若边权只有 0 与 1,把队列换成双端队列(deque):权为 0 的边把邻居压入队首、权为 1 的压入队尾,即可在 内求出最短路,比堆优化的 更快。

4.2 Bellman-Ford:允许负权,且能判负环

核心思想:不再贪心,而是暴力地反复松弛所有边。松弛 轮的理由是:

从 到任意点的最短路径一定是简单路径(若含环,去掉环只会更短或不变——负环除外),所以最多包含 条边。第 轮松弛后,所有「最多用 条边」的最短路都已确定。因此 轮后,所有最短路都已被确定。

判负环:若第 轮还能松弛成功,说明存在一条含 条边却更短的路径,即路径中必有环且该环权为负——存在从源点可达的负环(此时最短距离无定义,为 )。

def bellman_ford(n, edges, src):
    """Bellman-Ford:返回 (dist, 是否存在可达负环)。edges = [(u, v, w)]。O(VE)"""
    INF = float("inf")
    dist = [INF] * n
    dist[src] = 0

    for _ in range(n - 1):                 # 最多松弛 n-1 轮
        updated = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:                    # 本轮无任何更新 → 已收敛
            break

    # 第 n 轮仍能松弛 ⇒ 存在从 src 可达的负环
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            return dist, True
    return dist, False

SPFA(Shortest Path Faster Algorithm) 是 Bellman-Ford 的队列优化版:只有「距离被更新过的点」才有必要去松弛它的邻居,因此用队列维护待松弛的点。

def spfa(n, graph, src):
    """SPFA:队列优化的 Bellman-Ford。平均 O(E),最坏 O(VE)。
    graph[u] = [(v, w), ...]。返回 dist;检测到负环返回 None"""
    INF = float("inf")
    dist = [INF] * n
    in_queue = [False] * n
    enter_count = [0] * n                  # 每个点的入队次数,用于判负环
    dist[src] = 0
    q = deque([src])
    in_queue[src] = True
    enter_count[src] = 1

    while q:
        u = q.popleft()
        in_queue[u] = False
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if not in_queue[v]:
                    q.append(v)
                    in_queue[v] = True
                    enter_count[v] += 1
                    if enter_count[v] >= n:    # 入队 >= n 次 ⇒ 存在负环
                        return None
    return dist

SPFA 已经「死」了——什么时候不能用它

SPFA 的最坏复杂度是 ,且这一上界能被构造出来。竞赛中专门有针对 SPFA 的「网格菊花图」数据,可以把 实际跑满,导致超时(这就是「SPFA 已死」说法的由来)。实践建议:

- 边权非负 → 一律用 Dijkstra,正确且稳定 ;

- 需要判负环 → 用朴素 Bellman-Ford(复杂度确定,)或队列 + 计数判环的 SPFA;

- 确实需要 SPFA → 加上 SLF / LLL 优化,并做好被卡的心理准备。

另外,负环判定要注意「可达性」:只有从源点可达的负环才会让 dist 无意义。若图不连通,需要对每个未访问的连通块单独跑一次,或加一个虚拟超级源点连向所有点。

4.3 Floyd-Warshall:全源最短路

核心思想:区间/阶段 DP。状态 dp[k][i][j] = 「只允许经过前 个顶点作为中转时, 到 的最短距离」。

空间优化:第 轮只依赖第 轮,且 dp[i][k]、dp[k][j] 在第 轮中不会被改小(无负环时 不会变),所以可以原地滚动,把三维压成二维,空间从 降到 。

def floyd(n, adj):
    """Floyd-Warshall 全源最短路。adj 是 n x n 邻接矩阵,无边处为 INF。O(V^3)"""
    INF = float("inf")
    dist = [row[:] for row in adj]         # 原地滚动:直接复用二维数组
    for i in range(n):
        dist[i][i] = 0                     # 自己到自己是 0
    for k in range(n):                     # ★ 中转点 k 必须在最外层
        dk = dist[k]
        for i in range(n):
            dik = dist[i][k]
            if dik == INF:                 # 剪枝:i 到 k 不可达,松弛无意义
                continue
            di = dist[i]
            for j in range(n):
                nd = dik + dk[j]
                if nd < di[j]:
                    di[j] = nd
    return dist

三重循环的顺序为什么不能颠倒

正确的顺序是 (中转点)→ (起点)→ (终点), 必须在最外层。原因是 DP 的阶段是中转点集合的大小:第 轮结束时,我们只保证「允许用前 个点中转」的答案是正确。

若把 放到最外层,算法就变成「对每个起点 ,枚举中转点 和终点 」——但此时 可能还没有利用 之后的中转点更新过,甚至可能存在「先用 更新了 ,但 之后再被 改小」的情况,导致 用的是过期的 。结果会偏大(漏掉更优路径),而且不会报错——这正是它成为经典陷阱的原因。

记忆法:「中转点是阶段,起点终点是状态」。阶段永远在最外层。

Floyd 的三个常见用途:

用途做法
全源最短路直接跑
传递闭包(可达性)把 min/+ 换成 or/and,布尔矩阵运算
最小环(无向图)在 循环内、更新 dist 之前检查 dist[i][j] + w(i,k) + w(k,j)

4.4 A\* 启发式搜索

A\* 是「Dijkstra + 目标导向的启发式」。它把优先队列的排序键从 (起点到 的真实代价)换成

其中 是「 到目标代价的估计」,称为估价函数(heuristic)。

概念定义作用
可采纳性(admissible) 真实的 最短距离(绝不高估)保证 A\* 找到的是最优解
一致性 / 单调性(consistent) 且 保证每个点只被扩展一次,效率更高
完全不估计A\* 退化为 Dijkstra
高估不可采纳变成贪心最优搜索,可能返回次优解
def astar(n, graph, start, goal, heuristic):
    """A* 搜索。graph[u] = [(v, w), ...],heuristic(u) 是到 goal 的估计代价(必须可采纳)。
    返回从 start 到 goal 的最短距离;不可达返回 inf"""
    INF = float("inf")
    g = [INF] * n
    g[start] = 0
    pq = [(heuristic(start), start)]       # 按 f = g + h 排序
    closed = [False] * n
    while pq:
        _, u = heapq.heappop(pq)
        if u == goal:
            return g[u]                    # 首次弹出 goal 即为最优(依赖可采纳性)
        if closed[u]:
            continue                       # 同一节点可能有多个过期条目
        closed[u] = True
        for v, w in graph[u]:
            ng = g[u] + w
            if ng < g[v]:
                g[v] = ng
                heapq.heappush(pq, (ng + heuristic(v), v))
    return INF


def manhattan(a, b):
    """网格地图上常用的可采纳启发式:曼哈顿距离(只允许四方向移动时)"""
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

分步推演(直观对比):在网格地图上从左上角走到右下角,障碍物很少。

算法扩展的节点形态扩展数量
BFS以起点为中心的同心方环全部可达格
Dijkstra以起点为中心的同心圆(等代价扩散)全部可达格
A\*(曼哈顿启发式)一条朝目标方向拉长的椭圆带通常远少于前两者

**A\* 什么时候会退化甚至出错**

- 高估(例如在有障碍的网格里仍用曼哈顿距离,但允许八方向移动时曼哈顿距离会高估)→ 失去最优性保证。

- 恒为 0 → 退化成 Dijkstra,只是白写了启发式。

- 地图有大量「陷阱」结构(目标被墙围住只剩一个小口)→ 启发式会把搜索拉向墙,扩展量可能超过 Dijkstra。这是 A\* 在实际寻路中需要配合「跳点搜索(JPS)」「分层寻路」的原因。

五、并查集(Disjoint Set Union, DSU)

是什么:维护一组不相交集合的数据结构,支持两个操作——find(x) 查询 属于哪个集合,union(a, b) 合并两个集合。

为什么需要它:处理「动态连通性」问题。BFS/DFS 只能在静态图上求连通块,一旦边是逐条加入的,重复跑 BFS 就太慢;并查集能在几乎 的时间内维护连通性。

两个关键优化:

优化做法单独使用的复杂度
路径压缩(Path Compression)find 时把路径上所有点直接挂到根上均摊
按秩合并(Union by Rank)把矮树接到高树上,避免退化成链均摊
两者结合—均摊

是什么量级

是反阿克曼函数(inverse Ackermann function),增长极其缓慢:。也就是说,对任何能写进宇宙的 ,单次操作的均摊代价都不超过 5 次基本操作——可以当作 使用。这个结论由 Tarjan 与 van Leeuwen 证明(路径压缩 + 按秩合并的均摊界为 );注意它是均摊而非最坏,单次 find 最坏仍可能走 步。

class DSU:
    """并查集:路径压缩 + 按秩合并,单次操作均摊 O(alpha(n)) ≈ O(1)"""

    def __init__(self, n):
        self.parent = list(range(n))       # 初始时每个点自成一个集合
        self.rank = [0] * n                # 秩 = 树高的上界
        self.count = n                     # 当前连通块个数

    def find(self, x):
        root = x
        while self.parent[root] != root:   # 第一步:找到根
            root = self.parent[root]
        while self.parent[x] != root:      # 第二步:路径压缩(迭代实现,无递归风险)
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                   # 已在同一集合(可用于判环)
        if self.rank[ra] < self.rank[rb]:  # 矮树接高树,控制树高
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1             # 两棵同高树合并,高度 +1
        self.count -= 1
        return True

    def connected(self, a, b):
        return self.find(a) == self.find(b)

朋友圈问题(LeetCode 547 省份数量):把每个人看成点,互为朋友的两个点合并,最后连通块个数就是省份数。

def find_circle_num(is_connected):
    """LeetCode 547 省份数量:并查集统计连通块。O(n^2 * alpha(n))"""
    n = len(is_connected)
    dsu = DSU(n)
    for i in range(n):
        for j in range(i + 1, n):
            if is_connected[i][j] == 1:
                dsu.union(i, j)
    return dsu.count

并查集判环(无向图):依次处理每条边 ;若 find(u) == find(v),说明这条边连接的两个点已经连通,加入它必然成环。

def find_redundant_connection(edges):
    """LeetCode 684 冗余连接:找出使图成环的那条边。O(n * alpha(n))"""
    n = len(edges)
    dsu = DSU(n + 1)                       # 题目顶点编号是 1..n
    for u, v in edges:
        if not dsu.union(u, v):            # 合并失败 ⇒ u、v 本就连通 ⇒ 这条边多余
            return [u, v]
    return []

六、最小生成树(Minimum Spanning Tree, MST)

是什么:在连通无向带权图中选出一棵包含全部 个顶点、恰好 条边的树,使边权总和最小。

理论基础——切分定理(Cut Property):把顶点集任意划分成 与 两部分(称为一个切分/cut),横跨该切分的权值最小的边一定属于某棵最小生成树。

切分定理如何同时支撑 Kruskal 与 Prim

- Kruskal 每次取的边,都是「当前连通块集合」与「其余点」这个切分中最小的边(因为边已按权排序)→ 由切分定理,它必在某棵 MST 中。

- Prim 每次取的边,都是「已选顶点集 」与「」这个切分中最小的边 → 同样由切分定理保证正确。

两者的差别只是切分的构造方式不同:Kruskal 是全局从小到大扫边(切分由并查集隐式决定),Prim 是从一个点开始向外生长(切分是显式的已选集合)。

6.1 Kruskal:按边贪心 + 并查集

1. 把所有边按权值升序排序
2. 依次考虑每条边 (u, v, w):若 u 与 v 尚未连通(并查集判环),就加入这条边
3. 直到选满 V-1 条边

def kruskal(n, edges):
    """Kruskal 最小生成树。edges = [(w, u, v), ...]。
    返回 (总权重, 选中的边列表);图不连通时选不满 n-1 条边。O(E log E)"""
    dsu = DSU(n)
    total = 0
    chosen = []
    for w, u, v in sorted(edges):          # 按边权升序(元组排序先比 w)
        if dsu.union(u, v):                # 不构成环才加入
            total += w
            chosen.append((u, v, w))
            if len(chosen) == n - 1:       # 已够 n-1 条边 ⇒ MST 完成
                break
    return total, chosen

6.2 Prim:按点贪心 + 优先队列

1. 任选一个点作为起点加入集合 S
2. 用优先队列维护「从 S 出发能到达 S 外各点的最小边权」
3. 每轮取出最小的一条跨越边,把对应点加入 S
4. 重复 V-1 次
def prim(n, graph, start=0):
    """Prim 最小生成树(堆优化)。graph[u] = [(v, w), ...]。O(E log E)"""
    used = [False] * n
    total = 0
    pq = [(0, start)]                      # (边权, 顶点)
    while pq:
        w, u = heapq.heappop(pq)
        if used[u]:
            continue                       # 该点已通过更小的边加入过
        used[u] = True
        total += w                         # 起点那次的 w 是 0,不影响结果
        for v, nw in graph[u]:
            if not used[v]:
                heapq.heappush(pq, (nw, v))
    return total

6.3 稠密图与稀疏图选型

维度KruskalPrim(堆优化)Prim(朴素邻接矩阵)
复杂度
适合稀疏图()稀疏图,略快于 Kruskal稠密图()
依赖结构并查集优先队列邻接矩阵
能否处理不连通图能,直接得到最小生成森林需对每个连通块分别跑同左
特殊优势天然支持「边已排序」或「动态加边」的场景不需要预先知道所有边(可流式读入)常数小, 时最实用

怎么选

一句话:边少用 Kruskal,点少边多用朴素 Prim。 竞赛中 的稀疏图基本都用 Kruskal(写起来短、不用建图)。若边权是「点之间的欧氏距离」(完全图,,例如 LeetCode 1584 连接所有点的最小费用),则必须用 Prim,否则光是枚举 条边就已经是上限。

七、拓扑排序:处理依赖关系

是什么:对有向无环图(DAG)的顶点排出一个线性序列,使每条边 中 都排在 之前。存在拓扑序 ⟺ 图中无环。

Kahn 算法(BFS 版):反复取出入度为 0 的点,并「删除」它的出边(把邻居入度减 1)。

def topological_sort(n, edges):
    """Kahn 算法拓扑排序。edges = [(u, v)] 表示 u 必须先于 v。
    返回拓扑序;若存在环则返回 None。O(V + E)"""
    graph = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        graph[u].append(v)
        indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)   # 入度 0 ⇒ 没有前置依赖
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1                  # 相当于删掉边 u -> v
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else None    # 输出不全 ⇒ 有环

DFS 版:后序遍历的逆序就是拓扑序(因为一个点的所有后继都先于它完成)。

def topo_sort_dfs(n, graph):
    """DFS 拓扑排序:后序逆序。返回拓扑序,有环返回 None"""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    order = []
    ok = True

    def dfs(u):
        nonlocal ok
        color[u] = GRAY
        for v in graph[u]:
            if color[v] == GRAY:           # 反向边 ⇒ 有环
                ok = False
                return
            if color[v] == WHITE:
                dfs(v)
        color[u] = BLACK
        order.append(u)                    # 后序位置:所有后继都已入列

    for i in range(n):
        if color[i] == WHITE:
            dfs(i)
    order.reverse()                        # 后序逆序 = 拓扑序
    return order if ok else None

典型应用:

场景建模方式
课程表 / 编译顺序课程或模块是点,先修依赖是边;拓扑序给出可行学习/编译顺序,判环即「无法完成」
任务调度最短工期拓扑序 + DP:dp[v] = max(dp[v], dp[u] + time[u]),答案取 max
并行任务的最少轮数Kahn 算法按层计数(每轮取出当前所有入度 0 的点)
字典序最小的拓扑序把队列换成最小堆(LeetCode 1203 项目管理即此类)
表达式求值 / 电子表格依赖单元格是点,公式引用是边,拓扑序保证先算被依赖者
def min_semesters(n, relations):
    """并行修课的最少学期数:Kahn 按层推进。O(V + E)"""
    graph = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in relations:
        graph[u].append(v)
        indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    semesters = 0
    done = 0
    while q:
        semesters += 1                     # 这一层可以并行修完
        for _ in range(len(q)):            # 只处理当前层的点
            u = q.popleft()
            done += 1
            for v in graph[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    q.append(v)
    return semesters if done == n else -1  # 有环 ⇒ 无法全部完成

八、强连通分量(Tarjan 算法)

是什么:有向图的强连通分量(Strongly Connected Component, SCC) 是极大的顶点集合,其中任意两点互相可达。

为什么需要它:SCC 是把有向图「压缩成 DAG」的工具。缩点之后,原图变成一个 DAG,于是拓扑排序、DAG 上 DP 等工具全都能用了。典型应用:2-SAT 判定、受欢迎的牛、缩点后求最长路。

Tarjan 算法的核心:一次 DFS,用两个数组维护信息:

  • index[u]: 被访问的时间戳(第几个被访问);
  • low[u]:从 出发,能追溯到的最小时间戳(沿 DFS 树边与指向栈内节点的边)。

当 low[u] == index[u] 时, 就是当前 SCC 的「根」,从栈顶弹出到 为止的所有点构成一个 SCC。

import sys

def tarjan_scc(n, graph):
    """Tarjan 求有向图强连通分量。graph[u] = [v, ...](有向)。
    返回分量列表,每个分量是顶点列表。O(V + E)"""
    sys.setrecursionlimit(max(1000, 2 * n + 10))
    index = [0] * n                        # 0 表示尚未访问
    low = [0] * n
    on_stack = [False] * n
    stack = []
    counter = 0
    sccs = []

    def dfs(u):
        nonlocal counter
        counter += 1
        index[u] = low[u] = counter
        stack.append(u)
        on_stack[u] = True
        for v in graph[u]:
            if index[v] == 0:              # 树边:递归后回传 low
                dfs(v)
                low[u] = min(low[u], low[v])
            elif on_stack[v]:              # 指向栈内节点 → 可追溯(横叉边不算)
                low[u] = min(low[u], index[v])
        if low[u] == index[u]:             # u 是本 SCC 的根
            comp = []
            while True:
                w = stack.pop()
                on_stack[w] = False
                comp.append(w)
                if w == u:
                    break
            sccs.append(comp)

    for i in range(n):
        if index[i] == 0:
            dfs(i)
    return sccs

Tarjan 的两个易错点

1. elif on_stack[v] 这个条件不能省:若 已访问但不在栈上,说明 属于一个已经结算完的 SCC,它是「横叉边」的目标,不能用 index[v] 更新 low[u],否则会把两个不相干的 SCC 错误地合并。这是 Tarjan 最常见的错误。

2. 递归深度:链状图会让 DFS 深度达到 。 时必须调大递归上限,或改写成迭代版 Tarjan(实践上更多人改用 Kosaraju 的两遍 DFS,或直接写法相对好懂的迭代实现)。

另一种实现:Kosaraju 算法——做两遍 DFS:第一遍在原图上求「完成时间」的逆序,第二遍在反图上按该逆序 DFS,每次 DFS 得到的点集就是一个 SCC。它比 Tarjan 好懂,但需要同时存原图和反图。

九、网络流:最大流简介

是什么:在一个有向图中,每条边有容量 ,源点 无限出水、汇点 无限收水,求从 到 的最大流量。约束有两条:

  1. 容量限制:;
  2. 流量守恒:除 、 外,每个点流入量 = 流出量。

核心定理——最小割最大流定理(Max-Flow Min-Cut Theorem):

即最大流的值等于最小割的容量。它把「求最大流」与「求最小代价切断」这两个看似不同的问题统一起来,是网络流所有应用的基石。

Ford-Fulkerson 方法:只要残量网络中还存在 的路径(增广路),就沿它推流,并建立反向边允许「撤销」之前的决策。

反向边为什么必须存在

反向边是 Ford-Fulkerson 正确性的关键:它让算法能够「反悔」。若某次推流占用了本可以更优使用的边,反向边提供了一条把流量退回去的通道。没有反向边,贪心推流会卡在局部最优。 实现上,正向边与反向边成对存储(编号 e 与 e^1),推流时正向减、反向加。

算法找增广路的方式复杂度备注
Ford-Fulkerson(DFS)任意路径容量为无理数时可能不终止
Edmonds-KarpBFS 找最短增广路与容量数值无关,稳定可靠
DinicBFS 分层 + DFS 阻塞流实践中远快于此,竞赛首选
最小费用最大流SPFA/Bellman-Ford 找最小代价增广路边上再加「单位费用」
class MaxFlow:
    """Edmonds-Karp 最大流:每轮 BFS 找最短增广路。O(V * E^2)"""

    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]    # 每个点存出边编号
        self.to = []                           # 第 e 条边指向的点
        self.cap = []                          # 第 e 条边的剩余容量

    def add_edge(self, u, v, c):
        """加一条 u->v 容量 c 的边,同时建立容量 0 的反向边(成对出现)"""
        self.graph[u].append(len(self.to))
        self.to.append(v)
        self.cap.append(c)
        self.graph[v].append(len(self.to))
        self.to.append(u)
        self.cap.append(0)                     # 反向边初始容量为 0

    def _bfs(self, s, t, prev_edge):
        """BFS 找一条增广路,prev_edge[v] = 到达 v 用的边编号"""
        prev_edge[:] = [-1] * self.n
        prev_edge[s] = -2                      # 起点哨兵
        q = deque([s])
        while q:
            u = q.popleft()
            for eid in self.graph[u]:
                v = self.to[eid]
                if self.cap[eid] > 0 and prev_edge[v] == -1:
                    prev_edge[v] = eid
                    if v == t:
                        return True            # 找到汇点即可停止
                    q.append(v)
        return False

    def max_flow(self, s, t):
        flow = 0
        prev_edge = [-1] * self.n
        while self._bfs(s, t, prev_edge):
            # 第一步:沿增广路求瓶颈容量
            bottleneck = float("inf")
            v = t
            while v != s:
                eid = prev_edge[v]
                bottleneck = min(bottleneck, self.cap[eid])
                v = self.to[eid ^ 1]           # 反向边的终点就是原来的 u
            # 第二步:更新残量网络(正向减、反向加)
            v = t
            while v != s:
                eid = prev_edge[v]
                self.cap[eid] -= bottleneck
                self.cap[eid ^ 1] += bottleneck
                v = self.to[eid ^ 1]
            flow += bottleneck
        return flow

    def min_cut(self, s):
        """返回最小割的 S 侧点集:残量网络中从 s 可达的点"""
        seen = [False] * self.n
        seen[s] = True
        q = deque([s])
        while q:
            u = q.popleft()
            for eid in self.graph[u]:
                v = self.to[eid]
                if self.cap[eid] > 0 and not seen[v]:
                    seen[v] = True
                    q.append(v)
        return seen

最大流的常见建模(都可以归约到最大流/最小割):

原问题建模
二分图最大匹配源点 → 左部(容量 1),左部 → 右部(容量 1),右部 → 汇点(容量 1)
项目选择 / 最大权闭合子图源点连正权点,负权点连汇点,答案 = 正权和 − 最小割
图像分割 / 二值标记源汇分别代表两类,边权为「分错类的代价」
多重匹配 / 容量约束的分配边的容量设为可服务的次数

十、二分图匹配:匈牙利算法

是什么:在二分图中选出尽可能多的边,使任意两条边不共享端点,这就是最大匹配(Maximum Matching)。

核心思想——增广路(Augmenting Path):从某个未匹配的左部点出发,交替走「非匹配边 → 匹配边 → 非匹配边 → …」,若终点是一个未匹配的右部点,则把这条路径上的匹配状态翻转,匹配数就 。若找不到这样的路径,则该点无法再增加匹配。

增广路定理

匹配 是最大匹配 当且仅当 不存在关于 的增广路(Berge 定理)。匈牙利算法的每一轮就是在为新的左部点寻找增广路——这本质上是一次 DFS,与最大流的「找增广路」是同一件事(二分图匹配是最大流的特例)。

def hungarian(n_left, n_right, adj):
    """匈牙利算法求二分图最大匹配。adj[u] = 左部点 u 能连的右部点列表。
    返回 (最大匹配数, match_left, match_right)。O(V * E)"""
    match_left = [-1] * n_left
    match_right = [-1] * n_right

    def try_kuhn(u, visited):
        for v in adj[u]:
            if visited[v]:
                continue                   # 本轮已经尝试过 v,跳过避免死循环
            visited[v] = True
            # v 还没被匹配,或者 v 的原配能找到别的右部点 → 让位
            if match_right[v] == -1 or try_kuhn(match_right[v], visited):
                match_left[u] = v
                match_right[v] = u
                return True
        return False

    result = 0
    for u in range(n_left):
        if try_kuhn(u, [False] * n_right):  # 每轮为 u 找一条增广路
            result += 1
    return result, match_left, match_right

分步推演:左部 、右部 ,边为 、、。

轮次处理visited 与递归过程结果
1试 :未匹配 → 直接配0-a
2试 :已配给 0 → 递归让 0 换0 改试 (未匹配,成功)

最终匹配数 2:0-b、1-a。可以看到「让位」是匈牙利算法能找到最优匹配的关键——没有递归让位,第 2 轮就会失败。

匈牙利算法的复杂度与限制

复杂度是 ,其中每轮 try_kuhn 是一次 DFS,最坏 。注意:

- 递归深度可能达到 ,稠密二分图上要留意栈深度;

- 它求的是最大基数匹配(边数最多);若边带权求「最大权匹配」,需要 KM 算法或最小费用最大流;

- 二分图必须已确认是二分图(先用二染色验证),否则结果无意义。

十一、图算法选型速查表

问题首选算法时间复杂度前提 / 注意
无权图单源最短路BFS边权必须相等
边权只有 0/1 的最短路0-1 BFS(双端队列)比堆优化 Dijkstra 更快
非负权单源最短路Dijkstra(堆优化)边权不能为负
非负权稠密图单源最短路Dijkstra(朴素) 时优于堆优化
含负权单源最短路Bellman-Ford可判负环;SPFA 最坏同阶
含负权 + 必须判负环Bellman-Ford队列 + 入队计数亦可
全源最短路Floyd-Warshall可含负权,不能有负环;
启发式/带地图的寻路A\*取决于 必须可采纳(不高估)
动态连通性 / 判环 / 朋友圈并查集均摊 只能合并,不能删除
最小生成树(稀疏图)Kruskal需要并查集
最小生成树(稠密图)Prim(朴素)需要邻接矩阵
依赖顺序 / 判有向环拓扑排序(Kahn)只适用于 DAG
有向图强连通分量 / 缩点Tarjan注意 on_stack 判断
最大流Edmonds-Karp / Dinic / 需要建反向边
最小割转最大流后取残量可达集同最大流最小割最大流定理
二分图最大匹配匈牙利算法图必须确实是二分图
二分图最大权匹配KM 算法 / 最小费用最大流匈牙利算法不处理边权
状态空间上的最短路BFS / Dijkstra(隐式图)视状态数状态可能爆炸,需剪枝
访问所有点的最短路()状压 DP(Held-Karp)见 [[算法-动态规划与贪心]]

十二、注意事项与常见坑

什么时候不能用这些算法

- Dijkstra 不能用于负权边(哪怕只有一条负权边)。见 4.1 的反例。若必须用,请先用 Johnson 重标定把边权变非负。

- Dijkstra / Bellman-Ford 都不能处理负环:负环存在时「最短路」无定义(可以无限绕圈)。Bellman-Ford 的作用是检测它,而不是求解。

- BFS 只适用于无权图(或边权全相等)。边权不同必须换 Dijkstra。

- Floyd 不能用于 大的图: 时 ,直接超时。

- 并查集只能合并不能拆分:涉及「删边」的连通性问题(如动态图连通性、离线删边)需要倒序处理操作把删边变成加边,或使用 Link-Cut Tree 等高级结构。

- 拓扑排序只适用于 DAG:有环的图没有拓扑序,但「检测出有环」本身就是有用信息(例如循环依赖报错)。

- **A\* 的启发式绝不能高估**:否则返回的可能不是最短路径。

- 二分图匹配要求图确实是二分图:奇环存在时匈牙利算法的结果没有意义。

- 最大流的 Ford-Fulkerson(DFS 任意增广)在容量为无理数时可能不终止:实现时请用 BFS(Edmonds-Karp)或 Dinic。

其他高频坑

1. 无向图建边只加了一遍:邻接表里无向边必须 graph[u].append(v) 与 graph[v].append(u) 都写。

2. Floyd 的三重循环顺序写错:中转点 必须最外层(见 4.3)。

3. Dijkstra 忘记跳过过期堆条目:if d > dist[u]: continue 少了它结果仍然正确,但会把复杂度推高一个量级。

4. BFS 在出队时才标记访问:应在入队时标记,否则同一节点可能被多次入队,队列体积爆炸。

5. 递归 DFS 在链状图上爆栈: 的链会超过 Python 默认递归上限,改用显式栈。

6. Tarjan 漏掉 on_stack 判断:会把不同的 SCC 合并(见第八节)。

7. 网络流忘记建反向边或反向边容量写错:正确做法是正向容量 、反向容量 ,成对存储并用 eid ^ 1 互相索引。

8. Bellman-Ford 判负环时忘了检查可达性:dist[u] != INF 这个前置条件不能省,否则不可达点会误报负环。

9. 网格 BFS 越界:四个方向扩展前一定要判断 0 <= nr < m and 0 <= nc < n。

十三、练习题

练习 1(Dijkstra,给出完整解题过程)

LeetCode 743 网络延迟时间:有 个网络节点,times[i] = (u, v, w) 表示 到 的传信时间为 。从节点 发出一条信号,求所有节点都收到信号的最短时间;若有节点收不到返回 。

第一步:建模。节点是点,传输关系是有向边,传递时间是边权。题目求「从 到所有点的最短路中的最大值」——因为信号同时发出,最后一个收到的时间就是答案。

第二步:选算法。边权为正(传输时间),、边数 ,是稀疏图 → 堆优化 Dijkstra,。( 这么小,Floyd 也完全可行,可以作为对照实现。)

第三步:实现。

def network_delay_time(times, n, k):
    """LeetCode 743 网络延迟时间:单源最短路的最大值。O((V+E) log V)"""
    graph = [[] for _ in range(n + 1)]     # 节点编号 1..n
    for u, v, w in times:
        graph[u].append((v, w))
    INF = float("inf")
    dist = [INF] * (n + 1)
    dist[k] = 0
    pq = [(0, k)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                       # 过期条目
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    ans = max(dist[1:])                    # 取所有点的最短路最大值
    return -1 if ans == INF else ans

第四步:分步推演。times = [[2,1,1],[2,3,1],[3,4,1]],n = 4,k = 2。

轮次出堆dist[1]dist[2]dist[3]dist[4]说明
初始—∞0∞∞起点 2 入堆
1101∞松弛 、
2101∞节点 1 无出边
31012松弛
41012无出边

答案 。

第五步:边界检查。存在不可达节点 → max 会取到 INF,返回 。k 超出范围时 dist[k] 会 IndexError,实际题目保证 。注意 dist[1:] 切片是为了跳过下标 0(不存在的节点)。

练习 2(拓扑排序)

LeetCode 207 课程表:共 numCourses 门课,prerequisites[i] = [a, b] 表示修 a 之前必须先修 b。判断能否修完所有课程。

提示:课程是点,先修关系 是有向边。能修完 ⟺ 图中无环。用 Kahn 算法跑拓扑排序,若输出的点数等于 numCourses 则返回 True;也可用三色标记 DFS 判环。

练习 3(稠密图上的 Prim)

LeetCode 1584 连接所有点的最小费用:给定 个点的坐标,连接点 与 的费用是曼哈顿距离 ,求把所有点连起来的最小费用。

提示:这是完全图(), 意味着 接近 。用朴素 Prim ,每次线性扫描找「距离已选集合最近的点」,不要预先构造所有边(否则光是建图就要 空间且常数很大)。

练习 4(Bellman-Ford 的变体)

LeetCode 787 K 站中转内最便宜的航班:求从 src 到 dst 最多经过 k 站中转的最低票价,不可达返回 。

提示:Bellman-Ford 的「松弛 轮」正好对应「最多经过 条边」——把轮数改成 轮( 站中转 = 条边)即可。关键细节:每轮必须用上一轮的 dist 快照来更新,否则同一轮内会串联松弛出「超过 条边」的路径,答案偏小。

练习 5(并查集 / 环检测)

LeetCode 684 冗余连接:在一棵树上加一条边形成的有向无环图中,找出那条可以删掉的边,使剩余部分是一棵树(若有多个答案,返回输入中最后出现的那条)。

提示:依次遍历边,用并查集合并;第一次 union 返回 False 的边就是答案(见第五节代码)。注意题目要求「最后出现的那条」,因此按输入顺序遍历、返回第一个失败者即可,因为形成环的那条边在输入顺序上就是使环闭合的那条。

十四、常见问题 FAQ

Dijkstra、Bellman-Ford、Floyd 三个最短路算法该怎么记?

按两个维度记:单源还是全源、能否处理负权。

- Dijkstra:单源、非负权、,贪心;

- Bellman-Ford:单源、可负权、,暴力松弛 + 判负环;

- Floyd:全源、可负权、,区间 DP。

一句话选择法:非负权就用 Dijkstra;有负权且单源用 Bellman-Ford; 很小且要所有点对用 Floyd。 A\* 是 Dijkstra 加上启发式,只在「有明确目标点 + 有好的启发函数」时才更快。

为什么 BFS 求最短路不需要「松弛」操作?

因为无权图(或边权全相等)中,路径长度就等于边数。BFS 按层扩展天然保证「第一次到达某点时用的边数最少」,不存在「先到但更贵」的可能,所以不需要像 Dijkstra 那样回头修正。一旦边权不等,「层」的概念就失效了——先到的路径可能更贵,于是必须用优先队列按代价排序,这就是 Dijkstra。

并查集真的可以当作 吗?

在「路径压缩 + 按秩合并」同时使用时, 次操作的总代价是 ,均摊到每次是 ,而 对一切实际可能的 成立,因此工程上完全可以当 。但要记住这是均摊界:单次 find 的最坏代价仍是 ,在需要严格最坏时间保证的实时系统里要留意。

最大流为什么要建反向边?不建会怎样?

反向边让算法能「反悔」。举个最小例子:(容量 1)、(容量 1)、(容量 1)、(容量 1)、(容量 1)。若第一次错误地沿 推了 1 单位流,则 这条边就废了,最大流只能到 1;但有反向边时,算法可以沿 (其中 是 的反向边)推流,把之前的决策撤销,最终得到正确的最大流 2。反向边本质上是在残量网络上「退还」流量。

相关笔记

  • 数据结构-图:图的存储结构(邻接矩阵 / 邻接表 / 边列表)与遍历基础
  • 算法-动态规划与贪心:Dijkstra 与 Bellman-Ford 是「最短路上的 DP」,Floyd 是区间 DP 的近亲,状压 DP 解决 TSP
  • 算法-查找与分治:二分答案常与最短路/生成树结合(如「最小化最大边权」)
  • 算法-复杂度分析:、、 的推导与均摊分析
  • 数据结构-树与堆:优先队列是 Dijkstra / Prim / A\* / 哈夫曼的共同基础设施
  • 数据结构-哈希表:哈希表实现「隐式图」的状态去重(BFS 访问标记)
  • 00-索引 / 学习路线图:回到总导航安排学习顺序

参考来源