图论

图论问题涉及整个计算机科学，图算法对计算机科学至关重要。

图片来源于网络，未能全部标注来源，不用于任何商业用途。

常用算法速查表：

Name	App	DS	Time	Space
BFS	UnWtd	Queue	$O(V+E)$	$O(V)$
DFS	Connectivity	Stack / Recursion	$O(V+E)$	$O(V)$
Dijkstra	SSSP	Binary Heap	$O((V+E) \log V)$	$O(V+E)$
	Non-neg	Fibonacci Heap	$O(E + V \log V)$	$O(V+E)$
Bm-Fd	SSSP Neg√	E-1 loops for longest possible	$O(V \cdot E)$	$O(V)$
Flyd-W	APSP	DynamicPrg	$O(V^3)$	$O(V^2)$
Kruskal	MST	DSU+ Sorting	$ElogE+E \alpha (V)$	$O(V+E)$
Prim	MST	Binary Heap	$O((V+E) \log V)$	$O(V+E)$
		Fibonacci Heap	$O(E + V \log V)$	$O(V+E)$
TopoSt	DAGs	Stack (DFS)	$O(V+E)$	$O(V+E)$

.

图的表示

对于图$G=(V, E)$，我们用G.V表示顶点的集合（Vertex Set），用G.E表示边的集合（Edge Set）。

一般有以下方法表示图：

直接把图画出来
邻接表（Adjacency List）
邻接矩阵

在大多数情况下，我们用邻接表来表示图，这是因为大多数图都是稀疏图（$E$远小于$V^2$）。唯有在稠密图（$E$接近$V^2$）的情况下，用邻接矩阵更合适。

注意，在实践中，邻接表有两种主要的表示方法：

python中用dict表示邻接表
python中用List[List[]]表示邻接表

比如说，对于有向图：

{
  "a": ["c", "d"],
  "b": ["a", "c"],
  "c": ["d"],
  "d": ["e"],
  "e": ["a"]
}

图中a指向c和d，其他以此类推。我们可以根据上图总结以下信息：

$V$ (顶点集): $$ V = {a, b, c, d, e} $$
$E$ (边集): (注意箭头的方向) $$ E = {(b, a), (b, c), (a, c), (a, d), (c, d), (d, e), (e, a)} $$
统计数据:$|V| = n = 5$ (顶点数量)，$|E| = m = 7$ (边数量)

对于无向图：

{
  "a": ["b", "c", "d", "e"],
  "b": ["a", "c"],
  "c": ["a", "b", "d"],
  "d": ["a", "c", "e"],
  "e": ["a", "d"]
}

从上图可以看到a的邻居中有e，e的邻居中也有a，即a和e是相互指向的。我们可以整理出以下信息：

$V$ (顶点集): $$ V = {a, b, c, d, e} $$
$E$ (边集): $$ E = {(a, b), (a, c), (a, d), (a, e), (b, c), (c, d), (d, e)} $$

图的相关术语还包括：

术语	定义说明
Vertices（顶点）
Edges（边）
Adjacent（相邻）	若两个顶点由一条边连接，则称它们是相邻的。
Neighbor（邻居）	与某顶点相邻的所有顶点称为它的邻居。
Directed（有向性）	就是一个顶点是否指向另一个顶点
Weighted（加权）
Incident（关联）	若一条边与一个顶点相连，则称该边与该顶点关联。
Degree（度）	与某顶点相连的边的条数称为该顶点的度。
Path（路径）	从一个顶点到另一个顶点经过的一系列边与顶点。
Simple Path（简单路径）	在一条路径中没有任何顶点是重复的
Distance / Length（距离 / 长度）	从一个顶点到另一个顶点的最短路径所包含的边数。
Cycle（环）	起点与终点相同的路径，至少包含三个顶点。
Acyclic（无环）
Simple Cycle（简单环）	除起点外不重复顶点的环。
Connected（连通）	若任意两顶点之间存在路径，则该图是连通的。
Component（连通分量）	最大的连通子图。

根据图的定义和性质，我们可以发现：

树是特殊的图（无环且拥有n-1条边，或者无环且连通）
在无向图中，每条边对两个顶点的度各贡献 1，因此所有顶点的度数之和等于边数的两倍。
一个有n个顶点的图，最少有0条边，这种图叫做完全不连通的图
连通但无环的最小图就是树
最大边数出现在完全图（complete graph）中，即每一对不同顶点之间都有一条边，这时边数为n*(n-1)/2。

树本质上就是一个连通的、无环的、无向的图。

对于一个包含 $n$ 个顶点的无向图 $T$，只要 满足以下任意一条 ，它就被定义为一棵“树”（Tree）。这就意味着这四条性质在数学上是等价的（互为充要条件）。

边数性质： $T$ 是连通的，且恰好有 $n - 1$ 条边。
解释： 如果你有5个点，连通它们且不形成环，最少且恰好需要4条边。
最小连通性： $T$ 是连通的，但在 $T$ 中删除任何一条边 $e$，图就会变得不连通。
解释： 这说明树里没有多余的边（即没有环）。所有的边都是维持连接所必需的“桥”。
无环性质： $T$ 是连通图，且没有环 (Cycles)。
解释： 这是最直观的树的定义：连通且不闭合。
唯一路径： 在 $T$ 中任意一对节点之间，有且仅有一条简单路径。
解释： 如果有两条路径，就会形成环；如果没有路径，就不连通。

有向图与无向图

对于一个图，我们要迅速观察其：

是否有方向：有向图/无向图
是否有权重：有权图/无权图

对于有向图（Directed Graph），其有两个重要的概念：

强连通分量（SCC）
有向无环图（DAG）

对于无向图（Undirected Graph），其有几个重要的概念：

连通分量（Connect Component）
割点（Cut Vertex）
桥（割边）, Bridge (Cut Edge)

一定要区分有向图和无向图的这些概念。

强连通分量（Strongly Connected Component, SCC）只适用于有向图：

在有向图中，如果 u 可以到 v 且 v 也可以到 u（双向可达），那么 u 和 v 属于同一个强连通分量。

换句话说，必须双向可达（mutually reachable）：

存在一条从 u 到 v 的有向路径
存在一条从 v 到 u 的有向路径

求强连通分量的内容参见单独的强连通分量章节。

有向无环图（Directed Acyclic Graph, DAG） 是一个讨论较多的图，比如AOV网（Activity On Vertex Network）就是有向无环图。

在DAG上可以进行拓扑排序（Topological Sort）：

拓扑排序是对有向图的顶点进行线性排序，使得对于图中的每一条有向边 $(u, v)$，顶点 $u$ 在排序中总是在顶点 $v$ 之前。

只有有向无环图（DAG） 才能进行拓扑排序。如果一个有向图包含环（Cycle），那么环上的顶点之间无法确定一个满足拓扑排序要求的线性次序。例如，在 $A \to B \to C \to A$ 的环中，如果 $A$ 在 $B$ 前，则 $B$ 必须在 $C$ 前，$C$ 必须在 $A$ 前，这就产生了矛盾。因此， DAG 是可进行拓扑排序的充要条件 。

BFS和DFS都可以实现拓扑排序。

DAG的具体内容参见BFS的拓扑排序或DFS的拓扑排序章节。

对于有环的图，通过找到强连通分量并把SCC压缩为一个顶点，可以将有环的有向图转换为DAG。相关练习参见附录部分。

连通分量（Connected Component） 是无向图的极大连通子图：

在无向图中，如果两个节点之间存在一条路径（不论怎么绕），那么它们属于同一个连通分量。

举例来说：

A -- B -- C      D -- E

在上图中，有两个连通分量：A-B-C和D-E。这里要注意，虽然A-B-C中A-B也是连通的，但是它不是一个完整的连通分量，因为连通分量是一个无向图中最大的互相可达的节点集合。

Cut Vertices & Bridge

割点（cut vertex） 只适用于无向图，其简单定义是：删除该点后，图的连通分量增加。 也可以说：对一个连通的图，如果去掉一个点导致图不连通，那么该点即为割点。

桥（Bridge）或者割边（Cut Edge）指的是删除这条边会使无向图变得不连通。

详情见Tarjan求割点/桥。

有权图与无权图

对于边上没有权重的图，我们称为无权图（Unweighted Graph）；对于边上带权重的图，我们称为有权图（Weighted Graph）。

对于无向有权图，我们常把不相连的边的权重视为0或无穷大。如果把每个顶点看做一个网络中的结点，那么：

假设边代表的是带宽，edge=0表示不相连
假设边代表的是网络延迟，那么edge=无穷大代表不通或服务器不相连

1763765437543

对于有向的权重图，道理和上面是一样的。

无权图可以看做是权重都是1或者权重都一样的特殊有权图。

稠密图与稀疏图

稠密图（Dense Graph）是指边数 ($E$) 接近最大可能边数的图；反之，边数很少的图称为 稀疏图 (Sparse Graph) 。

图的密度 $D$ 是实际边数与最大可能边数的比值。其取值范围为 $0 \le D \le 1$。可以知道：

$D = 1$：完全图 (Complete Graph)，即最稠密的图。
$D = 0$：没有边的图。

假设 $|E|$ 为边数，$|V|$ 为顶点数，那么：

对于无向简单图（Undirected Simple Graphs），最大边数为 $\binom{|V|}{2} = \frac{|V|(|V|-1)}{2}$，密度公式为：

\[ D = \frac{2|E|}{|V|(|V|-1)} \]

对于有向简单图 (Directed Simple Graphs)，最大边数是无向图的两倍（因为每条边有两个方向）。密度公式为：

\[ D = \frac{|E|}{|V|(|V|-1)} \]

在计算机科学中，判定一个图是稠密还是稀疏，并不总是依赖一个精确的“密度阈值”（比如密度大于 0.5 就是稠密），而是主要依据边数 $|E|$ 与顶点数 $|V|$ 的数量级关系 ，以及 在特定场景下选择哪种数据结构或算法更优 ：

基于渐进复杂度：根据图的增长规模和边的增长趋势来判断
基于空间效率：当$|E| \ll |V|^2$时，邻接表通常都更优，此时图被视为稀疏。
基于时间复杂度：如果一个图让 $O(|V|^2)$ 的算法跑得比 $O(|E| \log |V|)$ 的算法还要快，那他就是稠密图
经验法则：一般来说，当D<10%时默认使用邻接表，当D>30%时更优先使用邻接矩阵

广度优先搜索（BFS）

广度优先搜索BFS是最简单的图搜索算法，也是许多重要图算法的原型（比如Prim最小生成树、Dijkstra最短路径，后面会讲到）。之所以叫BFS，是因为算法需要发现所有距离源节点为k的nodes后，才会发现距离源节点为k+1的node。

为了跟踪算法的进展，BFS一般会在搜索途中为已经访问到的node进行标记，在概念表示中一般为node涂上颜色，在实际应用中一般设立一个叫做visited的set来进行记录。

在执行BFS的时候会构造出一颗BFS树。一开始，BFS树只有根节点，也就是源节点s。在扫描已发现的节点u的邻居时，每当发现一个新的未访问的node v，就将(u, v)加入到BFS Tree中。在BFS Tree中，u是v的前驱（predecessor）或父节点（parent node）。由于每个node最多被发现一次，因此每个node最多只有一个父节点。

在CLRS中，用颜色来进行区分：

白色：未访问的node
灰色：已访问的node，但是它的邻居还没有被完全检查完
黑色：已访问的node，且所有邻居都已经被发现

伪代码如下：

BFS(G, s)
1  for each vertex u ∈ G.V - {s}
2      u.color = WHITE
3      u.d = ∞
4      u.π = NIL    | 这里设为NIL是因为一开始的时候所有节点的父节点都还没有被发现
5  s.color = GRAY
6  s.d = 0
7  s.π = NIL
8  Q = ∅
9  ENQUEUE(Q, s)
10 while Q ≠ ∅
11     u = DEQUEUE(Q)
12     for each v ∈ G.Adj[u]
13         if v.color == WHITE
14             v.color = GRAY
15             v.d = u.d + 1
16             v.π = u
17             ENQUEUE(Q, v)
18     u.color = BLACK

在实践中，我们用一个visited就能记录所有的去过的点，同时python代码如下：

from collections import deque

def BFS(graph, start):
    queue = deque([start]) # 使用 deque 作为队列，性能 O(1)

    # 如果不需要存储距离，则直接用一个set visited记录已经访问过的点就可以了
    distances = {start: 0}

    parents = {start: None} # 记录路径 (前驱节点)

    # 主循环
    while queue:
        current = queue.popleft()  # 取出队首 (相当于 DEQUEUE)

        # 遍历邻居
        for neighbor in graph[current]:
            if neighbor not in distances:
                distances[neighbor] = distances[current] + 1
                parents[neighbor] = current
                queue.append(neighbor) # 加入队尾 (相当于 ENQUEUE)

    return distances, parents

# =================测试=================
# 同样的图结构
G = {
    'r': ['s', 'v'], 's': ['r', 'w'], 't': ['w', 'x', 'u'],
    'u': ['t', 'x', 'y'], 'v': ['r'], 'w': ['s', 't', 'x'],
    'x': ['w', 't', 'u', 'y'], 'y': ['x', 'u']
}

dists, paths = BFS(G, 's')

print("节点 | 最短距离 | 父节点")
for node in G:
    # 使用 .get() 防止图中有些点可能从起点无法到达（属于非连通图）
    d = dists.get(node, '不可达')
    p = paths.get(node, '无')
    print(f" {node}   |    {d}     |   {p}")

可以看到python代码比伪代码还要更加简洁明了，所以后面的部分中我们直接用python来展示代码原型。

BFS的时间复杂度是$O(V+E)$。

BFS Tree

如果我们在BFS过程中记录每个节点的父节点，那么我们就能记录BFS Tree。这棵树非常有用，可以用来：

寻找最短路径：在无权图中，BFS Tree从根节点到任意节点的路径就是最短路径
确定层级关系：六度人脉、LinkedIn社交网络等，BFS Tree可以快速告诉A和B之间隔了几个人（即计算Kevin Bacon Number）

但是我们也可以发现，假如我们以A为根建立了一颗BFS Tree，然后我们想知道C到D的距离，那么我们就必须重新以C为根建立一颗新的BFS Tree。因此BFS是单源最短路径算法。如果我们想知道All-Pairs最短路径，即任意两点间的距离，我们就需要对每个点都跑一次BFS（假设是无权图）。更多单源最短路径和All-Pairs最短路径的议题在后面会展开讲解。

拓扑排序（Kahn算法）

Kahn 算法是实现拓扑排序的一种非常流行且直观的方法，它基于广度优先搜索 (BFS) 的思想，利用顶点的入度 (In-degree) 来工作。

这里再提一下有向无环图，一个容易被忽视的点是：

有向无环图中可以存在孤立的点。

拓扑排序的核心原则是：

对于图中的任何一条有向边 $u \to v$，节点 $u$ 必须在排序中出现在节点 $v$ 之前。

让我们看看孤立节点 D：

D 没有入边（In-degree = 0） ：这意味着它不依赖于图中的任何其他节点。因此，它不需要等待任何节点被排序后才能轮到它。它可以随时被安排。
D 也没有出边（Out-degree = 0） ：这意味着它不约束图中的任何其他节点。没有哪个节点是“必须”在 D 之后出现的。

由于 D 没有依赖关系，也没有被依赖关系，它在拓扑排序中的位置是 自由的 ，不会违反任何约束条件。

