算法模板 - 图论

本文整理图论相关的算法模板，按难度递增排列：拓扑排序 → DFS 序 → 最短路系列 → 最小生成树 → LCA → 二分图 → 高级图论。

1. 拓扑排序

适用场景：有向无环图（DAG）的线性排序，如任务调度、课程依赖。

核心思想：Kahn 算法——不断取入度为 0 的节点加入结果，同时更新邻居的入度。如果最终结果长度 < 节点数，说明有环。

from collections import deque

def topological_sort(adj: list) -> list:
    """
    拓扑排序（Kahn 算法）

    参数:
        adj: 邻接表，adj[u] = [v1, v2, ...] 表示 u → v
    返回:
        拓扑序列，如果存在环则返回 []
    """
    n = len(adj)
    in_degree = [0] * n
    for u in range(n):
        for v in adj[u]:
            in_degree[v] += 1

    q = deque([u for u in range(n) if in_degree[u] == 0])
    topo = []

    while q:
        u = q.popleft()
        topo.append(u)
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                q.append(v)

    return topo if len(topo) == n else []  # 长度不等于 n 说明有环

# 示例：课程依赖
adj = [[1, 2], [3], [3], []]  # 0→1,3  0→2,3
print(topological_sort(adj))  # [0, 1, 2, 3] 或 [0, 2, 1, 3]

为什么能检测环？ 如果有环，环上的节点入度永远不为 0，不会被加入队列，最终 topo 长度 < n。

---

2. DFS 序（判断祖先关系）

适用场景：O(1) 判断 u 是否是 v 的祖先。

核心思想：DFS 记录每个节点的进入时间 tin 和离开时间 tout。u 是 v 的祖先当且仅当 tin[u] ≤ tin[v] 且 tout[v] ≤ tout[u]。

def build_dfs_order(adj, n):
    """构建 DFS 序，adj[u] = [v1, v2, ...]"""
    tin = [0] * n
    tout = [0] * n
    timer = 0

    def dfs(u, fa):
        nonlocal timer
        timer += 1
        tin[u] = timer
        for v in adj[u]:
            if v != fa:
                dfs(v, u)
        timer += 1
        tout[u] = timer

    dfs(0, -1)
    return tin, tout

def is_ancestor(u, v, tin, tout):
    """判断 u 是否是 v 的祖先"""
    return tin[u] <= tin[v] and tout[v] <= tout[u]

为什么这样判断？ DFS 的进入/离开时间形成了一个"括号序列"。如果 u 是 v 的祖先，那么 v 的整个 DFS 区间 [tin[v], tout[v]] 被包含在 u 的区间 [tin[u], tout[u]] 内。

---

3. Dijkstra（邻接表 + 优先队列）

适用场景：非负权图的单源最短路。最常用的最短路算法。

核心思想：贪心。每次从"未确定最短路的节点"中选距离最小的，用它去松弛邻居。为什么贪心正确？因为非负权保证了"当前最小的 dis[u] 不会被后续更新变小"。

from heapq import heappush, heappop

def dijkstra(adj: list, source: int, n: int) -> list:
    """
    Dijkstra 最短路算法（邻接表 + 堆优化）

    参数:
        adj: 邻接表，adj[u] = [(v, w), ...]
        source: 源点
        n: 节点数（0-indexed）
    返回:
        dis: dis[i] 表示 source 到 i 的最短距离
    """
    dis = [float('inf')] * n
    dis[source] = 0
    heap = [(0, source)]

    while heap:
        d, u = heappop(heap)
        if d > dis[u]:
            continue  # 已经找到更短的路，跳过（懒删除）
        for v, w in adj[u]:
            if dis[u] + w < dis[v]:
                dis[v] = dis[u] + w
                heappush(heap, (dis[v], v))
    return dis

# 示例
adj = [
    [(1, 1), (2, 3), (3, 1)],
    [(0, 1), (2, 1)],
    [(0, 3), (1, 1), (3, 1)],
    [(0, 1), (2, 1)]
]
print(dijkstra(adj, 0, 4))  # [0, 1, 2, 1]

为什么用堆？ 每次暴力找最小值是 O(n)，总共 O(n²)。用优先队列优化到 O((n+m) log n)。if d > dis[u] 是"懒删除"——堆中可能有同一个节点的多条记录，只取最新的。

