图算法

第 11 章 · 数据结构与算法

怎么走最短？怎么连最省？ 上一章学会了图的遍历，但现实中我们常要「从 A 到 B 的最短路径」或「用最少代价把一堆点连成连通图」——前者是最短路，后者是最小生成树。最短路：无权图用 BFS；边权非负用Dijkstra（贪心 + 优先队列）；有负权边可用 Bellman-Ford；全源最短路可用 Floyd。最小生成树（MST）：在无向带权图中选 n-1 条边使图连通且总权最小，Prim 与 Kruskal 是两种经典算法。本章讲这些算法的思想、图示与 Python 实现（含类型标注与注释），并配至少三道例题。

一、最短路问题概述

单源最短路：从起点 s 到其余各点的最短距离（及路径）。全源最短路：任意两点之间的最短距离。

边权均为 1（无权）：BFS 即可，上一章已讲。
边权非负：Dijkstra，用优先队列每次取「当前距离最小」的未确定点松弛其邻居，O((V+E) log V) 或 O(V²+E)。
存在负权边：Dijkstra 不适用；Bellman-Ford 对边松弛 V-1 轮，可检测负环；或用 SPFA。
全源：Floyd-Warshall，三重循环枚举中转点，O(V³)。

带权无向图：0 到 3 权 1，0 到 1 权 2，0 到 2 权 5，3 到 1 权 3、到 2 权 1

二、Dijkstra 算法

Dijkstra 要求边权非负。思路：维护「已确定最短距离」的集合，每次从「未确定」中取当前距离最小的点 u，认为其距离已确定，并对 u 的所有出边做松弛：若 dist[u] + w(u,v) < dist[v]，则更新 dist[v]。用小根堆（优先队列）存 (距离, 顶点)，则取最小为 O(log n)，总时间 O((V+E) log V)。

松弛操作：通过 u 能否让 v 更近

import heapq
from typing import List, Tuple


def dijkstra(
    n: int,
    adj: List[List[Tuple[int, int]]],
    start: int,
) -> List[int]:
    """
    单源最短路（边权非负）。adj[u] 为 (v, w) 列表，表示 u->v 权为 w。
    返回长度为 n 的列表，dist[i] 为 start 到 i 的最短距离，不可达为 inf。
    """
    INF = 10**18
    dist: List[int] = [INF] * n
    dist[start] = 0
    # 小根堆：(距离, 顶点)，同一顶点可能多次入队，用 vis 保证只扩展一次
    heap: List[Tuple[int, int]] = [(0, start)]
    visited: List[bool] = [False] * n
    while heap:
        d, u = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

三、最小生成树（MST）

最小生成树（Minimum Spanning Tree）：在无向带权连通图中，选出一棵包含所有顶点的树，使边权之和最小。若图不连通则求的是「最小生成森林」。

Prim：从任一点开始，每次选「当前已选点集」到「未选点」的权值最小的边，把该边与未选端点加入集合，直到包含 n 个顶点。用优先队列维护「未选点」到已选集的最小边权，类似 Dijkstra。时间 O((V+E) log V)。

Kruskal：将所有边按权值从小到大排序，依次尝试加入，若两端当前不在同一连通分量则加入（用并查集维护），直到选满 n-1 条边。时间 O(E log E)。

Prim：从 A 开始，依次选权 1、2、1、3 的边；Kruskal：边按权排序后依次选不成环的

四、Prim 与 Kruskal 的 Python 实现

import heapq
from typing import List, Tuple


def prim_mst(n: int, edges: List[Tuple[int, int, int]]) -> int:
    """
    无向图 MST 权值和。edges 为 (u, v, w) 列表，顶点 0..n-1。
    从 0 开始，用优先队列维护 (边权, 邻接点)，每次取最小边扩展。
    """
    adj: List[List[Tuple[int, int]]] = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
        adj[v].append((u, w))
    total = 0
    visited: List[bool] = [False] * n
    heap: List[Tuple[int, int]] = [(0, 0)]  # (权, 点)
    while heap:
        w, u = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True
        total += w
        for v, w_uv in adj[u]:
            if not visited[v]:
                heapq.heappush(heap, (w_uv, v))
    return total


class UnionFind:
    """并查集：支持 find 与 union，用于 Kruskal 判环。"""

    def __init__(self, n: int) -> None:
        self.parent: List[int] = list(range(n))

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        self.parent[rx] = ry
        return True


def kruskal_mst(n: int, edges: List[Tuple[int, int, int]]) -> int:
    """
    Kruskal：边按权排序，用并查集维护连通性，选 n-1 条不成环的边。
    """
    edges_sorted = sorted(edges, key=lambda e: e[2])
    uf = UnionFind(n)
    total = 0
    count = 0
    for u, v, w in edges_sorted:
        if uf.union(u, v):
            total += w
            count += 1
            if count == n - 1:
                break
    return total

五、Bellman-Ford 与 Floyd 简述

Bellman-Ford：对每条边松弛，重复 V-1 轮；若第 V 轮仍能松弛则存在负环。单源、允许负权，O(VE)。Floyd-Warshall：用 dp[k][i][j] 表示「只经过 0..k 为中转时 i 到 j 的最短路」，可压成二维，三重循环 O(V³)，求全源最短路。

小贴士： 最短路与 MST 都不会重复经过同一条边（在简单路径/树的意义下）；负环时最短路无界，需先判环或限制步数。

六、小结