这里之所以特别提DAG和孤立的点，是因为在接下来介绍的Khan算法中，必须 （或者说，它会自然而然地）考虑孤立节点，但它不需要为孤立节点进行任何特殊的处理 。实践中，我们一般先建图，建图的时候顺便更新indegree值。最后入队的时候，需要对所有图中顶点的indegree进行判断。

Kahn 算法的逻辑非常直观：在一个有向无环图 (DAG) 中，任何任务（顶点）如果没有任何前置依赖（即入度为 0），那么它就可以首先执行。因此Kahn算法其实就是持续找到图中入度为 0 的顶点，将它们从图中“移除”（即从待处理列表中移除，并减少其邻居的入度），直到所有顶点都被移除。

换句话说，我们的目标是拓扑排序，那么我们就把“根级”顶点先找出来，这些“根级”顶点自然是没有前置节点的。当我们每找到一个这样的顶点，它的邻居的in-degree就减一，这是因为已经找到的顶点我们已经把他放在结果列表中了，我们不再需要考虑他作为其他节点的前置节点。

我们来看一下算法思路：

Kahn算法

# 计算所有顶点的in-degree
遍历G的所有边(u, v)，统计有多少条边指向v

# 初始化队列
创建一个队列Q
遍历所有顶点，将所有in-degree为0的顶点加入到队列Q中

# BFS循环
只要队列Q不为空，就重复以下操作：
    出队：从队列Q中取出一个顶点u，将其加入到topo sort list中
    遍历u的所有邻居v：
        将v的in-degree减一
        如果v的in-degree减少到0，说明v的所有前置依赖都已经满足，将v加入Q

# 检查图中是否存在环
如果结果列表的顶点数量等于图中总顶点数V，则图是一个DAG
否则（如果顶点数量小于图中总顶点数V）图中存在环

Kahn算法的时间复杂度是O(V+E)，因为它只对每个顶点进行一次入度计算，并对每条边进行一次访问和入度减操作。

可以看到，Kahn算法除了可以便捷、快速地排序，其本身也可以用来检查环。

在图的DFS过程中，我们同样用三种颜色代表三种状态：

白色（WHITE）：未访问
灰色（GRAY）：递归栈中（正在访问）
黑色（BLACK）：访问完毕

当第一次探索边$(u, v)$时，我们可以通过$v$的颜色来判断边的类型：

v 的颜色	边的类型
白色	树边 Tree Edge
灰色	后向边/回边 Back Edge
黑色	需判断时间戳 ⇒ 前向边 or 横向边

树边、后向边/回边、前向边（Forward Edge）、横向边（Cross Edge）：

1763441912365

在无向图中，只会出现树边和回边。

深度优先搜索（DFS）

DFS Tree

深度优先搜索（DFS）在图中非常重要，牵扯出非常多的用法和算法。当DFS从一个源点$u$出发，沿着递归不断深入其他节点，形成一条条分支，这个深度优先搜索过程中形成的树即是深度优先树（DFS Tree）；当图不连通时，会形成多个DFS Tree，即深度优先森林（DFS Forest）。在DFS的过程中，每当一个节点从未被访问变成被访问时，这个操作叫做发现（discover） 该节点。

在深度优先搜索的时候，每个节点$v$会记录它是从哪个节点被搜索到的，这个父节点叫做它的前驱（predecessor或parent）。由于每一个节点的前驱都是在DFS第一次访问它时确定的，因此每一个节点最多只有一个前驱。DFS的前驱关系决定DFS Tree的边。所有的节点的前驱指针组成一个前驱子图。

在DFS的过程中，每个节点都会记录两个时间：

发现时间：d[v]，即discover[vertex]，当一个节点第一次被发现
完成时间：f[v]，即finish[vertex]，当一个节点所有邻居都处理完时

这里要注意，如果一个节点发现后没有邻居，结束时间也要加一，如下图所示：

1765508705365

显然，对于每个节点$u$，我们都有：

\[ u.d < u.f \]

.

我们来举例说明，看一下下面这张图：

       A → B → C
       |   |   |
       v   v   v
       D → E → F

上图对应的邻接表如下:

Adj[A] = [B, D]
Adj[B] = [C, E]
Adj[C] = [F]
Adj[D] = [E]
Adj[E] = [F]
Adj[F] = [ ]

我们从A开始做一次DFS：

首先访问A
然后访问B（从A来）
然后访问C（从B来）
然后访问F（从C来）；F没有邻居，F完成
回到C，F已经访问完，没有未访问的邻居了，C完成
回到B，访问下一个未访问的邻居E
E的邻居只有F，但是F已经访问过了，所以E完成
回到B，所有邻居都访问完了，B完成
回到A，访问A的第二个邻居D
D完成
A完成

我们把时间戳加上，可以得到下表：

节点	d[v]	f[v]
A	1	12
B	2	9
C	3	6
F	4	5
E	7	8
D	10	11

同时也可以得到前驱表：

节点	parent
A	NIL
B	A
C	B
F	C
E	B
D	A

我们把parent指针连起来，就得到了前驱子图（DFS Tree）：

.

最后看一下DFS的伪代码和实现：

def DFS(G):
    """
    G: 邻接表形式的图，例如：
        G = {
            'A': ['B', 'D'],
            'B': ['C', 'E'],
            ...
        }
    返回:
        color  : 颜色(white/gray/black)
        d      : 发现时间
        f      : 完成时间
        parent : 前驱指针(构成 DFS 树/森林)
    """
    color  = {}
    d      = {}
    f      = {}
    parent = {}

    # 初始化
    for u in G:
        color[u]  = 'white'
        parent[u] = None

    time = 0  # 全局时间戳

    def dfs_visit(u):
        nonlocal time
        time += 1
        d[u] = time          # 发现时间
        color[u] = 'gray'    # 变灰色（正在处理）

        for v in G[u]:
            if color[v] == 'white':
                parent[v] = u
                dfs_visit(v)

        color[u] = 'black'   # 处理完成
        time += 1
        f[u] = time          # 完成时间

    # 可能是非连通图，因此要遍历所有结点，得到 DFS 森林
    for u in G:
        if color[u] == 'white':
            dfs_visit(u)

    return color, d, f, parent

# 使用示例
G = {
    'A': ['B', 'D'],
    'B': ['C', 'E'],
    'C': ['F'],
    'D': ['E'],
    'E': ['F'],
    'F': []
}

color, d, f, parent = dfs(G)

.

欧拉序列

欧拉序列（Euler Tour） 可以理解为强化版的时间戳。

在时间戳版本中，我们会记录每个节点被discover和finish的时间，这样我们就能轻松判断出一个节点是否是另一个节点的祖先（Ancestor）。具体来说，如果$v$在$u$的DFS子树中，那么必然满足：

\[ d[u] < d[v] < f[v] < f[u] \]

上面的叙述等同于：$u$是$v$的祖先。这种特性来源于时间戳区间的嵌套性质：

第一次访问一个节点时会打开一个区间
回溯离开该节点时会关闭这个区间
子树中所有节点都必定在区间内部被打开和关闭
如果$v$是$u$的后代，那么DFS必然先访问$v$
如果$v$是在处理$u$的递归过程中访问到的，那么$u$必然是$v$的祖先

如果我们在DFS的过程中记录访问顺序，那么我们就得到了欧拉序列。

举例来说，我们来看下面这个有向图：

1: [2, 3]
2: [4, 5]
3: [5]
4: [2, 6]
5: [4]
6: [3]

我们从1开始，构造DFS Tree，记录时间戳，得到下表：

节点 u	d[u]	f[u]
1	1	12
2	2	11
4	3	10
6	4	9
3	5	8
5	6	7

从时间戳中我们可以轻松判断DFS Tree的结构如下：

1
└── 2
    └── 4
        └── 6
            └── 3
                └── 5

现在，我们可以从上述信息中得到很多关键信息，比如在DFS Tree中，4的时间戳被1包裹，所以1是4的祖先。

又比如，在有向图的DFS中，如果出现一条边：$u \to v$满足$v$已经被访问过，并且$v$仍然在当前DFS递归栈中（也就是灰色），那么这条边就是回边（back edge）。我们可以直接通过时间戳来判断回边，比如说：当DFS通过1、2访问到4的时候，4的邻居中有2，而现在正好在2的递归中，所以$4 \to 2$是一个回边。

我们可以用时间戳来检查，在一个有向图中，对于有向边$a \to b$，如果：

\[ d[b] < d[a] < f[a] < f[b] \]

那么我们就可以说$a \to b$是一个回边。这是因为：

b是a的祖先
a指向b

因此a到b是一个回边，该有向图有环。

在上述DFS中，我们记录每一个被访问的节点，包括再次访问到的，形成欧拉序列：

[1, 2, 4, 6, 3, 5, 5, 3, 6, 4, 2, 1]

通过欧拉序列，我们可以轻松知道两个节点的最近公共祖先（Lowest Common Ancestor），比如对于上例的欧拉序列，如果我们想知道5和6的LCA，我们可以把欧拉序列写出来：

Index:   1  2  3  4  5  6  7  8  9  10 11 12
Euler = [1, 2, 4, 6, 3, 5, 5, 3, 6, 4, 2, 1]

一共12个元素。我们可以看到：

5第一次出现时的index是6，即first[5]=6
6第一次出现时index是4，即first[6]=4

我们取欧拉序列的区间：

Euler[4..6] = [6, 3, 5]

此时还需要判断深度，我们把深度写出来：

Euler:  1  2  4  6  3  5  5  3  6  4  2  1
Depth: [0, 1, 2, 3, 4, 5, 5, 4, 3, 2, 1, 0]
Index:   1  2  3  4  5  6  7  8  9 10 11 12

可以看到在区间[4,6]的node和深度分别是：

index	node	depth
4	6	3
5	3	4
6	5	5

深度最小的node是6，因此6就是LCA。

至此我们找到了一个LCA问题的通用解法：

LCA(u, v) = 在欧拉序列中 first[u] 与 first[v] 之间的区间中，深度最小的节点。

括号定理

括号定理（Parenthesis Theorem）是很多图算法的理论基础，主要用来分析DFS时间戳、祖先关系、边的类型等。

在对有向图或无向图进行的任意DFS中，对于任意两个节点u和v来说，下面三种情况只有一种成立：

两个区间完全分离，即$[d[u], f[u]]$和$[d[v], f[v]]$完全不相交
$u$的区间完全包含$v$的区间
$v$的区间完全包含$u$的区间

根据该定理，可以推论出下列重要结论：

当$u$的区间完全包含$v$的区间时，$u$是$v$的祖先
若$u$是$v$的祖先，则DFS必然会在$u$的递归过程中访问$v$

我们还可以推导出白色路径定理（White-Path Theorem）：

如果$u$是$v$的祖先，那么从$u$到$v$存在一条全部由白色节点组成的路径。

上面的定理会在后面的一些概念中被应用，比如：

判断DFS Tree中的祖先/后代关系
判断有向图是否有环（即判断回边）
拓扑排序的正确性证明
强连通分量
寻找桥与割点

拓扑排序（DFS版）

虽然一般拓扑排序用BFS解的更多，但是对于一个确定是DAG的图，DFS求解拓扑排序的思路其实也很简单：

按照字典序或者随便找一个点，以这个点为起点进行DFS
DFS过程中，每一个节点在其所有邻居都push完成后，才能push自己
完成后reverse就是Topo Sort了

DFS Topo Sort的过程在求SCC的时候也能用到，具体参见SCC章节的Kosaraju算法。

对于一个确定是DAG的图，DFS算法非常简单：

DFS求解一个确定是DAG的Topo Sort

result = []
visited = set()

def DFS(vertex):
    遍历vertex的邻居：
        如果邻居 not in visited：
            DFS(邻居)
    result.append(vertex)

REVERSE result

但是在解决实际问题的时候，我们拿到一个图的时候不确定他是不是有环，所以仅记录是否访问过时不够的。

在图的DFS过程中，我们一般用三种颜色代表三种状态：

白色（WHITE）：未访问
灰色（GRAY）：递归栈中（正在访问）
黑色（BLACK）：访问完毕

如果记不住颜色，也可以用状态表示：

未访问：visited = "unvisited"
访问中：visited = "visiting"
访问完毕：visited = "visited"

很显然，如果我们在对一个vertex进行DFS的时候：

如果访问到一个visiting的邻居，那么图不是DAG，不能做topo sort

下面我们来看DFS的完整算法：

DFS求TOPO SORT

初始化图
设置三个状态：unvisited, visiting, visited
将所有vertex设为unvisited

DFS(vertex):
    设vertex状态为visiting
    遍历vertex的邻居：
        如果vertex的邻居是visiting：
            有环，TOPO SORT没有意义，这里可以根据自己的喜好处理
            一般我会在这里标记CYCLE=True
        如果vertex的邻居是unvisited：
            DFS(邻居)
    设vertex状态为visited
    将vertex加入到result中

访问所有vertex：
    如果vertex状态为unvisited：
        DFS(vertex)
    如果CYCLE==True:
        提前结束，result没有意义

REVERSE result，得到TOPO SORT

DFS进行拓扑排序的时间复杂度是$O(V+E)$

Tarjan求割点/桥

Tarjan是一位图论领域的专家，他在DFS基础上提出了三个著名的Tarjan算法：

Tarjan's SCC Algorithm（求强连通分量）
Tarjan's algorithm for articulation points（求割点）
Tarjan's algorithm for bridges（求桥）

顺便提一下，斐波那契堆也是Tarjan的成果。

本小节主要介绍用Tarjan算法求割点和求桥，求SCC的部分参见SCC章节。

在我的笔记中，针对无向图的两个Tarjan算法简称为“Tarjan Cut”（这是我起的名字，为了区分Tarjan SCC）。Tarjan Cut是针对无向图的。

Tarjan算法的核心有两个：

dfs
lowlink value

我们先来看dfs，这个比较好理解：

我们在无向图上做一次DFS，从某个起点开始，每到访一个新的点，就给它一个时间戳。这个时间戳代表发现时间（discovery time）。这里要注意，我们只记录第一次到访的时间，而不关注离开的时间。我们使用一个全局计数器 time，每次访问一个新的点就 dfn[u] = ++time。每一个点对应的第一次发现时间就叫做Depth-First Number, 一般简称dfn。

接下来看lowlink value（简称low值）。low-link value （Lowlink 值，一般简称low值）是 Tarjan 算法的核心，是整个算法的灵魂。

简单来说，low[u]就是u所在子树能够往上跳到的最早祖先。我们先来理解一下什么是“跳”，一般来说，在DFS中，我们总是从父节点向下走（down），比如：

父节点
 ↓
子节点
 ↓
孙节点

如果想返回上面的节点（更靠近根部的节点），一般需要往回走。然而，由于我们这里的树结构并非是在一个本身就是树的结构上产生出来的，而是在一个图结构上产生出来的DFS Tree，因此无论在多么深的节点处，都有可能突然回到上面比较浅的位置，这就是“往上跳”，也即我们在前面笔记中提到的回边。

理解往上跳的概念后，我们来看一下lowlink value或者说low值。简单来说，low值的作用就是在DFS Tree中向上回溯时，告诉我们一个节点能否通过子树绕回祖先。如果能绕回，则说明存在一条回边使得该节点、其子树、其祖先共同构成了一个环或强连通结构。

听起来有点绕，我们来看个具体的例子：

1
|
2 <- 5
|
3
|
4
|
5 -> 2

在上图中，5通过回边可以直接返回到2。很显然，在DFS过程中，我们从1开始一路访问到5，因此dfn很清晰：