---

4. Dijkstra（邻接矩阵版）

当图是稠密图（边数接近 n²）时，邻接矩阵 + O(n²) 的朴素 Dijkstra 比堆优化版更快（常数更小）。

def dijkstra_matrix(weight, source):
    """
    Dijkstra 邻接矩阵版，O(n²)

    参数:
        weight: 邻接矩阵，weight[i][j] 表示 i→j 的边权（无边为 inf）
        source: 源点
    """
    n = len(weight)
    visited = [False] * n
    dis = [float('inf')] * n
    dis[source] = 0

    for _ in range(n):
        u = -1
        for i in range(n):
            if not visited[i] and (u == -1 or dis[i] < dis[u]):
                u = i
        if dis[u] == float('inf'):
            break
        visited[u] = True
        for v in range(n):
            if not visited[v] and dis[u] + weight[u][v] < dis[v]:
                dis[v] = dis[u] + weight[u][v]

    return dis

# 示例
w = [[0, 1, 3, 1], [1, 0, 1, 999], [3, 1, 0, 1], [1, 999, 1, 0]]
print(dijkstra_matrix(w, 0))  # [0, 1, 2, 1]

邻接表 vs 邻接矩阵：

特性	邻接表 + 堆	邻接矩阵
时间	O((n+m) log n)	O(n²)
空间	O(n+m)	O(n²)
适用	稀疏图 (m << n²)	稠密图 (m ≈ n²)

---

5. Bellman-Ford

适用场景：含负权边的图，可以检测负环。

核心思想：对所有边做 n-1 轮松弛。如果第 n 轮还能松弛，说明存在负环。为什么是 n-1 轮？因为不含负环的图中，最短路最多经过 n-1 条边。

def bellman_ford(edges: list, n: int, source: int) -> tuple:
    """
    Bellman-Ford 最短路算法

    参数:
        edges: 边列表 [(u, v, w), ...]
        n: 节点数
        source: 源点
    返回:
        (dis, has_negative_cycle)
    """
    dis = [float('inf')] * n
    dis[source] = 0

    for i in range(n):
        updated = False
        for u, v, w in edges:
            if dis[u] == float('inf'):
                continue
            if dis[v] > dis[u] + w:
                dis[v] = dis[u] + w
                updated = True
        if not updated:
            break  # 没有松弛发生，提前退出
    else:
        return dis, True  # n 轮后仍在更新，有负环

    return dis, False

---

6. SPFA

适用场景：含负权边的图（Bellman-Ford 的队列优化），实际复杂度通常远优于 O(nm)。

核心思想：只有被松弛的节点才需要重新处理，用队列维护待处理的节点。

from collections import deque

def spfa(adj: list, n: int, source: int) -> tuple:
    """
    SPFA 最短路算法

    参数:
        adj: 邻接表，adj[u] = [(v, w), ...]
        n: 节点数
        source: 源点
    返回:
        (dis, has_negative_cycle)
    """
    dis = [float('inf')] * n
    in_queue = [False] * n
    cnt = [0] * n  # 入队次数，用于检测负环

    dis[source] = 0
    q = deque([source])
    in_queue[source] = True

    while q:
        u = q.popleft()
        in_queue[u] = False
        for v, w in adj[u]:
            if dis[v] > dis[u] + w:
                dis[v] = dis[u] + w
                cnt[v] = cnt[u] + 1
                if cnt[v] >= n:
                    return dis, True  # 负环
                if not in_queue[v]:
                    q.append(v)
                    in_queue[v] = True

    return dis, False

为什么 SPFA 比 Bellman-Ford 快？ Bellman-Ford 每轮处理所有边，很多松弛是无效的。SPFA 只处理"刚被松弛的节点"的邻居，实际运行时每个节点平均只入队几次。

三种最短路算法对比：

算法	时间复杂度	负权边	负环检测	适用场景
Dijkstra	O((n+m) log n)	❌	❌	非负权图（最常用）
Bellman-Ford	O(nm)	✅	✅	需要检测负环
SPFA	期望 O(m)，最坏 O(nm)	✅	✅	含负权边的稀疏图