最短路：无权 BFS；非负权 Dijkstra（优先队列）；负权 Bellman-Ford；全源 Floyd。MST：Prim 类似「从一点扩散」、Kruskal 为「边排序 + 并查集」。下一章讲排序：比较排序与稳定性。

七、例题

以下例题使用 Python 3 类型标注与注释。

例题 1：网络延迟时间（Dijkstra）

题目描述：有 n 个节点，从 1 到 n 编号。给定有向边 times[i]=[u,v,w] 表示 u→v 耗时 w。从节点 k 发出信号，求所有节点收到信号的最短时间；若存在无法收到的节点则返回 -1。

输入：n、k、times。
输出：最远的那个节点的接收时间；不可达则 -1。

import heapq
from typing import List


def network_delay_time(times: List[List[int]], n: int, k: int) -> int:
    """
    建图后从 k 跑 Dijkstra，取 dist 最大值；若有 inf 则返回 -1。
    注意题目节点从 1 开始，建邻接表时用 0..n-1 或 1..n 均可，统一即可。
    """
    adj: List[List[tuple]] = [[] for _ in range(n + 1)]
    for u, v, w in times:
        adj[u].append((v, w))
    INF = 10**18
    dist = [INF] * (n + 1)
    dist[k] = 0
    heap: List[tuple] = [(0, k)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    ans = max(dist[1 : n + 1])
    return -1 if ans == INF else ans

讲解：单源最短路，边权为正，Dijkstra。建邻接表后从 k 跑一遍，答案即 max(dist[1..n])；若有节点仍为 INF 则返回 -1。时间 O((V+E) log V)。

例题 2：连接所有点的最小费用（MST）

题目描述：平面上有 n 个点，用 points[i]=[xi,yi] 表示。连接两点的费用为曼哈顿距离 |xi-xj|+|yi-yj|。求连接所有点的最小总费用（即 MST 权值和）。

思路：任意两点之间都可连边，边权为曼哈顿距离。可先生成所有边再跑 Kruskal 或 Prim。边数 O(n²)，Kruskal O(E log E)=O(n² log n)。

from typing import List


def min_cost_connect_points(points: List[List[int]]) -> int:
    n = len(points)
    if n <= 1:
        return 0

    def manhattan(i: int, j: int) -> int:
        return abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])

    edges: List[tuple] = []
    for i in range(n):
        for j in range(i + 1, n):
            edges.append((i, j, manhattan(i, j)))
    edges.sort(key=lambda e: e[2])

    parent = list(range(n))

    def find(x: int) -> int:
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    total = 0
    count = 0
    for u, v, w in edges:
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            total += w
            count += 1
            if count == n - 1:
                break
    return total

讲解：完全图上的 MST。枚举所有 (i,j) 建边并排序，Kruskal 选 n-1 条不成环的边。并查集用路径压缩即可。时间 O(n² log n)，空间 O(n²)。

例题 3：路径权重和最大的路径（DAG 最长路）

题目描述：给定有向无环图（DAG），每条边有权值。求从某起点到某终点的路径上边权之和的最大值。

思路：DAG 可拓扑排序后按拓扑序 DP：dp[v] = 到达 v 的最大权值和，dp[v] = max(dp[u] + w(u,v))。或把边权取负后跑最短路。

from typing import List


def max_path_weight(n: int, edges: List[List[int]], start: int, end: int) -> int:
    """
    edges: [u, v, w] 表示 u->v 权 w。DAG 最长路：拓扑排序后 DP。
    """
    adj: List[List[tuple]] = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v, w in edges:
        adj[u].append((v, w))
        indeg[v] += 1
    from collections import deque
    topo: List[int] = []
    q: deque = deque(i for i in range(n) if indeg[i] == 0)
    while q:
        u = q.popleft()
        topo.append(u)
        for v, _ in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    INF = -10**18
    dp: List[int] = [INF] * n
    dp[start] = 0
    for u in topo:
        if dp[u] == INF:
            continue
        for v, w in adj[u]:
            if dp[u] + w > dp[v]:
                dp[v] = dp[u] + w
    return dp[end] if dp[end] != INF else -1

讲解：拓扑排序得到线性顺序后，按该顺序对每条边做松弛（这里取 max 而非 min），即 DAG 上的最长路。时间 O(V+E)。

例题 4：最多经过 K 站的最便宜机票（Bellman-Ford 思想）

题目描述：n 个城市，航班列表 flights[i]=[from,to,price]。求从 src 到 dst 最多经过 k 站（即最多 k+1 条边）的最便宜价格；无法到达返回 -1。

思路：限制「最多 k+1 条边」的最短路。对 dist 做 k+1 轮松弛：每轮用当前 dist 更新「多走一条边」后的结果，类似 Bellman-Ford 的轮数限制。

from typing import List


def find_cheapest_price(n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
    """
    最多 k+1 条边：做 k+1 轮松弛。每轮用上一轮的 dist 更新，避免同一轮内多步扩散。
    """
    INF = 10**18
    dist = [INF] * n
    dist[src] = 0
    for _ in range(k + 1):
        prev = dist[:]
        for u, v, w in flights:
            if prev[u] != INF and prev[u] + w < dist[v]:
                dist[v] = prev[u] + w
    return -1 if dist[dst] == INF else dist[dst]

讲解：用 prev 保存上一轮距离，本轮只从 prev 松弛一条边，这样第 i 轮得到的是「最多 i 条边」的最短路。时间 O((k+1)·E)，空间 O(n)。