dfn[1] = 1
dfn[2] = 2
dfn[3] = 3
dfn[4] = 4
dfn[5] = 5

在DFS的过程中，每当访问到一个新的node，那一刻该node自己就是它当前能到达的最早祖先，因为第一次访问到一个node的时候我们还没有看到他的子树以及他的子树的回边，所以在初次访问的时候我们可以同步将dfn值更新为low值，即：

low[u] = dfn[u]

low[1] = 1
low[2] = 2
low[3] = 3
low[4] = 4
low[5] = 5

然后DFS进行到5，这个时候发现有一个从5到2的回边，此时dfn值是：

dfn[5] = 5
dfn[2] = 2

此时我们要更新low值，更新方法如下：

当遇到一条回边时，更新：$low[u] = min(low[u], dfn[v])$

于是：

low[5] = min(low[5], dfn[2])
        = min(5, 2)
        = 2

其含义就是说：5能往上跳到节点2，而2是目前为止5能到达的最早祖先。

然后我们回溯到4，对树边(4, 5)做更新：

low[4] = min(low[4], low[5]) = min(4, 2) = 2

这里的含义是：4的子树中，节点5能往上跳到2，那么4的整个子树也就能网上跳到2。虽然4没有回边，但是它的子树有，所以4的low也必须继承子树的low。

综上，我们可以总结low值更新规则如下：

刚访问 u：low[u] = dfn[u]。
遇回边：low[u] = min(low[u], dfn[v])。
子树返回：low[u] = min(low[u], low[v])。

常见的python实现如下：

from collections import defaultdict
import sys

sys.setrecursionlimit(10**7)

def tarjan_articulation_points(n, edges):
    """
    n: 节点个数，默认点为 1..n
    edges: 无向边列表 [(u, v), ...]
    返回:
        dfn: 每个点的 dfs 序（访问时间）
        low: 每个点的 lowlink 值
        is_cut: 每个点是否为割点（True/False）
    """

    # 建图：无向图
    g = [[] for _ in range(n + 1)]
    for u, v in edges:
        g[u].append(v)
        g[v].append(u)

    dfn = [0] * (n + 1)     # dfn[u]：第一次访问 u 的时间戳
    low = [0] * (n + 1)     # low[u]：u 子树能回到的最早祖先的 dfn
    is_cut = [False] * (n + 1)  # 是否为割点
    time = 0

    def dfs(u, parent, root):
        nonlocal time
        time += 1
        dfn[u] = low[u] = time   # 初始化：low[u] = dfn[u]

        child_count = 0  # 统计 u 在 DFS 树中的儿子个数（用于根节点判割点）

        for v in g[u]:
            if not dfn[v]:
                # 树边 u -> v
                child_count += 1
                dfs(v, u, root)

                # 子树返回后，用子节点的 low[v] 更新 low[u]
                low[u] = min(low[u], low[v])

                # 非根节点割点判定：看子树能不能绕开 u
                if u != root and low[v] >= dfn[u]:
                    is_cut[u] = True

            elif v != parent:
                # 回边 u -> v，用 dfn[v] 更新 low[u]
                low[u] = min(low[u], dfn[v])

        # 根节点割点判定：根有至少两个子树
        if u == root and child_count >= 2:
            is_cut[u] = True

    # 可能是不连通图，所以要对每个未访问的点开一棵 DFS 树
    for start in range(1, n + 1):
        if not dfn[start]:
            dfs(start, parent=-1, root=start)

    return dfn, low, is_cut


# ===== 示例使用 =====
if __name__ == "__main__":
    # 你的例子：
    # 1 - 2 - 3 - 4 - 5
    #      ^         |
    #      |_________|
    n = 5
    edges = [
        (1, 2),
        (2, 3),
        (3, 4),
        (4, 5),
        (5, 2)
    ]

    dfn, low, is_cut = tarjan_articulation_points(n, edges)

    print("dfn:", dfn[1:])   # 下标从 1 开始
    print("low:", low[1:])
    print("cut points:", [i for i in range(1, n + 1) if is_cut[i]])

DFS完成后，我们可以得到dnf和low值，利用这两个列表，我们可以求无向图的割点和桥。

用Tarjan算法求割点

割点一般分为两种情况：

根节点
非根节点

首先来看根节点，当根节点有两个或以上的DFS子树时，根节点是割点。

接着来判断非根节点$u$，当$u$存在子节点$v$满足：

\[ low[v] \ge dfn[u] \]

时，非根节点$u$是割点。

也就是：

\[ child.low \ge parent.d \]

时，parent是割点。（这个记法更好记）

理由很简单：子树$v$不能绕过$u$，因此删除$u$后$v$子树会全部断开，所以$u$是割点。

在实现的时候，我们只需要分别把根节点和非根节点的求割判断写下来就可以：

# 根节点求割
if u == root and child_count >= 2:
    is_cut[u] = True

# 非根节点求割
if u != root and low[v] >= dfn[u]:
    is_cut[u] = True

.

用Tarjan算法求桥

对每条DFS树边(u → v)判断，若：

\[ low[v] \gt dfn[u] \]

则(u, v)是桥。

理由很简单：v的子树跳不回来，所以(u, v)是唯一的连通路径，删除它会让图断开。

在实现时，我们只需要在树边返回后加一句判断：

# 求桥
if low[v] > dfn[u]:
    bridges.append((u, v))

.

强连通分量（SCC）

本章节介绍如何找到强连通分量，以及如何利用强连通分量（比如压缩SCC为顶点，来把有环的有向图转换为DAG）。强连通分量是针对有向图的。

Kosaraju算法

Kosaraju算法（科萨拉珠算法）非常的巧妙。在前文中我们已经掌握了使用DFS去求TOPO SORT，Kosaraju的第一步和DFS拓扑排序的第一步非常像，都是从一个顶点开始进行DFS然后得到一个按照finishing time访问顺序记录的列表。不过在一次DFS并得到该列表后，Kosaraju就进入到了新的步骤中，这是因为TOPO SORT针对的是有向无环图，而Kosaraju针对的是有向有环图。

Kosaraju算法的核心思路如下：

按照finishing time记录DFS的顺序
将图反转
在反转图上，所有从未访问节点开始DFS的构成一个SCC

Kosaraju 算法以其清晰、直观的思路和优秀的 $O(|V| + |E|)$ 线性时间复杂度 ，成为了理解强连通分量的经典算法。

我们以下面这个图为例，讲解一下Kosaraju算法：

有向图 $G$ ：

A → E
B → A, E, F
C → D
D → A
E → C
F → C, G
G → B

1763768912239

其反向图$G^T$就是所有的方向全部反过来，如下所示：

1763768927835

我们来看一下Kosaraju算法的过程：

步骤 1: 第一次 DFS (计算完成时间)

我们对原图 $G$ 进行深度优先搜索（DFS），并记录每个顶点被完全访问（即其所有邻接点及其子孙都被访问）时的完成时间 $f[v]$。

初始点	DFS 路径	完成时间 f[v]
A	A → E → C → D → A	$f[D]=6, f[C]=7, f[E]=8, f[A]=9$
B	B → F → G → B	$f[G]=17, f[F]=18, f[B]=19$

假设我们从 A 开始，然后从 B 开始，并按照 A, B, C, D, E, F, G 的顺序检查邻接点。

所有顶点的完成时间：

顶点	A	B	C	D	E	F	G
$f[v]$	9	19	7	6	8	18	17

步骤 2: 顶点排序

将所有顶点按照它们的完成时间 $f[v]$ 从大到小 （即逆序）排列，得到一个顶点列表 $L$。

完成时间 f[v]	19	18	17	9	8	7	6
顶点$v$	B	F	G	A	E	C	D

排序后的列表 $L$： $[B, F, G, A, E, C, D]$

步骤 3: 构造反向图 $G^T$

我们将原图 $G$ 中所有边的方向反转，得到反向图 $G^T$。

*$G^T$ 的边：*

A $\leftarrow$ B, D
E $\leftarrow$ A, B
F $\leftarrow$ B
D $\leftarrow$ C
C $\leftarrow$ E, F
G $\leftarrow$ F
B $\leftarrow$ G

*步骤 4: 第二次 DFS (寻找 SCC)*

我们使用在步骤 2 中得到的完成时间逆序列表 $L = [B, F, G, A, E, C, D]$，依次在反向图 $G^T$ 上进行 $\text{DFS}$ 遍历。每一次从尚未被访问过的顶点开始新的遍历，所发现的顶点集合即为一个强连通分量 ($\text{SCC}$)。

处理顶点 $\text{B}$: $\text{B}$ 是列表 $L$ 中第一个未被访问的顶点，我们以它为起点开始 $\text{DFS}$。在 $G^T$ 中，遍历路径为 $\text{B} \to \text{G} \to \text{F} \to \text{B}$。所有通过这次 $\text{DFS}$ 遍历到的顶点构成了第一个强连通分量：$\{\text{B}, \text{F}, \text{G}\}$。完成这次遍历后，我们将 $\text{B}, \text{F}, \text{G}$ 标记为已访问。
处理顶点 $\text{F}$ 和 $\text{G}$: 尽管 $\text{F}$ 和 $\text{G}$ 在列表 $L$ 中紧随 $\text{B}$ 之后，但它们已被标记为已访问（属于前一个 $\text{SCC}$），因此被跳过。
处理顶点 $\text{A}$: $\text{A}$ 是列表 $L$ 中下一个未被访问的顶点，我们以它为起点开始第二次 $\text{DFS}$。$\text{A}$ 的邻接点有 $\text{B}$ 和 $\text{D}$；由于 $\text{B}$ 已经被访问，我们只沿着 $\text{D}$ 继续。遍历路径为 $\text{A} \to \text{D} \to \text{C} \to \text{E} \to \text{A}$。在遍历过程中，尽管 $\text{A}$ 或 $\text{E}$ 在 $G^T$ 中可能指向已访问的 $\text{B}$，但 $\text{DFS}$ 不会沿着已访问的节点继续探索。这次遍历到的顶点集合构成了第二个强连通分量：$\{\text{A}, \text{C}, \text{D}, \text{E}\}$。我们将 $\text{A}, \text{C}, \text{D}, \text{E}$ 标记为已访问。
处理顶点 $\text{E}, \text{C}, \text{D}$: 列表 $L$ 中剩下的 $\text{E}, \text{C}, \text{D}$ 都已被标记为已访问，因此跳过。

至此，所有顶点都已被处理。最终找到的强连通分量是 $\{\text{B}, \text{F}, \text{G}\}$ 和 $\{\text{A}, \text{C}, \text{D}, \text{E}\}$，结论正确。

Tarjan算法

SCC缩点

在一个 SCC 内，你可以访问该 SCC 内的任何其他节点，并且可以回到起点。从算法角度看，一个 SCC 就是一个“整体”，你可以通过路径收集 SCC 内所有节点的属性（例如经典应用例题Coin Collector中的金币）。

我们把每一个单独的SCC压缩为一个新的单一节点（通常称为SCC节点），把原图节点的权重总和设定为新的节点的权重，我们就完成了一次SCC 缩点 ，也称为图的凝结 (Condensation)。

SCC缩点后的变化：

*节点转化：* 原图 $G$ 中的每一个 SCC 被压缩成新图 $G'$ 中的一个 单一节点 （通常称为超级节点或 SCC 节点）。
节点权重： 新节点 $C_i$ 的权重等于其包含的 所有原图节点属性的总和 （例如，所有金币的总和）。
边转化： 如果原图 $G$ 中存在一条边 $u \to v$，且 $u$ 属于 SCC $C_A$，$v$ 属于 SCC $C_B$，那么如果 $C_A = C_B$，则这条边在 $G'$ 中被忽略（因为它是 SCC 内部的环）；如果 $C_A \neq C_B$，则在 $G'$ 中添加一条新的边 $C_A \to C_B$。

SCC 缩点后得到的图 $G'$ 具有一个至关重要的性质：

凝结图$G'$一定是一个有向无环图（DAG）。

以求解最大和路径为例（也就是下面经典应用中的例子Coin Collector），问题可以被转化为下列清晰的三个步骤：

阶段	任务目标	算法工具	复杂度
I. SCC 求解	找出原图$G$的所有 SCC 并计算它们的总权重。	Kosaraju 算法或 Tarjan 算法	$O(N+M)$
II. DAG 构建	基于 SCC 之间的连接关系，构建凝结图$G'$。	遍历$G$的所有边	$O(N+M)$
III. 路径求解	在点带权重的 DAG$G'$上寻找最大和路径。	拓扑排序 + 动态规划 (DP)	$O(N_{SCC} + M_{DAG}) \le O(N+M)$

无论是用Kosaraju算法还是Tarjan算法，其实现SCC缩点的时间复杂度都是$O(N+M)$。

通过SCC缩点，我们可以对带环的有向图进行准拓扑排序（Quasi Topo Sort），本质上就是先转换为标准的DAG，然后再拓扑排序。

双连通分量（BCC）

双连通分量是针对无向图的。

双连通分量（Biconnected Component, 简称BCC） 指的是在无向图中具有容错性的子结构。简单来说，在BCC内部，至少需要破坏两个元素才能把它弄断。依据破坏点和破坏边，BCC分为两类：

边双连通分量（Edge-Biconnected Component, e-BCC）
点双连通分量（Vertex-Biconnected Component, v-BCC）

v-BCC比e-BCC稍微复杂一点，但也是更常见的一种定义。一般情况下，如果只是说双连通分量而没有说明是哪一种情况，我们更倾向于默认指的是v-BCC。

e-BCC

一个无向图（或子图）是 边双连通的 (Edge-Biconnected) ，如果它：

是连通的。
不包含任何桥 (Bridge-free) 。
即：删除任意一条边，图仍然连通。

边双连通分量 (e-BCC) 指的是无向图中极大的 (Maximal) 边双连通子图。“极大”意味着你不能再向这个子图中添加任何节点或边，否则它就会包含桥，从而失去边双连通的性质。

e-BCC的性质与结构：