---

7. 最小生成树 — Kruskal 算法

适用场景：稀疏图。基于边排序 + 并查集。

核心思想：把所有边按权重排序，从小到大依次考虑。如果这条边连接的两个端点还不在同一个连通分量中（用并查集判断），就加入 MST。

def kruskal_mst(adj: list, n: int) -> tuple:
    """
    Kruskal 最小生成树算法

    参数:
        adj: 邻接表，adj[u] = [(v, w), ...]
        n: 节点数
    返回:
        (total_weight, mst_edges) 或 (-1, []) 如果图不连通
    """
    edges = []
    for u in range(n):
        for v, w in adj[u]:
            if u < v:
                edges.append((w, u, v))
    edges.sort()

    parent = list(range(n))
    rank = [0] * n

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

    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry:
            return False
        if rank[rx] < rank[ry]:
            rx, ry = ry, rx
        parent[ry] = rx
        if rank[rx] == rank[ry]:
            rank[rx] += 1
        return True

    total_weight = 0
    mst_edges = []
    for w, u, v in edges:
        if union(u, v):
            mst_edges.append((u, v, w))
            total_weight += w
            if len(mst_edges) == n - 1:
                break

    if len(mst_edges) != n - 1:
        return -1, []
    return total_weight, mst_edges

# 示例
adj = [[(1, 2), (3, 6)], [(0, 2), (2, 3), (3, 8), (4, 5)],
       [(1, 3), (4, 7)], [(0, 6), (1, 8)], [(1, 5), (2, 7)]]
weight, edges = kruskal_mst(adj, 5)
print(f"MST 权重: {weight}")  # 16

为什么 Kruskal 正确？ 这是"切分定理"的直接应用——对于任意切分，横跨切分的最小边一定在 MST 中。按权重排序保证每次选的都是当前最小的横跨边。

---

8. 最小生成树 — Prim 算法

适用场景：稠密图。基于顶点扩展 + 优先队列。

核心思想：从任意顶点开始，每次选连接"已选集合"和"未选集合"的最短边。

import heapq

def prim_mst(adj: list, n: int) -> tuple:
    if n == 0:
        return 0, []
    in_mst = [False] * n
    min_weight = [float('inf')] * n
    parent = [-1] * n
    min_weight[0] = 0
    heap = [(0, 0)]

    total_weight = 0
    mst_edges = []
    count = 0

    while heap:
        w, u = heapq.heappop(heap)
        if in_mst[u]:
            continue
        in_mst[u] = True
        total_weight += w
        count += 1
        if parent[u] != -1:
            mst_edges.append((parent[u], u, w))
        if count == n:
            break
        for v, weight in adj[u]:
            if not in_mst[v] and weight < min_weight[v]:
                min_weight[v] = weight
                parent[v] = u
                heapq.heappush(heap, (weight, v))

    if count != n:
        return -1, []
    return total_weight, mst_edges

Kruskal vs Prim：

特性	Kruskal	Prim
思路	按边排序，逐边加入	按顶点扩展，逐点加入
数据结构	并查集	优先队列
时间	O(m log m)	O((n+m) log n)
适用	稀疏图 (m << n²)	稠密图 (m ≈ n²)

---

9. 最近公共祖先（LCA — 二进制提升）

适用场景：树上两点的最近公共祖先查询。

核心思想：预处理每个节点的 2^k 级祖先，查询时先将两个节点跳到同一深度，再同时往上跳。

from typing import List