缩点 (Contraction) ：如果我们把图中的每一个边双连通分量看作一个“超级节点”，把原来的桥看作连接它们的边，那么原图就会变成一棵 树 (Tree) （或者森林）。
等价条件 ：根据 门格尔定理 (Menger's Theorem) ，一个图是边双连通的，当且仅当任意两个顶点之间至少存在两条 边不相交的路径 (Edge-disjoint paths) 。

求解e-BCC通常使用Tarjan Cut算法：

使用Tarjan Cut找到Bridge后，再做一次DFS/BFS，只要不走桥，那么能摸到的所有点就是一个eBCC。

v-BCC

通常直接说“双连通分量”时，默认指的就是v-BCC。

一个无向图（或子图）是 点双连通的 (Vertex-Biconnected) ，如果它：

是连通的。
不包含任何割点 。
即：删除任意一个节点，图仍然连通。

点双连通分量 (v-BCC) 指的是无向图中极大的 (Maximal) 点双连通子图。

这里要注意，边双连通具有传递性，即，若 𝑥,𝑦边双连通，𝑦,𝑧边双连通，则 𝑥,𝑧边双连通。但点双连通不具有传递性，反例如下图，𝐴,𝐵点双连通，𝐵,𝐶点双连通，而 𝐴,𝐶不点双连通。

1763839256561

在v-BCC中，一个割点可以同时属于多个点双连通分量 。

形象理解 ：想象两个铁环扣在一起，相扣的那个点就是割点。左边的铁环是一个 v-BCC，右边的铁环也是一个 v-BCC，而中间那个点被两者共享。

边的归属 ：图中的每一条边，恰好属于一个点双连通分量。

由于割点属于多个分量，不能简单地像“边双”那样把分量缩成一个点。我们需要构建一种特殊的树，称为 圆方树 (Block-Cut Tree)。

vBCC和eBCC不同，eBCC可传递，而vBCC不可传递，这就注定找vBCC不能简单地通过找到cut vertex然后删掉来完成。一定要记住：

割点本身也是vBCC的一部分。

因此我们用Tarjan Cut算法找到割点后，不能直接删掉，而是必须把割点复制若干份，分别给予该割点所在的分量。因此找vBCC必须用栈。

圆方树

圆方树 (Block-Cut Tree)是专门为点双连通分量 (v-BCC) 服务的。圆方树（Block-Cut Tree）是把原图中“复杂的纠缠关系”解耦成“清晰的树状关系”的最终形态。

圆方树的思路是： 既然割点既属于 A 分量又属于 B 分量，那我干脆 不合并点 ，而是新建一些虚拟节点来代表分量。在圆方树中，原来的每个点对应一个圆点，每一个vBCC对应一个方点。

1763839931997

最小生成树（MST）

最小生成树（Minimum Spanning Tree, MST）就是在一个连通的加权无向图中找到一颗最小权重的生成树。如下图所示：

1763845373430

根据树的性质，我们知道MST一定：

包含了原图中的n个节点
只有n-1条边
连通
在图能转换的所有树中，总权重最小的那一个

MST核心性质

MST有几个最重要的性质，必须单独记忆：

割性质：对于图中任意一个割，如果其相连的某条边严格小于其他边，那么这个边一定在MST中
环性质：任何一个环中如果有一条边严格大于其他边，那么这条边不会被MST所采用
图中所有边中，如果存在一条严格小于其他边的边，那么这条边一定在MST上
如果图中所有边的权重都互不相等，那么MST是唯一的

Cut Lemma

Cut Lemma （割引理），也常被称为 Cut Property （割性质）或 Cut Theorem （割定理），是最小生成树 (Minimum Spanning Tree, MST) 算法（如 Prim's 算法 和 Kruskal's 算法 ）正确性的基础。

割引理的表述如下：

给定一个连通且带权的图 $G = (V, E)$，令 $(S, T)$ 是图 $G$ 的一个割。如果边 $e=(u, v)$ 是割集 $\delta(S)$ 中权重最小的边（即 $w(e) \le w(f)$，对于所有 $f \in \delta(S)$），则边 $e$ 一定属于图 $G$ 的某个最小生成树。

割引理保证了在图 $G=(V, E)$ 中，如果一条边是横跨割 (Cut) 的所有边中权重最小的，那么这条边一定属于图 $G$ 的某个最小生成树。

最小化最大边

最大边的意思就是一条路径上权重最大的那条边，最小化最大边（minimax） 就是让一条路径中最大的边尽可能小。

MST自动满足minimax性质：

在任意图中，MST 给出的任意两点之间的路径，都是所有可能路径中“最大边最小”的那一条。

又或者说：

MST 在所有瓶颈生成树中的总权最小。

瓶颈生成树（Bottleneck Spanning Tree）的意思是最大边最小的生成树。MST一定是瓶颈生成树，但瓶颈生成树不一定是MST。

MST之所以一定是瓶颈生成树，是因为MST：

先选小边
能不用大边绝对不用大边
能连通的时候绝不跳到更大的边

因此MST的最大边一定已经尽可能小，而且MST必然是一个瓶颈最优的生成树。

minimax是MST一个非常重要的性质，可以解决非常多的现实问题，比如：

最小化最大延迟的路径
最小化最大危险/最大难度的路径，比如登山路线
找到两点之间最小瓶颈路径（Minimum Bottleneck Path）
网络带宽优化，找到最小化最大延迟瓶颈的路线

上面提到的最小瓶颈路径（Minimum Bottleneck Path）指的是两点之间所有可能的路径中，可以让这条路径中“最坏的那条边”尽可能小的那条路。这两点在MST中的那条路径天然就是最小瓶颈路径。

这里最小瓶颈实际上就是最小化大边。你可以把边理解为网络延迟或者交通，那么一个网络中最大的瓶颈就是延迟最高或者最堵车的那一段。最小瓶颈路线就是尽可能让最拥堵的路段不那么堵，也就是最小化最大边（minimax）。

Prim（种树）

Prim算法的思路是种一棵树，让树从一个节点增长到N个节点。在每一轮“生长”中，添加一个新的节点和一条边。在生长过程中，保证树是无环且连通的。这里要注意，Prim算法只记录一个节点距离MST的最短距离。

标准Prim算法的核心思想是贪心，从一个点开始，每次将离当前生成树最近的节点加入进来。其主要步骤如下：

首先是初始化一个Min-Heap，用来存储所有的顶点。这里设置起始点 $r$ 的 key（距离）设为 0，其他所有点的 key 设为无穷大 ($\infty$)。
然后就是主循环，只要min-heap还有元素：
Extract-Min: 取出 key 值最小的顶点 $u$，将其加入最小生成树（MST）。
Relax： 遍历 $u$ 的所有邻居 $v$。如果 $v$ 还在优先队列中，且边权 $w(u, v)$ 小于 $v$ 当前的 key 值，则更新 $v.key = w(u, v)$，并将 $v$ 的父节点设为 $u$。这一步需要调用 Decrease-Key 操作。

很显然，假设图中有V个节点，那么Prim需要运行N次循环。

我们来分析一下Prim算法的时间复杂度：

初始化：建堆需要$O(V)$
外层循环执行$V$次，因为每个顶点都要出队一次（Extract-Min），在最小堆中取出最小值（这里注意取出需要从堆中移除元素）需要$O(log V)$，总共取出$V$次，因此耗时$O(VlogV)$。
Relax：内层循环遍历所有的边，对于每条边，可能执行一次Decrease-Key。在最小堆中修改一个值并调整堆（Sift Up），需要$O(log V)$，总共最多$E$次，因此耗时$E log V$。

因此我们可以看到，总共的时间复杂度就是：

\[ O(V \log V + E \log V) = O((V+E) \log V) \]

对于连通图，通常 $E \ge V-1$，所以一般简写为 $O(E \log V)$

这里要注意，如果使用斐波那契堆进行优化，Prim算法的时间复杂度可以达到$O(E + V \log V)$。然而，斐波那契堆的优化是否能达到理论上的更快速度，取决于$E$和$V$的关系。在稠密图中，$E \approx V^2$，斐波那契堆更快。但斐波那契堆实现起来非常复杂，因此在实际使用中，一般都默认Prim使用最小堆。

桶排序优化

我们来看这样一个特殊情况：边权是整数，且在集合 $\{1, 2, \dots, k\}$ 中，其中 $k = O(1)$（即 $k$ 是一个很小的常数）。

我们已经知道，Prim算法的约束在于从堆中取出最小值的$O(logV)$和调整最小堆进行Sift Up的$O(log V)$。那么对于一些能满足上述特殊情况的例子，比如权值范围非常小（类似考试分数的范围，或者年龄范围），我们不需要用基于比较的排序结构（堆），而是可以用类似桶排序（Bucket Sort）或计数排序（Counting Sort）的思想。

数据结构替换：

不再使用二叉堆。
改用一个 大小为 $k+1$ 的数组 。数组的索引 $0, 1, \dots, k$ 代表可能的边权值。
这里要注意，Bucket的下标本身就代表了边的权重，其本身就是从小到大排列的自然数，因此我们只需要从0开始找到第一个非空的Bucket，里头存放的一定是最小值。
数组的每个位置存储一个 双向链表（Doubly Linked List） ，里面存放具有该 key 值的顶点。
为什么用双向链表？ 因为我们需要在 $O(1)$ 时间内从链表中间删除一个节点（用于 Decrease-Key）。比如一个节点的权重一下子从10骤降到2，这个时候我们就要把这个node从bucket10中移动到bucket2中，我们预选在Pos数组中存储了顶点v的节点指针，因此调整起来可以很快，这是list或者set等其他数据结构无法做到的。

我们来看该特殊情况下的算法流程：

输入：连通图 $G=(V, E)$，边权 $w(u, v) \in \{1, 2, \dots, k\}$，起始点 $r$。

数据结构：

Buckets（桶数组） ：大小为 $k+1$ 的数组 B，B[i] 是一个双向链表。
Key 数组 ：key[v] 存储顶点 $v$ 到 MST 的最小距离，初始化为 $\infty$。
InMST 数组 ：布尔标记，记录顶点是否已处理。
Pos 数组 ：pos[v] 存储顶点 $v$ 在双向链表中的节点指针（用于 $O(1)$ 删除）。

算法步骤 ：

1、初始化 (Initialization) ：

将所有顶点的 key 设为 $\infty$，parent 设为 NULL。
设起始点 key[r] = 0。
将 $r$ 插入到链表 B[0] 中，并更新 pos[r]。

2、主循环 (Main Loop) ：

定义变量 idx = 0 (当前扫描到的最小桶索引)。
当 MST 未包含所有顶点时，执行以下操作：
a. Extract-Min (寻找最小点) ：
- 当 B[idx] 为空时，执行 idx = idx + 1。（寻找第一个非空桶）
- 从 B[idx] 的头部取出顶点 $u$。
- 标记 u 为 InMST = true。
b. Relax (松弛邻边) ：
遍历 $u$ 的所有邻接点 $v$，边权为 $w$：
- 如果 $v$ 不在 MST 中且 $w < key[v]$：
- 步骤 i (移除旧值) ：如果 key[v] 不是 $\infty$，利用 pos[v] 指针，将 $v$ 从原来的桶 B[key[v]] 中移除（$O(1)$ 操作）。
- 步骤 ii (更新数据) ：更新 key[v] = w，parent[v] = u。
- 步骤 iii (插入新值) ：将 $v$ 插入到新桶 B[w] 的头部。
- 步骤 iv (更新指针) ：更新 pos[v] 指向新位置。
- 优化细节 ：如果 $w < idx$，可以重置 idx = w（虽非必须，但可加速查找）。

3、结束：输出 parent 数组定义的最小生成树。

时间复杂度：

Extract-Min (取出最小点):
操作： 从数组下标 0 开始扫描，找到第一个非空的链表。取出该链表头部的顶点。
耗时： 因为 $k$ 是常数 $O(1)$，扫描数组只需常数时间。从链表头取元素也是 $O(1)$。所以 Extract-Min 是 $O(1)$ 。
Decrease-Key (更新邻居):
操作： 当我们需要把顶点 $v$ 的权重从 old_w 减少到 new_w 时：
1. 在数组下标 old_w 对应的双向链表中，找到 $v$ 并将其移除（$O(1)$，前提是我们维护了指向节点的指针）。
2. 将 $v$ 插入到数组下标 new_w 对应的链表头部（$O(1)$）。
耗时： 整个过程全是链表指针操作，耗时 $O(1)$ 。

总时间复杂度计：

Extract-Min： 执行 $V$ 次，每次 $O(1)$ $\rightarrow$ 总共 $O(V)$。
Decrease-Key： 执行 $E$ 次，每次 $O(1)$ $\rightarrow$ 总共 $O(E)$。
总计： $O(V + E)$。

我们来看一个具体的应用案例。假设你要在一款瓦片式游戏（Tile-based Game）或者城市规划模拟器中，为一个区域铺设最省钱的输油管道或电网（最小生成树问题）。

地图被划分为 $N \times M$ 的网格。每一个格子（Tile）就是一个节点。图的规模很大（例如 $1000 \times 1000$ 的地图，有 100 万个点）。每个格子只与上下左右相邻的格子相连（网格图，Grid Graph）。

地形决定了铺设管道的成本。地形种类是非常有限的。我们定义铺设成本如下：

平地 (Grass) ：成本 = 1
森林 (Forest) ：成本 = 2
沙地 (Sand) ：成本 = 3
浅水 (Water) ：成本 = 4
岩石 (Rock) ：成本 = 5

注意：不存在成本为 1.54 或者 3.99 的情况，成本严格属于整数集合 $\{1, 2, 3, 4, 5\}$。这里 $k=5$。

这个案例中，我们可以发现以下两个特点：

数据量巨大 ：对于一张高清大地图，节点数 $V$ 可能达到百万级，边数 $E \approx 4V$。
权重范围极小 ：$k$ 只有 5。

我们可以粗略估算一下两种Prim的性能差异：

普通 Prim ($E \log V$) ：$4,000,000 \times \log_2(1,000,000) \approx 4,000,000 \times 20 = 80,000,000$ 次操作。
优化 Prim ($E + V$) ：$4,000,000 + 1,000,000 = 5,000,000$ 次操作。

优化后的算法比普通算法快了 16倍 左右，这在实时渲染或游戏加载中是巨大的优势。

斐波那契堆优化

如前面所提到的，斐波那契堆理论上可以优化但是实现复杂，所以一般没人用。（除非是特别需要）

使用二叉堆：

\[ \text{总耗时} \approx \underbrace{E \times \log V}_{\text{处理边}} + \underbrace{V \times \log V}_{\text{处理点}} \]

痛点： 每次处理一条边（松弛操作），都要承受 $\log V$ 的代价。

使用斐波那契堆：

\[ \text{总耗时} \approx \underbrace{E \times 1}_{\text{处理边}} + \underbrace{V \times \log V}_{\text{处理点}} \]

突破： 现在处理一条边，代价变成了常数 $1$（摊还）。

改用斐波那契堆后，“处理边”这件事变得极其廉价，算法的瓶颈从“边”转移回了“点” ($V \log V$) 上。绝大多数有实际意义的连通图中，边的数量都大于点的数量，因此算法瓶颈从边转换为点是有意义的。

Kruskal（森林合并）

Kruskal的基本想法是维持一个森林，每一轮循环会找到一条合格的边来连接两颗树，当森林中只剩下一棵树的时候就是MST。

很显然，假设图中有E条边，那么Kruskal最多循环E次。

我们把一个图中的所有顶点各自都视为一颗树，算法思路如下：

Kruskal算法

用一个最小堆（优先队列）记录所有的边和权重
集合T记录所有被选中的边，初始化时为空集

循环（直到T的边数=图的节点数-1）：
    取出最小堆中最小的边：
        如果该边的两端分别属于两颗树，则将该边加入T，将两棵树连接在一起

Kruskal的时间复杂度为$O(E \lg V)$。（注意：必须使用并查集，并查集的相关内容参见并查集章节）

并查集 DSU

并查集（Union-Find） 是一种用来处理不相交集合（Disjoint Sets, DSU）的数据结构。

并查集的核心基本操作包括：

MakeSet: 为每个元素创立一个独立的集合
Union: 将两个元素所在的集合合并
Find: 查询某个元素所在集合的代表

并查的主要作用包括：

查找图上有没有环
Prim算法中查找两个节点是否在一棵树上

注意：并查集适用于合并和查询，不适用于分离集合。

并查集使用路径压缩和按秩合并将时间复杂度大大提升：

优化策略	FIND 时间	UNION 时间	备注
无优化	O(n)	O(n)	链状树，最差
路径压缩	O(α(n))	O(α(n))	树变平但可能不平衡
按秩合并	O(log n)	O(log n)	高度有上界
路径压缩 + 按秩合并	O(α(n)) ≈ O(1)	O(α(n)) ≈ O(1)	最强，无敌

一般情况下，并查集默认指经过路径压缩和按秩合并优化的版本。

上表中的$\alpha (n)$是反阿克曼函数（Inverse Ackermann Function），增长极慢，把宇宙中所有的原子都放进来其函数值都不会超过4，因此在工程实践中通常认为优化后的并查集操作是$O(1)$的。

parent数组

1763859289827

我们用一个叫做parent的数组来记录每一个节点的父节点。

对于非数字型的节点，我们可以使用一个字典来作映射：map = {node: index}

parent数组是并查集的核心，任何node都可以通过parent数组一直向上找直到找到根节点（值一般设置为-1）。

换句话说，并查集中的 FIND操作本质上就是查找节点所在集合的那棵树的根节点。如果两个节点的所在集合的那棵树的根节点一样，也就是 find(x)==find(y)，那么x和y就是在同一个集合。

同样的，并查集中的 UNION操作本质上就是让一个集合的根节点指向另一个集合的根节点。比如说：

集合A 的根 = rootA
集合B 的根 = rootB

要合并集合A和集合B，只需要让 parent[rootA] = rootB就可以了。

这里要注意，不能直接把x的parent设置为y，必须通过find操作找到根来挂。因为只有集合的根节点能代表一个集合，如果你把中间的某个节点的parent设置为另一个节点，相当于把集合树丛中间拦腰截断了，会导致整个集合的结构被破坏。

路径压缩

路径压缩（Path Compression） 是并查集中最核心的优化，其操作是：

在执行FIND查找根节点的过程中，把路径上所有节点都直接挂在根节点上。

通过路径压缩，大大降低了树的高度，下一次查找这些节点的时候就可以一步到达根，大大加快速度。

路径压缩的代码非常简短：

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])   # ★ 路径压缩
    return parent[x]

.

按秩合并

按秩合并 (Union by Rank) 就是在执行 union 操作时，总是将较矮的树（Rank 小）附加到较高的树（Rank 大）上。这防止了树的高度无谓增长。这里的 "Rank" 近似表示树的高度。另一种变体是 "Union by Size"（按大小合并），效果类似。

实现版本

古法版本

本小节介绍古早教学版（也称为古法版本）。请注意，这个版本只提供一个早期人们构造并查集的思路，但现代工程实践没有人会用这种方法。古早教学版和现代方法的区别如下：

古法版本：链表法+加权合并（工程实践中绝对不会使用该方法）
现代方法：树结构+路径压缩+按秩合并（工程实践中使用该方法）

这里介绍古法版本主要是为了应对一些学校和课程的教学需求。在计算机科学的初期，链表法的确是存在过的，不过昙花一现。我们先来看一下并查集实践上大致的一个历史脉络：

计算机诞生之初的远古版本：原始树结构
计算机刚诞生的古法版本：链表法+加权合并
现代方法（1975年确立）：树结构+路径压缩+按秩合并

1975年，Tarjan在论文《Efficiency of a Good But Not Linear Set Union Algorithm》，证明了路径压缩和按秩合并可以达到O(α(n))，性能几乎最优，因而确定了并查集的现代方法版本。这也是为什么在整整50年后的今天，学校还在讲链表法的时候我会觉得很无语的原因。

那我们来看一下古法版本是如何用链表来实现并查集的。在古法版本中，一个集合（Set）就是一个单向链表，集合对象（Set Object or Dummy Head）是一个特殊的管理对象，每个集合都有一个。集合对象包含三个关键字段：

Head：指向链表的第一个元素
Tail：指向链表的最后一个元素（为了方便在末尾拼接）
Size：记录链表中有多少个元素（为了加权合并使用）

元素节点（Node）包含：

val：数据本身
Next：指向下一个节点
Rep：指向集合对象

三大操作流程如下：

MAKE-SET(x)
创建一个新的集合对象，Head和Tail指向x，Size=1
x的Rep指向自己
复杂度：O(1)
FIND-SET(x)
拿到节点x，顺着Rep找到集合对象，返回集合对象的Head
复杂度：O(1)
UNION(x, y)
找到x所在的集合S_x, 和y所在的集合S_y
比较S_x和S_y的大小，把size小的贴在大的后面：
- S_x.Tail.next = S_y.Head
- S_x.Tail = S_y.Tail
- S_x.Size = S_x.Size + S_y.Size
最后要刷指针，遍历小集合S_y中的每一个node，把Rep改为S_x

我们可以看到最耗时的环节在UNION操作中的刷指针。如果我们不看大小，随机合并。可能每次都把一个很大的集合合并到一个很小的集合里，导致我们要更新那个大集合里所有人的指针。最坏单次 UNION 是 $O(n)$。

然而，我们可以使用更加聪明的方法：加权合并（Weighted Union）。我们规定只更新小集合成员的指针，假设一个元素 $k$ 的指针被修改了，这说明它所在的集合被合并到了一个更大的集合里。合并后，新集合的大小至少是原集合大小的 2倍（因为大 $\ge$ 小，所以大+小 $\ge$ 2小）。所以如果总共有 $n$ 个元素，一个元素所在的集合大小从 1 翻倍到 $n$，最多只需要翻倍 $\log_2 n$ 次。也即是说，任意一个元素的指针最多被修改 $\log_2 n$* 次：

总复杂度：$m$ 次操作的总代价是 $O(m + n \log n)$。
摊还代价 ：平均下来每次 UNION 是 $O(\log n)$。

对于古法版本，我们只需要记住：UNION的Amortized时间复杂度是O(log N)。这比现代方法的O($\alpha(N)$)慢很多。Tarjan之所以说现代方法不是linear，是因为反阿克曼函数虽然实际上近似线性，但是在无穷的概念里他确实是在不断变大的。换句话说，$m \cdot \alpha(n)$ 不是严格的线性 $m$。它是一条 极其极其极其平缓的向上弯曲的曲线 ，在数学分类上它是“超线性（Super-linear）”的。

Tarjan证明了使用路径压缩和按秩合并的现代方法最坏情况上界是$O(m \alpha(n))$。这说明了算法有多快。后来在1989年，Fredman和Saks在论文《The cell probe complexity of dynamic data structures》中证明了Tarjan提出的现代方法是理论下界。换句话说，理论上不存在一种并查集算法能达到真正的 $O(1)$ 平均时间（也就是总时间 $O(m)$），哪怕你用量子计算机（在经典数据结构语境下）也不行。

标准并查集

在了解上面的核心概念后，我们来看一下标准并查集（包括路径压缩和按秩合并的现代方法）的实现。请注意：一定要熟练掌握标准并查集，这是一个经常要用到的数据结构。

这里注意，在算法题和高性能场景中，用数组来记录parent是更常见的方法。在绝大多数图论和并查集的题目中，节点通常被给出为 0 到 n-1 的整数，或者是一个二维矩阵的坐标（可以转化为整数索引）。

但是对于节点并非整数的情况，使用字典会更方便。

标准并查集实现如下：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [1] * n
        self.count = n  # 记录连通分量数量

    def find(self, p):
        if self.parent[p] != p:
            self.parent[p] = self.find(self.parent[p]) # 路径压缩
        return self.parent[p]

    def union(self, p, q):
        rootP = self.find(p)
        rootQ = self.find(q)
        if rootP == rootQ:
            return False

        # 按秩合并
        if self.rank[rootP] > self.rank[rootQ]:
            self.parent[rootQ] = rootP
        elif self.rank[rootP] < self.rank[rootQ]:
            self.parent[rootP] = rootQ
        else:
            self.parent[rootQ] = rootP
            self.rank[rootP] += 1

        self.count -= 1
        return True

如果输入节点非整数，比如ABC这种，我们需要用dict来实现：

class UnionFind:
    def __init__(self):
        self.parent = {} # 存储节点的父节点 {node: parent_node}
        self.rank = {} # 存储树的高度/秩 {node: rank_value}
        self.count = 0 # 记录连通分量的数量

    def add(self, x):
        # 添加新节点 x。如果 x 已经存在，则什么都不做。
        if x not in self.parent:
            self.parent[x] = x
            self.rank[x] = 1
            self.count += 1

    def find(self, p):
        # 查找 p 的根节点，并进行路径压缩。
        # 如果 p 不存在，可以选择报错或者自动添加（这里选择自动添加以增强鲁棒性）。
        if p not in self.parent:
            self.add(p)
            return p # 新加的节点，根就是自己

        # 路径压缩 (Path Compression)
        if self.parent[p] != p:
            self.parent[p] = self.find(self.parent[p])
        return self.parent[p]

    def union(self, p, q):
        # 合并 p 和 q 所在的集合。
        rootP = self.find(p)
        rootQ = self.find(q)

        if rootP == rootQ:
            return False

        # 按秩合并 (Union by Rank)
        if self.rank[rootP] > self.rank[rootQ]:
            self.parent[rootQ] = rootP
        elif self.rank[rootP] < self.rank[rootQ]:
            self.parent[rootP] = rootQ
        else:
            self.parent[rootQ] = rootP
            self.rank[rootP] += 1

        self.count -= 1
        return True

    def is_connected(self, p, q):
        return self.find(p) == self.find(q)

如果INPUT是邻接表：

def solve_adjacency_list(n, adj):
    """
    :param n: 节点总数 (有些题目没给 n，可能需要先遍历 adj 计算节点数)
    :param adj: 邻接表，例如 {0: [1], 1: [0, 2], 2: [1]}
    """
    uf = UnionFind(n)

    for u in adj:
        for v in adj[u]:
            # 对每一条边进行合并
            # 并查集内部会处理重复合并（即 union(u, v) 和 union(v, u) 是一样的）
            uf.union(u, v)

    return uf.count

# --- 测试案例 ---
# 5个节点 (0-4)
# 0-1, 1-2 相连 (一组)
# 3-4 相连 (一组)
n_nodes = 5
adj_list = {
    0: [1],
    1: [0, 2],
    2: [1],
    3: [4],
    4: [3]
}

print(f"邻接表连通分量数: {solve_adjacency_list(n_nodes, adj_list)}") # 输出: 2

如果INPUT是邻接矩阵：

def solve_adjacency_matrix(matrix):
    n = len(matrix)
    uf = UnionFind(n)

    # 遍历矩阵
    for i in range(n):
        # j 从 i + 1 开始，只遍历右上三角，避免重复检查 (i, j) 和 (j, i)
        # 同时也跳过了 M[i][i] 这种自环
        for j in range(i + 1, n):
            if matrix[i][j] == 1:
                uf.union(i, j)

    return uf.count

# --- 测试案例 ---
# 3个节点的图：0和1相连，2单独
adj_matrix = [
    [1, 1, 0],
    [1, 1, 0],
    [0, 0, 1]
]
print(f"邻接矩阵连通分量数: {solve_adjacency_matrix(adj_matrix)}") # 输出: 2

.

带权并查集

标准并查集只记录“谁是我的根”。带权并查集在记录父节点的同时，额外维护一个 value (权值) ，表示 “当前节点到父节点的关系” ：

核心思想 ：把节点看作图中的点，边权就是关系。通过 向量加法 （或乘法/异或），我们可以算出任意节点到根节点的总距离。

路径压缩时 ：val[x_to_root] = val[x_to_parent] + val[parent_to_root]。

合并时 ：利用向量三角形法则计算两个根节点之间应该连多少权重的边。

它最适合解决 具有传递性的“数值”或“二元”关系 问题。

区间和 / 差分约束 ：

已知 $A-B=3, B-C=2$，求 $A-C$。
这里“权”就是数值差。

奇偶性 / 分组校验 (LeetCode 886)：

A 和 B 不同组，B 和 C 不同组 $\rightarrow$ A 和 C 同组。
这里“权”是模 2 的加法（$1+1=0$）。

倍数关系 (LeetCode 399)：

A 是 B 的 2 倍，B 是 C 的 3 倍 $\rightarrow$ A 是 C 的 6 倍。
这里“权”是乘法。

扩展域并查集

当节点可能有多种状态（比如：好人/坏人，A类/B类/C类），且我们不知道它具体是哪种时，我们 把所有可能的身份都把它创建出来 。

核心思想 ：既然不知道 $i$ 是敌是友，我就把 $i$ 拆成两个点：i_friend 和 i_enemy。

逻辑连线 ：

如果“$i$ 和 $j$ 是敌人”，我就连接 (i_friend, j_enemy) 和 (i_enemy, j_friend)。
这句话的意思是：如果 $i$ 是好人，那 $j$ 就是坏人；如果 $i$ 是坏人，那 $j$ 就是好人。
这就构成了一个 逻辑蕴含图 。

它最适合解决 状态有限、逻辑互斥 的非数值问题：

敌友关系 / 团伙问题 ：

敌人的敌人是朋友。
拆成：$i_{self}$ (自己), $i_{enemy}$ (敌人)。

食物链 / 循环克制：

A吃B，B吃C，C吃A。
拆成三个域：$i_{self}, i_{eat}, i_{enemy}$。

简单的 2-SAT 问题 ：

条件选择问题，选了 A 就不能选 B。

单源最短路径（SSSP）

单源最短路径（Single-Source Shortest Paths, SSSP）。

最主要的算法包括：（有向无向都可以）

BFS: 针对无权图，$\Theta (V+E)$
Dijkstra: 针对有权图，不能有负权边，$\Theta ((V+E) \log V)$
Bellman-Ford: 针对有权图，可以有负权边，$\Theta (VE)$

单源最短路径包括以下核心概念：

最优子结构
负权边
负权环路
最短路径的表示
Relaxation（松弛操作）

最优子结构

最优子结构：

最短路径的子路径也是最短路径。

证明思路： 使用“剪切-粘贴”（Cut and Paste）反证法。如果子路径不是最短的，那么可以用更短的子路径替换它，从而使得整条路径的总权重更小，这与原路径是“最短”的前提矛盾。

负权边

负权重的边：
有些算法（如 Dijkstra ）要求图中所有边权重非负。
有些算法（如 Bellman-Ford ）允许负权边。
Bellman-Ford算法：
可以处理负权边。
能够检测是否存在从源点可达的负权环路。如果有，它会报告存在；如果没有，它能生成正确结果。

负权环路

正常情况下，由于我们找的是最短路径，因此遇到正权环路的时候肯定是选择避开的。但是如果环路是负权的呢？假如我们进入一个负权环路，我们在里头可以无限转圈，每转一圈总权就会降低一点，于是我们可能无穷无尽地转下去——Dijkstra在这种情况下会崩溃，而Bellman-Ford则能识别出负权环路。

既然正权环路浪费钱，负权环路会导致死循环，那么一条正经的、有限的最短路径里，肯定 不能包含任何环路 。因此，最短路径最多包含 $|V|-1$ 条边。

最短路径的表示

最短路径估计（$v.d$）：
对每个结点 $v$，维护一个属性 $v.d$，记录从源点 $s$ 到 $v$ 的最短路径权重的上界。
初始化时，$s.d = 0$，其他所有结点为 $\infty$。
前驱结点（$v.\pi$）：
记录最短路径树中的父结点。通过反转前驱链，可以重建从 $s$ 到 $v$ 的最短路径。
最短路径树（Shortest-path tree）：
一棵有向子图 $G'=(V', E')$，根结点为 $s$。
包含从 $s$ 可达的所有结点。
树上从 $s$ 到任意结点 $v$ 的唯一简单路径，即为图 $G$ 中 $s$ 到 $v$ 的一条最短路径。
注意： 最短路径不一定是唯一的，因此最短路径树也不一定是唯一的。

Relaxation

松弛（Relaxation） 是众多单源最短路径算法的核心操作。

定义： 检查通过边 $(u, v)$ 是否能找到从 $s$ 到 $v$ 的更短路径。
操作：如果 $v.d > u.d + w(u, v)$，则更新 $v.d = u.d + w(u, v)$，并将 $v$ 的前驱设为 $u$（即 $v.\pi = u$）。