class LcaBinaryLifting:
    def __init__(self, edges: List[List[int]]):
        """edges: [(x, y, w), ...]，节点编号从 0 开始"""
        n = len(edges) + 1
        m = n.bit_length()
        g = [[] for _ in range(n)]
        for x, y, w in edges:
            g[x].append((y, w))
            g[y].append((x, w))

        depth = [0] * n
        dis = [0] * n
        pa = [[-1] * m for _ in range(n)]

        def dfs(x: int, fa: int) -> None:
            pa[x][0] = fa
            for y, w in g[x]:
                if y != fa:
                    depth[y] = depth[x] + 1
                    dis[y] = dis[x] + w
                    dfs(y, x)

        dfs(0, -1)

        for i in range(m - 1):
            for x in range(n):
                if (p := pa[x][i]) != -1:
                    pa[x][i + 1] = pa[p][i]

        self.depth = depth
        self.dis = dis
        self.pa = pa

    def get_kth_ancestor(self, node: int, k: int) -> int:
        for i in range(k.bit_length()):
            if k >> i & 1:
                node = self.pa[node][i]
        return node

    def get_lca(self, x: int, y: int) -> int:
        if self.depth[x] > self.depth[y]:
            x, y = y, x
        y = self.get_kth_ancestor(y, self.depth[y] - self.depth[x])
        if y == x:
            return x
        for i in range(len(self.pa[x]) - 1, -1, -1):
            if self.pa[x][i] != self.pa[y][i]:
                x, y = self.pa[x][i], self.pa[y][i]
        return self.pa[x][0]

    def get_dis(self, x: int, y: int) -> int:
        return self.dis[x] + self.dis[y] - 2 * self.dis[self.get_lca(x, y)]

二进制提升的本质：把"跳 k 步"拆成二进制——比如跳 13 步 = 跳 8 步 + 跳 4 步 + 跳 1 步，每一步都是 O(1) 的查表。

---

10. 匈牙利算法（二分图最大匹配）

适用场景：求解二分图的最大匹配、最小路径覆盖等问题。

核心思想：对每个左部节点，尝试找增广路径。如果右部节点未匹配，直接匹配；如果已匹配，递归让它的"前任"去找新的。

def hungarian(graph: list, n_left: int, n_right: int) -> int:
    """
    匈牙利算法求二分图最大匹配

    参数:
        graph: 左部节点的邻接表，graph[i] = [j1, j2, ...]
        n_left, n_right: 左右部节点数
    """
    match = [-1] * n_right  # match[j] = i 表示右部 j 匹配了左部 i

    def find(x: int, visited: list) -> bool:
        for y in graph[x]:
            if visited[y]:
                continue
            visited[y] = True
            if match[y] == -1 or find(match[y], visited):
                match[y] = x
                return True
        return False

    result = 0
    for i in range(n_left):
        visited = [False] * n_right
        if find(i, visited):
            result += 1
    return result

最小路径覆盖

公式：最小路径数 = 顶点数 - 最大匹配数