算法区别：

Dijkstra： 对每条边仅松弛一次（基于贪心策略）。
Bellman-Ford： 对每条边松弛 $|V|-1$ 次。

下面是常用在图论证明中的一些性质：

性质名称	核心含义（人话版）	记忆关键点
三角不等式(Triangle Inequality)	抄近道更近	两点之间，直达距离$\le$绕路距离。$\delta(s,v) \le \delta(s,u) + w(u,v)$
上界性质(Upper-bound)	估算值只降不升	我们维护的距离$v.d$一开始是无穷大，随着计算只会变小，永远不会比真实距离更小。一旦降到真实值，就锁死不变了。
非路径性质(No-path)	路不通就是无穷大	只要物理上走不通，距离就是$\infty$。
收敛性质(Convergence)	前一步对，后一步就对	如果$u$的距离算对了，此时松弛边$(u,v)$，那么$v$的距离也会变成正确的。
路径松弛性质(Path-relaxation)	只要顺序对，过程不重要	只要按照路径顺序松弛了边，不管中间穿插了什么其他操作，最终结果一定是对的。
前驱子图性质(Predecessor-subgraph)	拼起来是一棵树	算法结束后，把所有点的“上家”（父结点）连起来，就是一棵以起点为根的树，没有环。

这些性质保证了松弛（Relaxation）操作最终能求出正确答案。

BFS系

对于无权图，BFS可以天然地用来求解SSSP，因为BFS就是一层一层往外扩的。

在无权图中，“最短路径”的定义是 经过的边数最少 。

层级遍历机制： BFS 的核心是从起点开始，一层一层向外扩展。
第 0 层：起点。
第 1 层：起点的所有邻居（距离为 1）。
第 2 层：邻居的邻居（距离为 2）。
保证最短： 因为它是按“层”推进的，所以当你第一次访问到某个节点 $v$ 时，你所经过的路径一定是从起点到 $v$ 的 最少边数 。不可能存在一条更短的路径，否则该节点早在上一层就被访问过了。

对于包含 $V$ 个节点和 $E$ 条边的图：

BFS 的复杂度： $O(V + E)$
这是线性的，也是寻找最短路径理论上的最优解。

双向BFS

如果你的目标是 已知起点和终点 （而不是求从起点到所有点的距离），双向 BFS 会更快。

原理： 同时从起点和终点开始做 BFS，直到两边的搜索范围相遇。
优势： 虽然复杂度量级不变，但搜索空间（访问的节点数）通常会显著减少（从 $b^d$ 减少到 $2 \times b^{d/2}$）。

0-1 BFS

如果图中的边权 不是全为 1，而是只有 0 和 1 两种 ：

普通 BFS 失效。
Dijkstra 可用但稍慢。

最佳选择： 使用 双端队列（Deque） 的 BFS。遇到权值为 0 的边加到队首，权值为 1 的边加到队尾。复杂度仍为 $O(V+E)$。

这里注意，0-1 BFS 是专门用来解决 边权只有 0 或 1 的单源最短路径问题的算法，它本质上是 Dijkstra 的特化版本，但因为在代码长相上和BFS几乎一模一样，所以一般习惯性称呼为0-1 BFS。

核心思想：

若边权为 0 ：从队头加入，下次优先处理
若边权为 1 ：从队尾加入，按普通顺序处理

这个机制保证了我们每次从 deque 的前端取到的，都是当前最短距离的节点（类似 Dijkstra 每次弹出最小距离点）。

Dijkstra系

Dijkstra算法是图论中最经典的算法，也是解决带权重的单源最短路径问题的标准方法。BFS的核心思想是一层一层往外扩，而Dijkstra则在此基础上进行了升级：谁最便宜先走谁。

这里要注意，Dijkstra是单源最短路径SSSP算法，因此其数据结构及变量存储的内容（如下图所示）中的dist代表的是起点到该点的距离。

Dijkstra的核心思想是贪心+松弛：

贪心：总是取出当前已知的距离最近的点（即min-heap中最小点）
松弛：对比当前最小点的邻居已经记录的距离和新算出的距离

使用min-heap的dijkstra算法：

extract-min: 对每个节点都要操作一次，单次操作是O(logV)(堆的高度)，因此是O(VlogV)
decrease-key: 单词插入或更新操作师O(logE)，最多发生E次，所以是O(ElogE)

因为 $E \le V^2$，所以 $\log E \le \log(V^2) = 2 \log V$。因此 $O(\log E)$ 和 $O(\log V)$ 是一个量级。

总复杂度： $O(V \log V + E \log V) = \mathbf{O((V+E) \log V)}$

对于绝大多数算法题和实际应用，图都是稀疏的，E和V是同一数量级，也即$E \ll V^2$。同时，Dijkstra的主要瓶颈是内层循环（decrease-key），是针对边触发的，因此通常简写为：$\mathbf{O(E \log V)}$

Dial算法

当图中的边权都比较小且是正整数的时候，可以用Buckets代替Heap，将Dijkstra的时间复杂度从$O(E + V \log V)$降低到理论上的线性时间$O(E + V)$。

Bellman-Ford系

核心要点：

简单，效率低
可以处理负权边、负权环

可以看下图，如果是Dijkstra算法，一旦确定A->C是3，就不会再更新这条路径。然而，更优的选择是A->B->C，结果是2。这种情况下，就需要使用Bellman-Ford算法了。

1764288003658

Bellman-Ford的核心思想是：

不断尝试更新所有的边，直到所有可能的最短路径都被找到。

我们来看一下Bellman-Ford的算法和过程详解：

BELLMAN-FORD算法

初始化距离：（距离代表的是从起点到该点的距离）
    起点设置为0，所有其他点设置为无穷大
    前驱全部都设置为空

执行V-1轮松弛操作：（这里的循环次数 = 路径允许的最大边数，一般是V-1）
    遍历所有边：
        对于边(u,v)
        计算 u.d + edge
        IF u.d + edge < v.d:
            v.d = u.d + edge
            v.predecessor = u
    如果这一轮遍历没有任何顶点的距离更新，则意味着结果已经收敛，可以提前结束

如果松弛完整进行了V-1次，则需要额外进行一轮松弛：
    遍历所有边，进行松弛操作
    如果有任何顶点被更新：
        存在负权环，即不存在最短路径

所有顶点的数值收敛后，我们便找到了起点到各点的最短路径：起点到任何一点的最短路径就是现在的结果

上面可以看出，外层循环V次，内层循环E次，因此时间复杂度是$V*E$。

我们用下面这个例子来讲解一下Bellman-Ford算法。

1764288813416

注：案例讲解和图片来自于Youtube波波微课。

从图中可以看到，一共有6个顶点，也就是说我们要对每一条边进行5轮松弛。

我们初始化所有的顶点，选择A作为起点，并记录所有的边。

表格中的距离的意思是从源点A出发，走到该点所需要的距离，因此A的距离永远是0。

第一轮

第一轮松弛后，保证了所有只走一步就能找到的最短路径被算出来

...

第四轮

第四轮松弛后，遍历所有的边，结果没有新的更新，结果已经收敛，我们可以省去第五轮，直接结束。同时因为已经收敛，我们也不需要进行第V轮松弛。

1764290032708

我们可以利用前驱来找到任何A到任何一点的具体路径。

这里要注意，Bellman-Ford是单源最短路径SSSP算法，在上面的例子中，我们以A为中心进行计算，则我们得到的结果就是只适用于A的。我们不能用这张表来计算其他的点对之间的距离，除非其他的点正好在A到另一个点的路径上，根据最优子结构性质我们可以找到该子路径。

SPFA算法

SPFA算法的全称是最短路径快速算法（Shortest Path Faster Algorithm）。 目前国际上普遍认为SPFA就是带有队列优化的Bellman-Ford算法，这一算法在随机的稀疏图上表现出色，并且适用于带有负边权的图。然而SPFA在最坏情况的时间复杂度与 Bellman-Ford 算法相同，因此在非负边权的图中，使用堆优化的Dijkstra算法可能优于SPFA。

SPFA的基本思路与 Bellman-Ford 算法相同，即每个节点都被用作用于松弛其相邻节点的备选节点。但相较于 Bellman-Ford 算法，SPFA的先进之处在于它并不盲目地尝试所有节点，而是维护一个备选的节点队列，并且仅有节点被松弛后才会将其放入队列中。整个流程不断重复，直至没有节点可以被松弛。

差分约束系统

例如：机器人执行动作序列，“动作 2 必须在动作 1 发生后的 [2s, 5s] 时间窗口内发生”。

$t_2 - t_1 \geq 2$
$t_2 - t_1 \leq 5$
这种被称为简单时序网络 (Simple Temporal Networks, STN)，其核心求解算法就是基于 Bellman-Ford 或 Floyd-Warshall 的差分约束求解。

一般面试和leetcode中该概念基本不会涉及。但是在实际应用中，差分约束系统是解决调度、布局、时间规划等“约束满足问题”的一个重要方法。如果后续遇到该类主题，我们再深入了解。

全点对最短路径 APSP

All-Pairs Shortest Paths (APSP)，全点对最短路径问题。

我们当然可以用SSSP来求解APSP， 比如对每个节点运行Dijkstra或者对每个节点运行Bellman-Ford。然而这两种方法在求解APSP时都有先天性局限：

Dijkstra循环的时间复杂度是可以接受的，但是无法处理带有负权边的情况。
Bellman-Ford可以处理负权边情况，但时间复杂度是不可忍受的

因此我们还需要学习专门的全点对最短路径算法Floyd-Warshall。

注意，对于只有正权边的情况，Dijkstra通常比Floyd-Warshall更快。

Floyd-Warshall

Floyd-Warshall的本质是动态规划，我们设定一个k，代表可以中转的次数。$k$ 不是指“某一个特定的中间点”，而是指“允许使用的中转节点集合的范围”。$DP[k][i][j]$ 表示“只允许经过节点编号 $1 \dots k$ 作为中间节点的情况下，$i$ 到 $j$ 的最短路径”。

为了高效遍历，我们一般都会设定两个矩阵：

邻接矩阵，记录最短距离
下一跳矩阵，记录下一跳节点

状态转移方程：

\[ dist[i][j] = \min(dist[i][j], \quad dist[i][k] + dist[k][j]) \]

变量含义：

$i$：起点。
$j$：终点。
$k$ (最关键)： 表示当前 允许经过的中转节点集合 （$1 \dots k$）。

如果只需要找到最短距离是多少的话，可以不记录下一跳。记录下一跳可以找到具体的路径。比如说，next[i][j]=10，从i到j的第一跳是10；然后你就可以找next[10][j]，不断寻找直到找到next[j][j]。

Floyd-Warshall可以作用于带有负权边的图。并且的，遍历之后可以进行负权环检测。只需要在三层循环后加一个简单的循环：

has_negative_cycle = False

for i in range(n):
    if dist[i][i] < 0:
        has_negative_cycle = True
        break

意思就是说只要发现任何一个 $dist[i][i] < 0$，就说明图中有负权环。这是因为在算法开始前，我们总是把自己到自己的距离设定为0。假设有一个环：$A \to B \to C \to A$，这个环的边权总和是 $-10$。那么在算法运行过程中，会在尝试更新$A \to A$*的距离时，因为负数小于该值而错误更新，从而实现了负权环的检测。

我们来看一个例子：

1765164748247

以上图为例，我们来看一下Floyd-Warshall算法是如何执行的。

你可以想象图中的节点是飞机场，edge是航线，weight是航行时间。那么Floyd-Warshall的核心思想就是循序渐进地解锁中转站：

先看没有任何中转城市时的情况，记为$D^{(0)}$。
再看可以以A为中转时的情况，记为$D^{(1)}$。
再看可以以A, B为中转时的情况，记为$D^{(2)}$。
再看可以以A, B, C为中转时的情况，记为$D^{(3)}$。

首先来看$D^{(0)}$：

我们把直接相连的记录下来，自己和自己记为0，无法到达的记为$\infty$。然后我们就能得到记录了所有店对之间最小距离的矩阵：

	A	B	C	D
A	0	3	8	$\infty$
B	3	0	-2	$\infty$
C	$\infty$	$\infty$	0	4
D	1	$\infty$	$\infty$	0

接着是$D^{(1)}$：

这里要注意，我们只统计经过A这个中转站的情况，而不是讨论所有经过一个点的情况！换句话说，就是在刚才的D(0)矩阵的基础上，看一下如果能增加一个经过A的选项，其值是否可以改变。

那么很显然，从A出来的这一行不会有改变，到A的这一列也不会有改变。我们在后续的矩阵中标注出那些改变了的值（在本轮运行中，D经过A可以更短地到达B和C，因此数值改变了）

	A	B	C	D
A	0	3	8	$\infty$
B	3	0	-2	$\infty$
C	$\infty$	$\infty$	0	4
D	1	4	9	0

接着是$D^{(2)}$：

本轮次我们将考虑经过中转站A、B的情况：

	A	B	C	D
A	0	3	1	$\infty$
B	3	0	-2	$\infty$
C	$\infty$	$\infty$	0	4
D	1	4	2	0

接着是$D^{(3)}$：

本轮次我们考虑经过中转站A, B, C的情况：

	A	B	C	D
A	0	3	1	5
B	3	0	-2	2
C	$\infty$	$\infty$	0	4
D	1	4	2	0

最后是$D^{(4)}$，这一轮将是最后考虑的一轮，因为我们将考虑全部点都可以中转的情况，也就是在D(3)的基础上增加经过D的情况：

	A	B	C	D
A	0	3	1	5
B	3	0	-2	2
C	5	8	0	4
D	1	4	2	0

至此，所有点对的最短距离就被找到了。

这里要注意的是，Floyd-Warshall可以用在有负权边的图上，但不能用在有负权环的图上。更准确的说，任何最短路径算法都无法在有负权环的图上成功运行，因为在负权环上会陷入死循环。

对于一个有N个节点的图来说，最多执行N+1次运算，我们就可以得到最终的矩阵结果。上图的最终结果如下：

\[ \begin{bmatrix} 0 & 3 & 1 & 5 \\ 3 & 0 & -2 & 2 \\ 5 & 8 & 0 & 4 \\ 1 & 4 & 2 & 0 \end{bmatrix} \]

我们可以检查最终结果对角线：如果对角线都是0，那么就没有负权环；如果对角线上有任何一个小于0的存在，那么就存在负权环，且这样的负数点就是负权环的一部分或者可以通过负权环到达该点。

值得注意的是，无向图的负权边就是负权环，因为你可以来回在这一条边上往返，或者可以看做是一对往返的负权边形成的负权环。

除了上述Distance Matrix外，我们一般还会维护另外一个Predecessor Matrix，记作$\Pi^{(k)}$。前驱矩阵就是在一个节点数值被更新时，记录该节点新的前驱节点，用来还原最短路径。具体来说，当你发现一条经过中转点 $k$ 的路径比原来的路径更短时，你不仅要更新距离矩阵 $D$，还要更新前驱矩阵 $\Pi$：$\pi_{ij}^{(k)} = \pi_{kj}^{(k-1)}$，这个的意思就是说，因为走 $i \to k \to j$ 更近，所以新的前驱 $\pi_{ij}$ 就变成了“从 $k$ 到 $j$ 路径上的前驱”。

在前驱矩阵中，对于自己到自己、无法到达的点等，一般用NIL来代表无前驱。

Transitive Closure

有向图的传递闭包（Transitive Closure） 实则是Floyd-Warshall的一个简化变种，在很多实际应用中（比如LeetCode.1462 Course Schedule IV）非常好用。它的核心问题不再是“A 到 B 有多远（距离）”，而是 “A 能不能走到 B（连通性）”

普通 Floyd: 关心具体的数字（比如 10公里）。
传递闭包: 只关心 True (能到) 或者 False (不能到) 。即 1 或 0。

计算机进行布尔运算是很快的，所以在特定场景下传递闭包很好用。

传递闭包算法
# T 是一个 N x N 的矩阵
# T[i][j] = 1 表示 i 到 j 有边，= 0 表示无边

# 核心：必须先把中间点 k 放在最外层
for k from 1 to N:
    for i from 1 to N:
        for j from 1 to N:
            # 逻辑：原路通，或者 (经过 k 中转也能通)
            # 对应公式：T[i][j] = T[i][j] OR (T[i][k] AND T[k][j])
            if T[i][k] == 1 and T[k][j] == 1:
                T[i][j] = 1

简单来说就是：如果你能从i到k，也能从k到j，那么你就能从i到j。

Johnson算法

用于稀疏图的Johnson算法。

Heurisitc Search

A*

A*在形式上是Dijkstra的变体，但是在思想上引入了启发函数的概念，成为了一个新的体系。

D*

IDA*

网络流

最大流-最小割定理

最大流

最大流问题 (Maximum Flow Problem) 是图论和网络流理论中一个非常经典且重要的优化问题。

简单来说，它的核心目标是：在一个由管道（边）和节点组成的网络中，计算从起点（源点）到终点（汇点）所能传输的 最大物质量 。

举例来说：

1763864360796

（图来自Youtube：Shusen Wang）

在上图中：

黑字代表容量
红字代表流量

最小割

最小割问题（Minimum Cut Problem） 和最大流问题在数学上是同一个问题的两个面或者说对偶问题（Dual Problem）：

最大流关注如何让流量最大
最小割关注系统的瓶颈在哪里

举例来说，在交通中，我们经常会遇到这样的情况：

你家门口的路很宽（容量大），公司楼下的路也很宽（容量大），但是连接这两个区域的只有一座跨江大桥，桥上只有两车道。

在这个场景下：

那座桥就是图论中的 最小割（Min-Cut） 。
无论你家门口的路修得再宽，整个城市早高峰从“居住区”到“CBD”的最大车流量， 永远受限于那座桥的通行能力 。

这就是最大流问题告诉我们的道理：系统的上限取决于最窄的那一段。

然而，有一个Braess悖论很有意思：有时候多修一条路反而会让交通更加拥堵，因为每个司机都想自己最快到达，从而所有人都会开到主干道上，从而把主干道彻底堵死。

不过在最大流模型中，多修路永远不会减少最大流量。

最大流-最小割定理” (Max-Flow Min-Cut Theorem) ：

在一个网络中，从源点到汇点的最大流量，永远等于该网络的最小割的容量。

举例来说，你想知道一个木桶（网络）最多能装多少水（最大流）？你不需要去算每一滴水的流向，你只需要找到 最短的那块木板 （最小割）。最短木板的高度，就是木桶的容量极限。

增广路径

最小费用最大流

欧拉回路

欧拉回路（Eulerian Circuit） 就是对于一个图，找到能遍历图并且每条边恰巧只走了一次的环路。欧拉回路可以多次访问同一个顶点。

在图论中， 欧拉路径（Eulerian path） 是经过图中每条边恰好一次的路径， 欧拉回路（Eulerian circuit） 是经过图中每条边恰好一次的回路。如果一个图中存在欧拉回路，则这个图被称为 欧拉图（Eulerian graph） ；如果一个图中不存在欧拉回路但是存在欧拉路径，则这个图被称为 半欧拉图（semi-Eulerian graph） 。

这里要注意，我们讨论欧拉回路的时候，默认讨论的是有限的连通图。

欧拉回路判定

有限连通图

有限的意思是图是确定的、有非无限数量个点和边。

在无向图中，如果图中任意两点之间都有一条路径相连，那么这个图就是连通图（Connected Graph）。

在有向图中，由于能不能走过去和能不能走回来时两码事，所以我们必须区分：

强连通图（Strong Connected Graph）：图中任意两个节点都可以双性可达
弱连通图（Weakly Connected Graph）：如果忽略所有边的方向，该图可转变为连通的无向图，那么这个图就是弱连通图。

无向图欧拉回路

对于一个无向图，我们其实可以很容易想到：

如果任何一个顶点连接着奇数个边，那么该图不可能有欧拉回路。

因为为了形成一个闭环（欧拉回路要从起点出发再走回终点），当你沿着一条边走到一个顶点的时候，你必须还能沿着另一条边走出这个顶点，否则你会在这个点停下来。而对于起点，出去需要一条，回来还需要一条，因此也必须是偶数个。

因此，一个无向图如果有欧拉回路，那么其充要条件是：

所有顶点的度数都是偶数。
所有度数大于0的顶点，必须属于同一个连通分量。

有向图欧拉回路

对于一个有向图：

如果任何一个顶点的入度不等于出度，那么该图不可能有欧拉回路。

因为任何一个点（包括起点本身），你访问多少次，就要离开多少次。

因此，一个有向图如果有欧拉回路，那么其充要条件是：

所有顶点的入度等于出度。
所有的边必须属于同一个弱连通分量。

Fleury算法

Fleury算法（避桥法）是一个直观但是非常低效的解法。

Hierholzer算法

Hierholzer算法是求欧拉回路的最佳实践算法（无论是无向图还是有向图都可以）。

哈密顿回路

哈密顿回路（Hamiltonian Cycle） 和欧拉回路不同：每个顶点必须去一次并且只能去一次。看起来和欧拉回路很像，但是难度却千差万别。欧拉回路属于P类问题，而哈密顿回路属于NP类问题。以哈密顿回路为基础的旅行商问题至今仍未有最优解。

下图展示了欧拉回路和哈密顿回路的不同：

1763841755675

哈密顿回路的定义是：

对于一个图，可以不重复、不遗漏地经过每一个顶点，最终回到起点。除了起点和终点外，每一个顶点恰好经过一次。

对于哈密顿回路，不要求经过所有的边，因此很多边可以是空的。

与欧拉回路不同，哈密顿回路至今没有充要条件。

无向图哈密顿回路

有向图哈密顿回路

旅行商问题

旅行商问题（Traveling Salesman Problem, TSP） 是哈密顿回路的升级版，是图论中最著名的问题之一。旅行商问题属于NP-Hard。

旅行商问题如下：

在一个带权图中，找出一个哈密顿回路，使得所有边的权重之和最小。

由于我们需要找到所有的哈密顿回路，然后在一堆哈密顿回路中比较总费用，因而当一个图的顶点数量达到20个以上时，暴力算法就完全无法执行了（哪怕用状态压缩DP也不可行）。

解决TSP一般用近似解法或者启发式搜索，比如：

模拟退火
遗传算法
蚁群算法

这些算法并不能保证找到最好的路，但是能在很短的时间内找到一条足够好的路。对于几千个城市的TSP，目前只能用这种方法。

二分图

二分图（Bipartite Graph） 是一种特殊的图，它的核心概念是“非黑即白”的阵营划分。

在一个二分图中，所有的顶点都可以被完美地分在两个独立的集合，并且满足：

线只能在两个集合之间连接
同一个集合内部绝对不能有连线

举个例子，在相亲中，左边阵营是男生，右边阵营是女生，连线表示两个人愿意约会。

1763865115644

那么如何判定一个图是否是二分图呢？

有一个著名的染色法判定标准：

如果你能用 两种颜色 （比如红和蓝）给图里所有的点染色，使得 每一条线连接的两个点颜色都不同 （即红连蓝，蓝连红，绝没有红连红或蓝连蓝），那它就是二分图。

注意： 如果一个图里包含“奇数长度的环”（比如 3 个点互相连成一个三角形），它就绝对不是二分图，因为你没法只用 2 种颜色把它们区分开。

如果我们希望能有尽可能多的配对，比如上面的相亲中我们希望尽可能多的人都能找到对象，那么这类问题就是在寻找二分图的最大匹配（Maximum Matching）。

在现实中，最大匹配当然不是用在相亲配对上。实际应用中更多用在人员调度、服务器负载等问题上。

无权二分图中的最大匹配

Maximum-Cardinality Bipartite Matching (MCBM)

有权二分图中的最大匹配

Maximum-Weight Bipartite Matching

匈牙利算法

Hungarian Algorithm

稳定婚配问题

Gale–Shapley Algorithm

附录：经典练习

应用例题标注含义：

LC: LeetCode
CS: 学校课程或非在线测评习题
CE: CSES
LG: 洛谷
PJ: 北京大学在线测评
SF: 自制问题

普通BFS

普通DFS

[LC] Find Eventual Safe States

LeetCode 802. Find Eventual Safe States

注：这道题一般第一印象是用DFS解，但其实也可以用BFS解。

这道题简单描述就是：

给一个有向图，每个点都有若干有向边指向别的点。
如果从某个点出发，能走到某个环上，那么这个点就是unsafe的
如果从某个点出发，一定能走到没有出边的点，那么这个点就是safe的；没有出边的点叫做terminal node

这道题使用常规的DFS遍历就可以解决，并且常规DFS遍历是最佳实践。其关键点在于：

在DFS过程中，如果遇到了一个visiting状态的vertex，那么说明当前递归栈中涉及到的所有点都是unsafe的，我们把当前递归栈中涉及到的点标记为unsafe
在DFS过程中如果一路走到头都没有遇到unsafe的点，直接走到了terminal node，且这个点的其他邻居也是safe的，那么这个点就是安全的。

换句话说，我们只需要维护两个状态：visit状态和safe状态，然后在DFS过程中，对每一个vertex，他只需要做如下判断：

如果一个点没有邻居，那么这个点是safe的
如果邻居中有visiting状态的点，那么该vertex就是unsafe状态的
如果邻居中有unsafe状态的点，那么该vertex就是unsafe状态的
如果一个点的所有邻居都是safe的，那么这个点就是safe的

拓扑排序

[LC] Course Schedule

LeetCode210. Course Schedule II

这是一道非常经典的拓扑排序题，用BFS（Khan）或者DFS都可以解决。在课程关系中：

{课程:先修课}代表Edge
课程代表Vertex

然后要注意：

使用BFS的话所有vertex都要考虑到，即孤点（indegree为0）也要被算在内
使用DFS的话要考虑环的检测，必须用三状态管理DFS过程

[LC] Alien Dictionary

LeetCode.

这道题也非常经典，比Course Schedule稍微难一点，但本质还是拓扑排序。

题目简单来说如下：

给定一系列按照外星语字典序排好的单词，判断这个外星语字母顺序。

例如：

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"
---
Input: words = ["z","x"]
Output: "zx"
---
Input: words = ["z","x","z"]
Output: ""
Explanation: The order is invalid, so return ""

解题的要点是通过单词之间的顺序，推导出字母之间的大小关系。

我们可以把每个字母当做图中的一个vertex，{前面的字母a->后面的字母b}代表的就是有向边{a->b}。

思路如下：

Alien Dictionary

INPUT: 若干个已经按照外星语字典序排好的单词

1、从INPUT中推导出字母间的关系
（1）推导出字母间的相对先后关系
（2）检查是否有非法关系，如果有，则直接结束
        这里检查的非法关系是前缀合法性
        比如 abc, ab 是绝对不可能按照字典序拍出来的

2、建图
我们直接把所有的相对关系转换为具体的边，这是本道题建图的核心思想要点

3、对图做TOPO SORT
※不要忘记检查是否有环，如果用Khan就做完TOPO SORT检查，如果用DFS就在做的时候检查visiting

OUTPUT：拓扑排序结果

我们可以看到，这道题非常反直觉：我们不需要考虑一个具体的图，因为我们的目标是找到最终的TOPO SORT，所以中间建的图长什么样子并不重要。因此，只要一个点在另一个点的前面，我们就可以建立一条从前面的点指向后面的点的有向边。

换句话说，不同的例子所构建出来的图长得可能不一样，但是只要是同一个外星语字典序做出来的合法例子，那么通过该合法例子做出来的图无论长什么样，最终根据这个图所做的拓扑排序总是一样的。

最终算法如下：

Alien Dictionary (DFS)

INPUT: words

1. According to INPUT, make a relationship list
chars: [pre_char -> char]
遍历words:
    一对一对比较，前面的叫word1，后面的叫word2
    if word1比word2长，且word1以word2开头：
        return ""
    遍历word1：
        如果找到第一个word1中和word2中不一样的字符：
            记录 [word1的字符 -> word2的字符]
            立刻结束循环，因为只有第一个不一样的字符有字典序意义

2. 记录所有vertex并设为unvisited
设立一个记录所有vertex的set，比如叫做vertexes
遍历word，把word中的所有字母记录到vertexes
将vertexes中的所有顶点设为"unvisited"

3. 建图
graph = 邻接表
遍历chars:
    记录到graph中

4. Define DFS
...此处省略...

5. RUN DFS & Check CYCLE
※ 一定要记得RUN DFS
※ 一定要记得判断是否有环

6. Return Result
OUTPUT: 根据题目要求返回对应的内容

在解题过程中，我们主要关注两个非法检查点：

记录所有相对关系的时候，是否出现了word1比word2长且以word2开头的情况。在python中可以用word1.startswith(word2)来快速判断。
最后检查是否有环，其实就是在检查是否出现了INPUT中错误关系的情况，比如 ["z","x","z"]这种。

[CS] Path Counting

这道题是学校课程作业的一道题，是经典的DAG动态规划练习。题目如下：

You are given a DAG G with V vertices and E edges, a source node s and a destination node t. Design a linear time algorithm in V and E that finds the number of distinct paths from s to t.

在拓扑排序后，我们会得到一个排序列表。

并查集

[LC] Number of Provinces

LeetCode 547. Number of Provinces

这是一道非常经典的标准并查集题，考察find和union。

（有空的话可以做一做）

[LC] Redundant Connection

LeetCode 684. Redundant Connection

这是另一道经典的标准并查集题。

（有空的话可以做一做）

[LC] Accounts Merge

LeetCode 721 Accounts Merge

经典的并查集题

（有空的话可以做一做）

[LG] 食物链

洛谷 P2024. 食物链

这是一道经典的扩展域并查集练习题。

（有空的话可以做一做）

SSSP - BFS

主要收录BFS

[LC] Rotting Oranges

LeetCode.994 Rotting Oranges

[LC] 网格中的最短路径

LeetCode.1293 Shortest Path in a Grid with Obstacles Elimination

[LC] Bus Routes

LeetCode.815 Bus Routes

[LC] 访问所有点

LeetCode.847 Shortest Path Visiting All Nodes

[LC] 收集钥匙

LeetCode.864 Shortest Path to Get All Keys

SSSP - Dijkstra

主要收录Dijkstra

[LC] 网络延迟时间

LeetCode.743 Network Delay Time

有 $N$ 个网络节点，给定一组带权有向边，求信号从 $K$ 发出，传遍所有节点需要多久。标准的堆优化 Dijkstra 模板题。

[LC] Path with Minimum Effort

LeetCode.1631 Path with Minimum Effort

[LC] Swim in Rising Water

LeetCode.778

[LC] 概率最大的路径

LeetCode.1514

[LC] 到达目的地的方案数

LeetCode.1976

[CS] Meet-in-the-middle

题目：一个图G，源点s，终点p，若干个m属于M，求经过m的最短路径。