def min_path_cover(n: int, edges: list) -> int:
    """有向图最小路径覆盖"""
    reach = [[False] * (n + 1) for _ in range(n + 1)]
    for a, b in edges:
        reach[a][b] = True
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                reach[i][j] |= reach[i][k] and reach[k][j]

    graph = [[] for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i != j and reach[i][j]:
                graph[i].append(j)

    match = [0] * (n + 1)
    def find(x, visited):
        for y in graph[x]:
            if not visited[y]:
                visited[y] = True
                if match[y] == 0 or find(match[y], visited):
                    match[y] = x
                    return True
        return False

    result = 0
    for i in range(1, n + 1):
        visited = [False] * (n + 1)
        if find(i, visited):
            result += 1
    return n - result

---

11. Floyd 最小环

适用场景：求图中边数 ≥ 3 的最小环。

核心思想：在 Floyd 最外层循环的第 k 轮，在更新最短路之前，用 dis[i][j] + val[i][k] + val[k][j] 更新答案——这保证 i→j 的最短路不经过 k，而 i→k 和 k→j 是直接边。

from cmath import inf

def floyd_min_cycle(val, n):
    """
    val: 邻接矩阵，val[i][j] 表示 i→j 的边权（无边为 inf）
    n: 节点数（1-indexed）
    """
    dis = [row[:] for row in val]
    ans = inf

    for k in range(1, n + 1):
        # 先更新最小环（i→j 不经过 k）
        for i in range(1, k):
            for j in range(1, i):
                ans = min(ans, dis[i][j] + val[i][k] + val[k][j])
        # 再正常 Floyd 更新最短路
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

    return ans

---

12. 2-SAT

适用场景：有 n 个布尔变量，给定若干形如 "(x_i = a) OR (x_j = b)" 的约束，判断是否存在满足所有约束的赋值。

核心思想：将每个变量拆成两个节点（True/False），构建蕴含图，用 Tarjan 求 SCC。如果 x 和 ¬x 在同一个 SCC 中，无解。

class TwoSAT:
    def __init__(self, n: int):
        self.n = n
        self.N = 2 * n
        self.g = [[] for _ in range(self.N)]

    def lit(self, var: int, is_true: bool = True) -> int:
        return (2 * var) ^ (0 if is_true else 1)

    def neg(self, x: int) -> int:
        return x ^ 1

    def add_or(self, a: int, b: int) -> None:
        """(a OR b) 等价于 (¬a → b) 且 (¬b → a)"""
        self.g[self.neg(a)].append(b)
        self.g[self.neg(b)].append(a)

    def add_clause(self, var1, val1, var2, val2) -> None:
        self.add_or(self.lit(var1, val1), self.lit(var2, val2))

    def add_true(self, var: int) -> None:
        x = self.lit(var, True)
        self.g[self.neg(x)].append(x)

    def solve(self) -> list | None:
        N = self.N
        dfn = [0] * N; low = [0] * N; instk = [False] * N
        stk = []; comp = [-1] * N; time = 1

        def tarjan(u):
            nonlocal time
            dfn[u] = low[u] = time; time += 1
            stk.append(u); instk[u] = True
            for v in self.g[u]:
                if dfn[v] == 0:
                    tarjan(v)
                    low[u] = min(low[u], low[v])
                elif instk[v]:
                    low[u] = min(low[u], dfn[v])
            if dfn[u] == low[u]:
                while True:
                    x = stk.pop(); instk[x] = False; comp[x] = u
                    if x == u: break

        for i in range(N):
            if dfn[i] == 0: tarjan(i)

        assignment = [False] * self.n
        for i in range(self.n):
            if comp[2*i] == comp[2*i ^ 1]:
                return None  # 无解
            assignment[i] = comp[2*i] > comp[2*i ^ 1]
        return assignment

---

13. 最大团（Bron-Kerbosch 算法）

适用场景：找无向图中的所有最大团（完全子图）。

核心思想：维护三个集合 R（当前团）、P（候选）、X（排除）。当 P 和 X 都为空时，R 是一个最大团。用 pivot 优化减少递归分支。

def bron_kerbosch(R, P, X, adj, cliques):
    if not P and not X:
        cliques.append(R.copy())
        return
    pivot = next(iter(P | X)) if (P | X) else None
    for v in P - adj.get(pivot, set()):
        bron_kerbosch(R | {v}, P & adj[v], X & adj[v], adj, cliques)
        P.remove(v); X.add(v)

def find_max_cliques(edges):
    n = len(edges)
    adj = {i: set() for i in range(n)}
    for u in range(n):
        for v in edges[u]:
            adj[u].add(v); adj[v].add(u)
    cliques = []
    bron_kerbosch(set(), set(range(n)), set(), adj, cliques)
    if not cliques: return []
    max_size = max(len(c) for c in cliques)
    return [c for c in cliques if len(c) == max_size]

# 示例
edges = [[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]
print(find_max_cliques(edges))  # [{0, 1, 2}, {0, 2, 3}]

pivot 优化的直觉：如果 pivot 和 P 中的大部分节点都相邻，那么不与 pivot 相邻的节点很少，递归分支就很少。这把 O(3^(n/3)) 的实际运行时间大幅降低。

---

总结

算法	时间复杂度	适用场景
拓扑排序	O(n+m)	DAG 线性排序
DFS 序	O(n) 预处理，O(1) 查询	判断祖先关系
Dijkstra（堆优化）	O((n+m) log n)	非负权单源最短路（稀疏图）
Dijkstra（邻接矩阵）	O(n²)	非负权单源最短路（稠密图）
Bellman-Ford	O(nm)	含负权边，检测负环
SPFA	期望 O(m)	含负权边的稀疏图
Kruskal	O(m log m)	稀疏图 MST
Prim	O((n+m) log n)	稠密图 MST
LCA（二进制提升）	O(n log n) 预处理，O(log n) 查询	树上祖先查询
匈牙利	O(nm)	二分图最大匹配
Floyd 最小环	O(n³)	求图中最小环
2-SAT	O(n+m)	布尔可满足性
最大团	O(3^(n/3))	枚举所有最大团

模板源码：AlgorithmLearning