这道题最直观的解法是从s出发做dijkstra，然后从p出发做反向图的dijkstra，然后从所有的m中找到最短的路径。

这道题还有一个引申出来的话题，就是做一遍dijkstra解决的方案：分层构图。

我们把这个图复制一份，作为第二层，将第一层的m各自指向第二层的复制m，然后将起点设为第一层的s，将终点设为第二层的p，那么我们只需要一次dijkstra即可找到最短的、经过m的路径。

[LC] 1129

LeetCode.1129 Shortest Path with Alternating Colors

[LC] 2203

LeetCode.2203 Minimum Weighted Subgraph with the required paths

[LG] 飞行路线

洛谷P4568. JLOI2011. 飞行路线

SSSP - Bellman-Ford

主要收录非BFS/Dijkstra的单源最短路径题

[LC] K站中转

LeetCode.787 Cheapest Flights Within K Stops

Bellman-Ford解法

这道题是leetcode中几乎唯一一道可以用Bellman-Ford来解的题。不过注意，这道题中没有负权边。

这道题要求在n个城市中，找到最多不超过k次中转的情况。这里有一个非常重要的点，也是这道题第一个非常经典的地方所在：

k次中转意味着最多走k+1条边，因为直飞意味着不需要中转
Bellman-Ford的外层循环次数 = 路径允许的最大边数，在这里是k+1而不是v-1

然后这道题还有第二个非常经典的地方所在：

如果我们松弛的时候直接把distance的值导入进去，会导致错误，比如把本来要中转一次的路程错误更新为可以直达的
因此每轮次的松弛时，我们都不能直接修改原始distance，必须备份，然后在一整轮松弛后再复原
简单来说，就是在松弛的时候读旧写新

然而，这道题最佳实践是BFS/SPFA变种解法。 Bellman-Ford可以稳定在$O(K \times E)$，然而，SPFA算法却可以保证最坏$O(K \times E)$并且让平均情况远小于此。在稀疏图（边不多的图）中，优势巨大。

BFS/SPFA变种解法

其实这个解法更符合直觉。我们从起点开始，层层推进，那么：

第一层自然就是从起点可以直飞到达的点
第二层自然就是所有中转一次就能到达的点
...
第K+1层就是中转K次能到达的点

该解法相比于Bellman-Ford的暴力松弛，更加符合我们对中转定义的直觉性建模。

同样的，对于BFS/SPFA解法，依然要注意几个重要的点：

queue中要存放到达当前节点时的花费
到达某一层的某一点时，更新邻居的时候用到达这一层时的数据（也就是上面说的要存放的到达当前节点时的花费）
只有更有价值的路径被发现时才需要将新的点加入queue

简单来说就是不能信任全局数组，我们来看这样一个例子：

假设我们要从 北京(src) 去 纽约(dst) ，限制 K=1 (最多转机 1 次) 。

现在有两条路能到中间站 东京(u) ：

路 A（超便宜，但是慢） ：北京 -> 昆明 -> 上海 -> ... -> 东京。

这条路只要 500块 ，但是中转了 10次 。
此时全局表记录：distance[东京] = 500。

路 B（超贵，但是快） ：北京 -> 东京。

这条路要 2000块 ，但是 0次中转（直飞）。
因为 2000 > 500，所以全局表 distance[东京] 依然保持 500 。

关键时刻来了！ 现在我们的 BFS 队列正在处理 路 B (直飞) 这一层（也就是第 1 层）。

我们从队列里拿出了东京。
我们要计算东京的下一站：纽约（票价 1000）。

如果你直接用全局数组 distance[东京]：

计算公式：distance[东京] + 1000。
带入数值：500 + 1000 = 1500。
结果：你算出北京->东京->纽约只要 1500块。

这里出了什么大问题？

你正在处理的是 第 1 层 （直飞的那条线）。
但是你计算价格时，用的却是那条 中转了 10 次 的路 A 的价格（500块）。
后果：你拼凑出了一条 “价格 500 + 1000，且只中转了 1 次” 的神仙路径。
但实际上，那条 500 块的路早就把中转次数用光了，根本没资格再飞纽约！你利用全局数组，把“未来的低价”穿越到了“现在的步数”里。

为了防止这种“张冠李戴”，我们需要给队列里的每个节点挂一个“专属价格牌”。

当 BFS 处理 路 B (直飞) 这一层时：
队列里存的是：（东京，2000）。
我们从队列拿出来计算下一站：
2000 + 1000 = 3000。
这个 3000 虽然贵，但是它诚实。它确实是 1 次中转能走出来的结果。

因此，在有步数限制（K）的 BFS 中：

Queue 是用来记录 “当前这一步” 的状态的。
Distance 数组 是用来 “剪枝” 的（防止走回头路，或者防止走比以前更贵的路）。

所以：

算数的时候 ：用 Queue 里的数（保证步数合法）。
比较的时候 ：和 Distance 里的数比（保证价格更优）。

这一点是BFS/SPFA变种解法中最难想明白的一点，比较绕。

要点总结：

我们必须根据当下路径的距离值+到邻居的值 VS 邻居的全局值，来判断是否要更新邻居的值。
只有邻居优于全局值时，我们才把邻居放到queue中。如果不在这里剪枝，程序会爆炸。

MST 最小生成树

[LC] 连接城市道路

LeetCode 1135. Connecting Cities with Minimum Cost

MST裸题（模板题），用Prim/Kruskal直接实现。

(有空可以做一下)

[CS] Road Repair

市政想修路，修路费用已经标在图中了。其中：

蓝色边表示有水管，修路费用可能暴涨
黑色边就是固定价格

题目让我们判断一个图如果不用蓝色边去修，结果能否保持和含有蓝色边的情况下的最小可能花费持平。

以下图为例：

1763945361653

上图中：

左图使用蓝色边和不使用蓝色边的MST是一样的，所以答案是TRUE
右图中如果不使用蓝色边MST会增加，所以答案是FALSE

解：

这道题用Kruskal非常好解，我们可以增加一个属性，把蓝色边设为1，把黑色边设为0。算法如下：

ROAD REPAIR SOLUTION

增加一个属性：Color, 如果是黑边Color是0，如果是蓝边Color是1

edge = (weight, color, u, v)
将所有edge放在列表edges中
对edges排序，按照第一顺位优先、第二顺位次之的顺序排序

然后用Kruskal算法
遍历edges：
    如果u和v不在一个集合中：
        合并u和v的集合
        如果color==1:
            return FALSE
return TRUE

这道题我也用python代码实现了一下，发现在实际使用中kruskal非常简洁：

class judgeOptimal:
    def __init__(self, raw_edges):
        self.edges = self.make_edges(raw_edges)
        self.parent = {}

    def make_edges(self, raw_edges):
        # edges = (weight, color, u, v) # 黑色在前
        edges = []
        for w, u, v, t in raw_edges:
            type = 0 if t == 'black' else 1
            edges.append((w, type, u, v))
        edges.sort()
        return edges

    def find(self, node):
        if node not in self.parent:
            self.parent[node] = node
        if self.parent[node] != node:
            self.parent[node] = self.find(self.parent[node])
        return self.parent[node]

    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)

        if root_a != root_b:
            self.parent[root_a] = root_b
            return True

        return False

    def main(self):
        for w, p, u, v in self.edges:
            if self.union(u, v):
                if p == 1:
                    return False
        return True


# ----------------------------------
if __name__ == "__main__":
    # raw_edges = (weight, u, v, type)

    # 图一的数据
    raw_edges1 = [
        (0.25, 'F', 'G', 'black'),
        (1,    'D', 'E', 'black'),
        (2,    'B', 'D', 'black'),
        (2.75, 'B', 'C', 'black'),
        (3.5,  'D', 'G', 'black'),
        (4,    'B', 'E', 'blue'),   # 蓝色边
        (4,    'C', 'F', 'blue'),   # 蓝色边
        (4.5,  'A', 'D', 'black'),
        (5,    'A', 'B', 'black'),
        (7,    'C', 'E', 'black')
    ]
    print(judgeOptimal(raw_edges1).main())


    # 图 2 (右图) 的数据
    raw_edges2 = [
        (4,    'A', 'B', 'blue'),   # 标价 >= 4
        (4,    'A', 'D', 'black'),
        (3,    'B', 'D', 'black'),
        (2,    'B', 'E', 'black'),
        (2,    'D', 'E', 'blue'),   # 标价 >= 2
        (5,    'B', 'C', 'black'),
        (1,    'C', 'E', 'black')
    ]
    print(judgeOptimal(raw_edges2).main())

可以把这道题作为kruskal的教学题来做。

[PJ] 道路维修

POJ 北京大学在线评测. Constructing Roads

MST基础题，需要稍微预处理一下。

这道题和普通MST的区别在于：有些路已经修好了。

(有空可以做一下)

[LC] Min Cost to Connect All Points

LeetCode 1584. Min Cost to Connect All Points

稠密图处理。

题目没有直接给边，而是给了坐标，两点之间的边权是曼哈顿距离。这意味着这是一个完全图（稠密图），用Prim更优。

(有空可以做一下)

[LC] 供水问题

LeetCode 1168. Optimize Water Distribution in a Village

这是一个非常经典且优雅的建模技巧。题目难点在于每个点有两种选择：要么自己挖井（点权），要么铺水管（边权）。标准的 MST 只能处理边权。

破题思路： 引入一个虚拟节点 0 （水源中心）。

如果房子 $i$ 挖井，花费 $W_i$，我们可以将其等价为连接边 $(0, i)$，权重为 $W_i$。
如果房子 $i$ 和 $j$ 铺管，花费 $P_{ij}$，则是普通边 $(i, j)$。

这样问题就转化为：在包含虚拟节点 $0$ 的 $N+1$ 个点中求最小生成树。

(有空可以做一下)

[LG] 货车运输

洛谷 P1967. 货车运输

MST + LCA (最近公共祖先) / 树上倍增。这是典型的 NOIP/提高组级别题目，综合性最强。

(有空可以做一下)

求割/求桥

[LC] Critical Connections in a Network

原题：Leetcode1192: Critical Connections in a Network

我们来看一个Tarjan的实际应用题。

1763499215965

在上图中，我们可以看到，如果把网络节点1和3之间的通路断掉，3就无法连接到网络中了，因此我们说1-3的连接是Critical的，也就是不可或缺的。这就是我们在上面Tarjan算法中提到的求桥。

给定一个包含n个节点的网络以及网络中所有的点点连接关系，比如：

n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]

返回所有的Critical Connections，也就是找到所有的桥。

我们来试着把整个思路写下来：

思路：
1、构建图

随便找一个起点，就connections的第一对吧：（题目保证图是连通的）
start = connections[0][0]

然后根据connections把图构建出来，这里注意无向图的正反都要构建：
for u, v in connections:
    graph[u].add(v)
    graph[v].add(u)

2、创建list：

dfn，记录dfn值
low，记录low值
bridge，记录桥

3、从start开始，进行DFS遍历

def dfs(u, parent):
    将time+1
    dfn[u] = low[u] = time

    访问u的每个邻居v：
        如果v是u的父节点，则忽略
        如果dfn[v]==-1，则v还没有访问过，我们沿着树边u->v往下走：
            dfs(v, u)
            递归结束后，更新u的low值：low[u] = min(low[u], low[v])
            如果low[v] > dfn[u]，则(u, v)是桥，加入bridge list
        ELSE:
            (u,v)是回边，更新low[u]=min(low[u],dfn[v])

这里要注意这道题本身是保证图都连通，如果图不一定连通，我们需要对每一个连通分量做一次DFS。在实践中，我们不需要找连通分量，只要把所有的点扫一遍，如果一个点没被访问过那么久从那一个点开始DFS，开一颗新的DFS树就行了。

SCC 强连通分量

[CE] Coin Collector

CSES Problem Set - Coin Collector

有 $n$ 个房间（节点）和 $m$ 条单向隧道（有向边） 的系统，每个房间 $i$ 有 $k_i$ 个金币。你可以自由选择起点和终点，目标是找到一条路径，使得路径上所有房间的金币总数最大。每个房间的金币只计算一次。

这道题的本质就是找到一条最大和的路径，思路如下：

先找到所有的SCC，将每个SCC视为一个新的节点，获得一张DAG
在DAG上寻找最大和路径

因此这道题本质上是两道题：

用Kosaraju/Tarjan求SCC
DAG上的DP

INPUT:

n m | number of rooms (n), number of tunnels (m)
.... | the number of coins in each room, romm number start from 1
a1, b1
a2, b2
a3, b3
...    | a -> b

Example:

Input:
4 4
4 5 2 7
1 2
2 1
1 3
2 4

Output:
16

.

算法如下：

INPUT: G, GT

1. Kosaraju算法求SCC
进行第一遍DFS，计算完成时间，得到result列表
REVERSE result
遍历result，进行第二遍DFS，得到：
    scc_count DAG节点数
    scc_id 映射
    scc_weights 列表

2. 构建凝结图DAG
遍历原图中的所有边
构建DAG边
去重

3. DAG上的最大和路径DP
...(此处略)

.

	A	B	C	D
A	0	3	8	\(\infty\)
B	3	0	-2	\(\infty\)
C	\(\infty\)	\(\infty\)	0	4
D	1	\(\infty\)	\(\infty\)	0

	A	B	C	D
A	0	3	8	\(\infty\)
B	3	0	-2	\(\infty\)
C	\(\infty\)	\(\infty\)	0	4
D	1	4	9	0

	A	B	C	D
A	0	3	1	\(\infty\)
B	3	0	-2	\(\infty\)
C	\(\infty\)	\(\infty\)	0	4
D	1	4	2	0

初始点	DFS 路径	完成时间 f[v]
A	A → E → C → D → A	\(f[D]=6, f[C]=7, f[E]=8, f[A]=9\)
B	B → F → G → B	\(f[G]=17, f[F]=18, f[B]=19\)

阶段	任务目标	算法工具	复杂度
I. SCC 求解	找出原图\(G\)的所有 SCC 并计算它们的总权重。	Kosaraju 算法或 Tarjan 算法	\(O(N+M)\)
II. DAG 构建	基于 SCC 之间的连接关系，构建凝结图\(G'\)。	遍历\(G\)的所有边	\(O(N+M)\)
III. 路径求解	在点带权重的 DAG\(G'\)上寻找最大和路径。	拓扑排序 + 动态规划 (DP)	\(O(N_{SCC} + M_{DAG}) \le O(N+M)\)

性质名称	核心含义（人话版）	记忆关键点
三角不等式(Triangle Inequality)	抄近道更近	两点之间，直达距离\(\le\)绕路距离。\(\delta(s,v) \le \delta(s,u) + w(u,v)\)
上界性质(Upper-bound)	估算值只降不升	我们维护的距离\(v.d\)一开始是无穷大，随着计算只会变小，永远不会比真实距离更小。一旦降到真实值，就锁死不变了。
非路径性质(No-path)	路不通就是无穷大	只要物理上走不通，距离就是\(\infty\)。
收敛性质(Convergence)	前一步对，后一步就对	如果\(u\)的距离算对了，此时松弛边\((u,v)\)，那么\(v\)的距离也会变成正确的。
路径松弛性质(Path-relaxation)	只要顺序对，过程不重要	只要按照路径顺序松弛了边，不管中间穿插了什么其他操作，最终结果一定是对的。
前驱子图性质(Predecessor-subgraph)	拼起来是一棵树	算法结束后，把所有点的“上家”（父结点）连起来，就是一棵以起点为根的树，没有环。