图论算法从入门到放下

agile Posted on Jul 14 2023

数据结构与算法 yukiyama

---
title: 图论算法从入门到放下
tags:
  - 图论算法
  - 算法与数据结构
  - 最短路径
  - 最大流
  - 最小生成树
  - bfs
  - dfs
  - 拓扑排序
  - Dijkstra
  - Beallman-Ford
  - SPFA
  - Floyd-Warshall
categories: 算法与数据结构
description: >-
  近六万字全面细致地讲解 bfs/dfs、拓扑排序、最短路、最小生成树、最大流，包括不仅限于给出每个专题内容的不同的常见算法 (如在最短路会讲解 DAG
  SSSP, Dijkstra, Bellman-Ford, SPFA, Floyd-Warshall
  等算法)，每一个算法的每一步操作的细节、算法正确性证明、复杂度证明以及完整的可应用的实现代码。
cover: >-
  https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/site_img/posts/algorithms/graph-bg.png
katex: true
abbrlink: graph
keywords:
top_img:
comments:
---

# 图论算法，拿得起放得下

> - 可在作者的 [github仓库](https://github.com/iyukiyama/leetcode-posts) 中获取本文和其他文章的 markdown 源文件及相关代码。
>
> - 欢迎评论或仓库 PR 指出文章错漏或与我讨论相关问题，我将长期维护所有文章。
> - 所有文章均用 Typora 完成写作，可使用 Typora 打开文章 md 文件，以获得最佳阅读体验。

⚠️ ⚠️ ⚠️ **本文巨巨巨长，正文近六万字 (不含题解)，尽最大努力全面细致地讲解 bfs/dfs、拓扑排序、最短路、最小生成树、最大流，包括不仅限于给出每个专题内容的不同的常见算法 (如在最短路会讲解 DAG SSSP, Dijkstra, Bellman-Ford, SPFA, Floyd-Warshall 等算法)，每一个算法的每一步操作的细节、算法正确性证明、复杂度证明以及完整的可应用的实现代码。全面、细致、系统、准确是本文的追求。**

❗️ **【NEW】** ❗️

- 9-15:  [红黑树从入门到看开](https://leetcode.cn/circle/discuss/SwgIJV/)

***

> $keywords$:
>
> 图的基本概念 / 邻接矩阵 / 邻接表 / 链式向前星 / $bfs$ / $dfs$ / 无向图连通性 / 并查集 / 无向图判圈 / 有向图判圈 / $Kahn$ 拓扑排序 / $Tarjan$ 拓扑排序 / 拓扑排序判圈 / 无权单源最短路径 / 带权单源最短路径 / $Dijkstra$ / DAG 单源最短路径 / 负边图 / 有圈图 / $Bellman-Ford$ / $SPFA$ / 带权全源最短路径 / $Floyd-Warshall$ / 最小生成树 / $Prim$ / $Kruskal$ / 网络流 / 增广路径 / 饱和边 / 最大流最小割定理 / $Ford-Fulkerson$ / $Edmonds-Karp$ / $Dinic$

这是 yuki 最近一段时间学习图论的总结，发出来跟大家分享 **亿点点** 🤏心得。写这篇文章的契机是前段时间看 Weiss 那本 「数算Java描述」，看着看着发现到图论那章作者就只提供伪代码了 (之前的章节会提供完整的可运行代码)，而且感觉 Weiss 在那一章里什么都提一点，但匆匆抛出几个结论就跑路，整章看下来比较难受。找了好多资料，包括力扣上几本相关的 leetbook，都不太满意。于是乎花了点时间探索整理了一下，写成本文，(我认为的) 优点有四。

1. **面向小白，入门友好** 。主要针对像我一样的初学者，或者粗浅地看过一些图论算法，但感觉不是特别踏实的朋友。这里的「不踏实」指的是在题解区看到一个问题有眼花缭乱的多种图论方法，但自己只知道常用的那种，有的压根没听过；也可以指的是虽然知道怎么做，但相关算法的正确性证明或复杂度证明，未曾确切地把握过。
2. **循序渐进，反馈及时** 。特别突出了各章节之间的联系与过渡。为了使读者能够在每一章学习中都有及时的正反馈，每介绍一个算法，我都会配套一道力扣上的原题 (力扣没有典型题目则采用其他平台的题目)。
3. **编排得当，重点全面。** 内容编排上作者也颇费苦心，例如「初探图搜索 (遍历)」一节，推敲几日，最终决定用「无向图连通性」问题引入 $bfs/dfs$ 。然后再以「无向图判圈」和「有向图判圈」问题，一面加强对 $bfs/dfs$ 写法变化的把握，一面也突出有向图和无向图中 $bfs/dfs$ 写法的差异。再如「最短路径」中，从无权单源到带权单源，包括带权单源中的 DAG 情形，再到带权全源，网罗各种情形下的最短路算法，朴素版和优化版都详细给出算法过程，复杂度分析，一些特殊情形的讨论，以及针对具体题目的实现代码等。
4. **证明翔实，有根有据** 。在「最短路」和「最大流」这两个章节中，对所有不易看出的结论均给出了详细的，较为严格的证明。**包括且不限于对 Dijkstra、Prim、Bellman-Ford、SPFA、Floyd-Warshall 算法的正确性证明，对「最大流最小割定理」的证明，对 Edmonds-Karp、Dinic 算法复杂度的证明等。** 部分证明着实耗尽了作者的最后一点智商，导致目前 **智商欠费，大脑停机** 。

本文所涉具已呈于「主要内容一览」中，如果朋友们觉得合适，不妨一看。希望朋友们能感受到 yuki 的 **亿点用心** 。

**本文标题** 意在表达作者的一种「希望」，即通过本文的学习，看似沉重的图论算法，也能 **重重拿起，轻轻放下** 。

然而不幸的是，作者能力水平十分有限，文章虽已审视几轮，所列代码也悉经验证，但根据之前几篇文章的经验，这一篇也会毫无例外地出现一些错误。因此本文既是心得分享，也是小白 yuki 再次向大家请教的一次机会，**文中若有疏漏之处，请各位不吝赐教** 🤝。

※ Dinic 的代码还需一些时间验证，暂不列出。「实战应用」中目前有十几题，会持续增加，整篇文章也会持续维护。

※ 部分算法正确性证明及复杂度证明以单篇文章发布过，但为了保持本文完整度，也一并呈现。

※ 内容可能较多，可根据目录选择性阅读。

***

yuki的其他文章如下，欢迎阅读指正！

> 如下所有文章同时也在我的 github [仓库](https://github.com/iyukiyama/leetcode-posts) 中维护。

| 文章                                                         | [发布时间] 字数/览/藏/赞 (~2022-10-20)   |
| ------------------------------------------------------------ | ---------------------------------------- |
| [十大排序从入门到入赘](https://leetcode.cn/circle/discuss/eBo9UB/)  🔥🔥🔥 | [20220516]  2.5万字/64.8k览/3.7k藏/937赞 |
| [二分查找从入门到入睡](https://leetcode.cn/circle/discuss/ooxfo8/) 🔥🔥🔥 | [20220509]  2.3万字/38.4k览/2.1k藏/503赞 |
| [并查集从入门到出门](https://leetcode.cn/circle/discuss/qmjuMW/) 🔥🔥 | [20220514]  1.2万字/17.9k览/1.0k藏/321赞 |
| [图论算法从入门到放下](https://leetcode.cn/circle/discuss/FyPTTM/) 🔥🔥 | [20220617]  5.6万字/19.9k览/1.3k藏/365赞 |
| 树ADT系列 (预计13篇)                                         | 系列文章，连载中                         |
| 3. [二叉查找树](https://leetcode.cn/circle/discuss/wPzlSb/)  | [20220801]  5千字                        |
| 4. [AVL树](https://leetcode.cn/circle/discuss/zbwD3p/)       | [20220817]  5千字                        |
| 5. [splay树](https://leetcode.cn/circle/discuss/BCK17f/)     | [20220817]  5千字                        |
| 6. [红黑树从入门到看开](https://leetcode.cn/circle/discuss/SwgIJV/) 🔥🤯🤯🤯 | [20220915]  3万字/5.3k览/269藏/72赞      |
| 10. [树状数组从入门到下车](https://leetcode.cn/circle/discuss/qGREiN/) 🔥🤯 | [20220722]  1.4万字/5.8k览/196藏/72赞    |
| 11. [线段树从入门到急停](https://leetcode.cn/circle/discuss/H4aMOn/) 🔥🤯 | [20220726]  2.5万字/8.7k览/481藏/138赞   |
| [图论相关证明系列](https://leetcode.cn/circle/discuss/GV0JrV/) | 系列文章                                 |
| 1. [Dijkstra正确性证明](https://leetcode.cn/circle/discuss/jJQn7V/) 🤯 | [20220531]                               |
| 2. [Prim正确性证明](https://leetcode.cn/circle/discuss/VVEc8f/) 🤯 | [20220919]                               |
| 3. [Bellman-Ford及SPFA正确性证明](https://leetcode.cn/circle/discuss/xeEwYl/) | [20220602]                               |
| 4. [Floyd正确性证明](https://leetcode.cn/circle/discuss/Nbzix4/) | [20220602]                               |
| 5. [最大流最小割定理证明](https://leetcode.cn/circle/discuss/tMIy36/) 🤯🤯 | [20220719]                               |
| 6. [Edmonds-Karp复杂度证明](https://leetcode.cn/circle/discuss/tN3sZc/) 🤯🤯 | [20220515]                               |
| 7. [Dinic复杂度证明](https://leetcode.cn/circle/discuss/T9Xa1R/) 🤯🤯 | [20220531]                               |

***

[2022-12-01]

- 修改了若干代码实现，使其更易于阅读和理解。

[2022-09-28]

- 进一步完善了 Prim 算法正确性证明过程。

***

<!-- ## 目录

[TOC] -->

## 概览

### 内容一览

![graph-mind.png](https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/posts_img/algorithms/graph/summary.png)

### 图论算法复杂度一览

以下列出本文讲解的全部图论算法的时空复杂度。

| 分类       | 算法                | 时间复杂度 |
| ---------- | ------------------- | ---------- |
| 图遍历     | bfs                 | $O(V+E)$   |
|            | dfs                 | $O(V+E)$   |
| 拓扑排序   | Kahn                | $O(V+E)$   |
|            | Tarjan (TopoSort)   | $O(V+E)$   |
| 最短路     | 无权SSSP 朴素版     | $O(V^2)$   |
|            | 无权SSSP 队列版     | $O(V+E)$   |
|            | Dijkstra 朴素版     | $O(V^2)$   |
|            | Dijkstra 优先队列版 | $O(ElogV)$ |
|            | DAG SSSP            | $O(V+E)$   |
|            | Bellman-Ford        | $O(VE)$    |
|            | SPFA (BFM)          | $O(VE)$    |
|            | Floyd-Warshall      | $O(V^3)$   |
| 最小生成树 | Prim 朴素版         | $O(V^2)$   |
|            | Prim 优先队列版     | $O(ElogV)$ |
|            | Kruskal             | $O(ElogV)$ |
| 最大流     | Ford-Fulkerson      | $O(E*f)$   |
|            | Edmonds-Karp        | $O(VE^2)$  |
|            | Dinic (Dinitz)      | $O(V^2E)$  |

※  $V$ 和 $E$ 表示点集和边集，表格中涉及到「数量」的 $V$ 和 $E$，应为 $|V|$ 和 $|E|$ (半角 "|" 会影响 markdown 表格的显示)。

※ 空间复杂度主要取决于建图方式，以「邻接矩阵」建图时为 $O(|V|^2)$，以「邻接表」建图时为 $O(|V|+|E|)$ ，表中不再列出。

### 图的基本概念

| 概念 | 描述 |
| ---------------------------------------------------- | ------------------------------------------------------------ |
| 顶点 & 边 *vertex & edge* | 一对顶点 $(u, v), u, v ∈ V$ 。$V$ 为顶点集。所有边构成边集 $E$。 边的条数表为 $E$ ，顶点的个数表为 $V$ 。 |
| 图 *graph* | 顶点集 $V$ 和边集 $E$ 构成图。 |
| 权 / 值 *weight / cost* | 边的权重。 |
| 邻接 *adjacent* | 顶点 $u$ 与 $v$ 邻接当且仅当 $(u, v) ∈ E$ 。 |
| 邻接矩阵 *adjacent matrix* | 以矩阵表示图。对每条边 $(u, v)$ 置矩阵的 $A[u, v]$ 为 $true$，无 $(u, v)$ 边则为 $false$。 若边有权，则 $A[u, v]$ 等于该值，以一个很大或很小的数表示该边不存在。 |
| 邻接表 *adjacency list* | 对每一个顶点，以一个表存放其邻接顶点，共以 $V$ 个表表示图。 |
| 无向图 *undirected graph* | 点无序的图，$(u, v)$ 与 $(v, u)$ 为同一条边。 |
| 有向图 *directed graph / digraph* | 点对有序的图，$(u, v)$ 与 $(v, u)$ 为两条不同的边。 |
| 度 *degree* | 对无向图顶点 $v$ 而言，其边的数量，也即其邻接顶点的数量。 |
| 入度 *indegree* | 对有向图顶点 $v$ 而言，$(u, v)$ 边的数量 |
| 出度 *outdegree* | 对有向图顶点 $v$ 而言，$(v, u)$ 边的数量 |
| 路径 *path* | 为一顶点序列 $v_1, v_2, v_3,...,v_N$ 使得 $(v_i, v_{i+1}) ∈ E, 1<=i<=N-1$ 一个顶点到他自身也可以看成是一条路径，如果路径不包含边，则路径长为 0 。 |
| 路径长度 *path length* | 无向图中指路径上的边数，有向图中指路径边权和。 |
| 简单路径 *simple path* | 所有顶点都不同的路径。 |
| 圈 *cycle* | 满足 $v_1 = v_N$ 的长至少为 1 的路径。 |
| 环 / 自环 *loop* | 一个顶点到它自身的边 $(v, v)$ ，此概念不常用。 通常环也被视作圈。中文语境下「环」与「圈」通常不做区分，具体需联系上下文理解。 |
| 有向无环(圈)图 *directed acyclic graph, DAG* | 无(环)圈的有向图。 |
| 连通图 *connected graph* | 从一顶点 $w$ 到另一顶点 $v$ 有路径相连称 $w$ 与 $v$ 连通， 任意两顶点之间连通的图称为连通图。有向连通图两点之间的路径上的边同向。 |
| 连通分量 *connected component* | 对于无向图而言，一个极大连通子图为一个连通分量。 所有连通分量构成互相没有相同顶点的子图集合。 |
| 基础图 *underlying graph* | 有向图去掉边的方向后的图称为该有向图的基础图 (无向图)。 |
| 强连通 *strongly connected* | 称有向连通图是强连通的。 |
| 强连通分量 *strongly connected component (SCC)* | 对于有向图基础图的一个连通分量， 若其中的顶点两两连通，则称此连通分量为强连通分量。 |
| 弱连通 *weakly connected* | 有向图不是强连通的，但其基础图是连通的，则称该有向图是弱连通的。 |
| 完全图 *complete graph* | 每一对顶点间都有边相连的图。 |

在后续叙述中，我会假定你已熟悉该表所罗列概念。

## 图的表示

求解图上问题，首先要以合适的方式存储图。图的基本信息是顶点、边、边的方向以及边权，通过「邻接矩阵」或「邻接表」来存储图，可以很好地组织上述信息。本节简单介绍这两种存图方式，但暂不呈现相关代码，在后续章节解决实际问题时，我们会看到程序中是如何应用这两种方式存图以及提取图中的信息的。（本文大部分实现均采用「邻接表」法存图，若读者想立即参考「邻接矩阵」的具体写法，可参考「最短路径」-「带权全源最短路」-「Floyd-Warshall」-「代码」一节的代码。）

### 邻接矩阵

用二维数组 $edges[][]$ (或者二维容器，例如哈希表) 表示图的方法称为「邻接矩阵」存图法。当顶点可以用整数，尤其是从 0 到 $|V| - 1$ 的整数表示时，以二维数组存图，此时 $edges[u][v]$ 表示顶点 $u$ 指向顶点 $v$ 的边，若为带权图，其值表示边权；若为无权图，可令值为 1 或 0 等；若边不存在，可令值为 -1 或 $Infinity$ 等。邻接矩阵表示法所需空间为 $O(|V|^2)$，显然，当图较稀疏时，大量空间将被浪费，利用「邻接表」存图效率更高。

### 邻接表

对每一个顶点，以一个列表来存储其邻接顶点和相应的边权信息，于是图信息被存储在 $|V|$ 个列表中，所有这些列表存储了 $|E|$ 条边的信息，因此邻接表所需空间为 $O(|V|+|E|)$ 。当顶点可以用整数，尤其是从 0 到 $|V| - 1$ 的整数表示时，普遍以线性表来存图。对于无权图，以 `List<List<Integer>> graph` 存图，通过 `graph.get(u).get(v)` 来获取边 $(u, v)$ 信息。对于带权图，由于需要存储边权，因此邻接表中的泛型为 $int[]$ ，即以 `List<List<int[]>> graph` 存图，对于 `int[] v_weight = graph.get(u)` ，$v\_weight$ 的大小为 2 ， $v\_weight[0]$ 为 $u$ 的邻接顶点 $v$，$v\_weight[1]$ 为 $|(u,v)|$。 也可以用 `List<List<Pair>> graph` 存图，但本文不采用此种写法。

当顶点不适合用非负整数表示时，例如为字符串或其他引用类型，则可用哈希表存图，$ke y$ 为顶点 (字符串或其他引用类型)，$value$ 仍是列表，内部存储顶点 $key$ 邻接顶点。

### 链式向前星

相比前两种存图法，「链式向前星」存图法是一种极具技巧性的存图方式，虽不太直观，但有不少优点，我们先来介绍其具体实现，再分析其优点。

首先，链式向前星的 **本质也是「邻接表」** ，与邻接表法的显式邻接表 (即 $graph.get(u)$ 获取 $u$ 的 $List$ 类型邻接表) 不同，链式向前星并不显式地存储与顶点对应的邻接表，而是将边编号，通过 **「边下标指针」** 来获取一个顶点的邻边信息。我们直接给出链式向前星具体的存图结构，然后再描述如何通过这样的安排来存图，使得我们能够获取图的相关信息，例如遍历一个顶点的所有边 (邻接顶点) 。

- 边从 $1$ 到 $|E|$ 编号。

- $ends[]$ 数组大小为 $|E|+1$ ，$ends[edgeNum]$ 表示下标  (编号) 为 $edgeNum$ 的边的终点。
- $weights[]$ 数组大小为 $|E|+1$ ，用于带权图，$weights[edgeNum]$ 表示下标为 $edgeNum$ 的边的边权。
- $nexts[]$ 数组大小为 $|E|+1$ ，对于顶点 $u$ ，$nexts[edgeNum]$ 表示下标为 $edgeNum$ 的边 **「在其所在的顶点邻接表」** 中的下一条边。
- $heads[]$ 数组大小为 $|V|$ ，对于顶点 $u$ ，$heads[u]$表示顶点 $u$ 的第一条边。

链式向前星通过「插头法」加边建图，伪代码如下，建议结合后图分析此伪代码。

```java
// 带权有向图
int n, m, edgeNum // n 为顶点数，m 为边数，edgeNum 为边下标(编号)
int[] heads = new int[n]
int[] weights = new int[m + 1], ends = new int[m + 1], nexts = new int[m + 1]

int u, v, weight // 添加边(u,v)
++edgeNum // 作为第 edgeNum 条边加入
weights[edgeNum] = weight // 边权
ends[edgeNum] = v // 该边的终点为 v
// heads[u] 表示建图至当前状态时 u 的邻接表中的第一条边(u,w)的下标
// (u,v)是 u 的邻接表中新加入的边，此句表示边(u,v)的下一条边是(u,w)
// 这也就是链式向前星「插头法」的体现，也是较难理解的一句
nexts[edgeNum] = heads[u] 
// 因为(u,v)插入了 u 的邻接表中原首边(u,w)之前，则此时的首边为(u,v)
heads[u] = edgeNum
```

```java
// 无权无向图
int n, m, edgeNum // n 为顶点数，m 为边数，edgeNum 为边下标(编号)
int[] heads = new int[n]
int[] ends = new int[2 * m + 1], nexts = new int[2 * m + 1]

int u, v, val // 添加边(u,v)和(v,u)
// 以下添加 (u,v)
++edgeNum // 作为第 edgeNum 条边加入
ends[edgeNum] = v // 该边的终点为 v
nexts[edgeNum] = heads[u] 
heads[u] = edgeNum
// 以下添加 (v,u)
++edgeNum // 作为第 edgeNum 条边加入
ends[edgeNum] = u // 该边的终点为 v
nexts[edgeNum] = heads[v] 
heads[v] = edgeNum
```

通过下图展示顶点 $u$ 的边是如何被存放和表达的 (只展现关键的 $edgeNum, heads, nexts$ 是如何关连的)。黑色实心圆点表示 $u$ 的第一条边，即 $heads[u]$ 。

- 在遍历边建图之前，`heads[u] = 0` ，表示此时 $u$ 无边，图中用蓝色虚线箭头表达。

- 在遍历到第 4 条边时 (前三条边与 $u$ 无关，它们的存图过程与 $u$ 类似)，遇到 $u$ 的第一条边 $(u,x)$ ，该边的编号为 $edgeNum = 4$，于是立即让这条新边作为首边 $heads[u] = 4$，然后让这条边的后继为上一条边 $nexts[4] = 0$ ，但是这需要先保存 0，例如下面这样操作。

```java
  int tmp = heads[u]; // tmp = 0
  heads[u] = edgeNum; // heads[u] = 4
  nexts[edgeNum] = tmp; // nexts[4] = 0
  ```

实际上我们可以先设置 $nexts[edgeNum]$ 再更新 $heads[u]$ ，就无需 $tmp$ 了。

```java
  nexts[edgeNum] = heads[u]; // nexts[4] = 0
  heads[u] = edgeNum; // heads[u] = 4
  ```

- 继续遍历边建图，我们在遍历到第 7 条边时遇到第二条 $u$ 的边 $(u,y)$ ，遍历到第 10 条边时遇到 $u$ 的第三条边 $(u,z)$ 。同样地，每次我们都令新边指向当前首边，然后将新边作为当前首边。

![image.png](https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/posts_img/algorithms/graph/linked-star.png)

从上述伪代码和图示中我们感到 `nexts[edgeNum] = heads[u]` 较难理解，此行是体现链式向前星「插头法」的核心，建图过程中我们总是以 $heads[u]$ 「实时地」更新顶点 $u$ 的首边。完成建图后，对于任意顶点 $u$ ，$edgeNum = heads[u]$ 为 $u$ 的首边下标，通过 $edgeNum = nexts[edgeNum]$ 可以「链式」地遍历 $u$ 的所有邻边，直到最后 $edgeNum = nexts[edgeNum] = 0$，遍历完成。此时我们能够很容易地写出「链式向前星」遍历顶点 $u$ 的邻边的写法。

```java
for(int edgeNum = heads[u]; edgeNum != 0; edgeNum = nexts[edgeNum]){
    int v = ends[edgeNum]; 
    int weight = weights[edgeNum]; // 若为带权图
}
```

如果还是不太好理解，我们可以把 $edge$ 看作是边类 $Edge$ 的实例，$nexts[edgeNum]$ 是其属性 $edge.next$ ，是此边的下一条边 (的引用)。顶点也看作一个类，每个顶点持有一个 $headEdge$ 属性，表示 $u$ 的首边， $head[u]$ 就是 $u.headEdge$ 。 那么基于数组写法就可以写成我们更熟悉的类的写法 (伪代码，仅作示意)：

```java
遍历到 u 的新边 edge 后的「插头」操作
edge.next = u.headEdge;
u.headEdge = edge;

遍历 u 的边
for(Edge edge = u.headEdge; edge != null; edge = edge.next)
```

现在我们能够看出「链式向前星」的如下优点：

1. 空间复杂度为 $O(|V|+|E|)$ 。且相比利用泛型线性表的邻接表法，空间开销会更小，因为 $List$ 的内部数组通常比实际大小更大。
2. 由于存粹以数组存图，因此处理速度也会比 $List$ 更快。
3. 由于对边编号，在某些需要处理一条边的反向边的场景下 (例如最大流算法中)，可以很方便地操作反向边 (具体看「小结」)。

读者若想尽快把握该存图操作，可直接查看如下位置的相应代码。

> 无权无向图: 「初探图搜索 (遍历)」-「无向图连通性」-「BFS」-「代码」
>
> 带权有向图: 「最短路径」-「带权单源最短路」-「Dijkstra」-「优先队列版」-「代码」

※ 从前面的图示可以看出「链式向前星」这个命名是很贴切的。根据知乎问题 [链式前向星的发明者是谁？](https://www.zhihu.com/question/306076815) ，知乎用户「Malash」似乎是中文「链式向前星」一词的命名者。根据该问题下 「Yixiao Huang」 用户的回答，该存图方式似乎出自此篇发表于 1987 年的论文 [A versatile data structure for edge-oriented graph algorithms](https://dl.acm.org/doi/pdf/10.1145/214762.214769) 。

### 小结

本节学习了三种图的表示方法，各有特点，也有各自适合的应用场景。

- 对已知「稠密图」建图，或需要频繁地根据两个顶点来读写边权的场景时，考虑「邻接矩阵」。
- 对已知「稀疏图」建图，或只需根据顶点 $u$ 遍历其邻边 (邻接顶点) 的场景时，考虑「邻接表」或「链式向前星」。这种场景较为常见，因「邻接表」更易实现，因此本文若为该场景，皆采用「邻接表」建图。
- 在希望空间复杂度更优，又需要操作「反向边」的场景，考虑「链式向前星」。

| 操作 | 邻接矩阵 | 邻接表 | 链式向前星 |
| ----------------------------- | ---------------------------- | ------------------------------- | ------------------------------------------------------------ |
| 编写 | 容易 | 容易 | 相对复杂 |
| 空间 | $O(V^2)$ | $O(V+E)$ | $O(V+E)$ 系数比邻接表更优 |
| 遍历 $u$ 的邻边 (邻接顶点) | 遍历 $dists[u]$ $O(V)$ | 遍历 $graph.get(u)$ $O(V)$ | $edgeNum = heads[u]$ 和 $edgeNum = nexts[edgeNum]$ 配合 $O(V)$ |
| 根据 $u, v$ 取边 $(u,v)$ | $dists[u][v]$ $O(1)$ | 遍历 $graph.get(u)$ $O(V)$ | $edgeNum = heads[u]$ 和 $edgeNum = nexts[edgeNum]$ 配合 $O(V)$ |
| 根据 $(u,v)$ 取反向边 $(v,u)$ | $dists[v][u]$ $O(1)$ | 遍历 $graph.get(v)$ $O(V)$ | 若已知 $(u,v)$ 编号 `k` ， 则可将边编号为 $[2,E+1] ，$ 则 $(v, u)$ 的编号为 `k^1` $O(1)$ |

※ 链式向前星取反向边操作的说明：

将边编号为 $[2,E+1]$ ，初始边编号为 1 (或者 $[0, E-1]$ ，初始边编号为 -1)，加边建图时加入偶数编号为 $k$ 的边 $(u,v)$ ，总是立即加入编号为 $k+1$ 的反向边 $(v, u)$ 。由于边 从 2 开始编号，因此：

- 所有编号为偶数的边，若记作 $k$ ，则其对应的反向边为 $k+1$
- 所有编号为奇数的边，若记作 $k$ ，则其对应的反向边为 $k-1$

上述两种情况可统一为 `k^1` ，`^` 为异或运算。

另外，并非所有图论问题都需要「建图」，因为问题的输入本身就包含了图的信息，只不过通常需要组织成适合算法操作的结构，若该输入可直接被算法操作，也就不必再另外「建图」了。例如在「最小生成树」-「Kruskal」一节中，利用输入 $connections$ 即可完成求解，无需另外建图。

## 初探图搜索 (遍历)

图的搜索 ($search$) 或者说遍历  ($traversal$) 算法是其他更高级的图论算法的基础，因此熟练掌握图的搜索算法非常重要。**「搜索」** 一词的重点在于关注图中的一个 $target$ ，可以是顶点，也可以是边或其他，找到即完成任务；**「遍历」** 一词的重点在于对整张图无遗漏地探索，多数时候这两个词是通用的。如同「树」的 **深度优先搜索**  ($dfs$) 和 **广度优先搜索**  ($bfs$)，图的基本搜索方法也是这两种。实际上我们知道树是一种特殊的图，在学习本节代码的过程中你会发现二者有很多相似之处。

$bfs$ 和 $dfs$ 的应用非常丰富，可用于解决许多图上的问题，但只需掌握其 **基本写法** ，就足以支撑我们学习后续更高级的图论算法。为了能够在学习中及时得到反馈，本节以如下三道基本题目引入并详细介绍最基本的 $bfs$ 和 $dfs$ 写法，读者在开始相应子章节前应熟读对应题目。学习解法后应尝试独立写出并提交以得到反馈，最后再参照本节给出的代码来自查。

| 问题           | 题目                                                         | 难度 | 题解                                                         |
| -------------- | ------------------------------------------------------------ | ---- | ------------------------------------------------------------ |
| 无向图的连通性 | [323. 无向图中连通分量的数目](https://leetcode.cn/problems/number-of-connected-components-in-an-undirected-graph/) | 中等 | [题解](https://leetcode.cn/problems/number-of-connected-components-in-an-undirected-graph/solution/by-yukiyama-y5l4/) |
| 无向图判圈     | [684. 冗余连接](https://leetcode.cn/problems/redundant-connection/) | 中等 | [题解](https://leetcode.cn/problems/redundant-connection/solution/-by-yukiyama-mlqi/) |
| 有向图判圈     | [207. 课程表](https://leetcode.cn/problems/course-schedule/) | 中等 | [题解](https://leetcode.cn/problems/course-schedule/solution/yukiyama-by-yukiyama-lbz3/) |

※ 当讨论「连通性」时，通常是对「无向图」而言的，即不关注边方向，只关注那些通过边互相连通的连通分量。在「有向图」中，另有「强连通分量」概念，我们已在「基本概念」中给出定义。

※ 这三道题均有适用性更强的「并查集」解法。如果你尚未学习过「并查集」或仍觉得不太熟练，可以参考我写的 [并查集从入门到出门](https://leetcode.cn/circle/discuss/qmjuMW/) ，全文 1w+ 字，尝试透彻分析并查集的基本内容，2022年5月中旬在力扣讨论区发布后半个月内收获 5k 阅读量，500+ 收藏，100+ 点赞。

### 无向图连通性

首先通过考察「无向图连通性」问题  [323. 无向图中连通分量的数目](https://leetcode.cn/problems/number-of-connected-components-in-an-undirected-graph/) 来学习最基本的图的 $bfs / dfs$ 算法。

虽然此时我们还不知道要如何具体写出这两种算法的细节，但我们知道通过 $bfs / dfs$，可以从一个顶点 $u$ 出发，「搜索」到与之连通的所有顶点。于是我们不难构思出通过「搜索」来寻找所有不相交的「连通分量」的过程。

1. 依次访问所有顶点，对于当前顶点 $u$，先检查它是否已经被访问过，若未被访问，以它为起始点进行「搜索」，在开始搜索后立即将 $u$ 标记为已访问。
2. 搜索过程中，跳过那些「已访问」的顶点，对于「未访问」的顶点，显然它们与 $u$ 同属一个连通分量。
3. 因为从 $u$ 开始的「搜索」一定能够找到所有与 $u$ 在同一连通分量的顶点，因此能够以多少个顶点为「起点」开始搜索，就有多少个连通分量。

上述过程的实现需要设置一个 $boolean$ $visited$ 数组，大小为顶点数，表示在此后的搜索中是否访问过。「搜索」可以采用 $bfs$ 或 $dfs$。

※ 通过 $bfs / dfs$ 来 **逐渐标记整张图 (的所有顶点)**  的做法，也被形象地称之为 [**flood fill (泛洪)**](https://en.wikipedia.org/wiki/Flood_fill) 或 seed fill (播种)，本质上是 **「记忆化搜索」** 的应用。

※ 若采用 $bfs$ 时，不只是对单个顶点按层搜索，而是对整张图按层搜索，也即初始时找到最外层的所有顶点 (对无向图来说度为 1，对有向图来说入度为 0 的顶点)，然后将这些顶点的邻接顶点作为下一层顶点，以此类推，按层操作。那么这种处理方式也被形象地称为「涟漪法」、「波纹法」、「涨潮法」等。 后续在「拓扑排序」、「无权单源最短路」中都能看到此方法的应用。

#### BFS

采用 $bfs$ ，如同树的 $bfs$， 需要借助队列。每次对「未访问」的顶点 $u$ 执行「搜索」时，将其放入队列中，出队时置出队顶点为已访问。借助队列完成同一连通分量顶点的搜索。只要队不空，则队首 $u$ 出队，访问 $u$ 的所有邻接顶点 $v$ ，并将它们都放入队中。通过这个方式，一定可以 **按层** 完成所有与 $u$ 相连通的顶点的标记。代码如下。需要注意的是，无向图要 **双向建边** 。

一般可用哈希表 $Map<k, v>$ 来存储图信息，$k$ 为顶点，$v$ 为该顶点的邻接顶点列表。当顶点为一组连续整数时 (通常为 $\{0,1,2,...,n-1\}$，$n$ 为顶点总数)，用 `List<List<Integer>>` 存图效率更高，下标表示顶点，其对应的 `List<Integer>` 即为该顶点的邻接顶点表。通过下标可快速获取顶点的邻接表。

第一份代码以 **哈希表** 存图，适合于无法用连续的整数来表示顶点的场景。本题中，顶点可以被表示为 $\{0, 1,2,3,...n - 1\}$ ，因此采用第二份以 **线性表** 存图的代码效率更高。之后的内容，只要能够以线性表存图，就不再列出哈希表存图的版本。

```java
// 以 HashMap 存图
class Solution {
 public int countComponents(int n, int[][] edges) {
 // 1. 建图
 Map<Integer, List<Integer>> graph = new HashMap<>();
 for(int[] edge : edges){
 int u = edge[0], v = edge[1];
 List<Integer> uAdj = graph.getOrDefault(u, new ArrayList<>());
 uAdj.add(v);
 graph.put(u, uAdj); // 无向图边 (u,v)
 List<Integer> vAdj = graph.getOrDefault(v, new ArrayList<>());
 vAdj.add(u);
 graph.put(v, vAdj); // 无向图边 (v,u)
 }
 // 2. 计算连通分量
 boolean[] visited = new boolean[n];
 int count = 0;
 for(int u = 0; u < n; ++u){
 if(!visited[u]){ // 以未访问过的 u 为起始顶点
 count++; // 只要顶点 u 此时尚未被访问，说明它不在此前的链路(连通分量)中，那么就以它为新的连通分量起点，连通分量数量+1
 bfs(u, visited, graph); // 通过 bfs 寻找与 u 处于同一连通分量的顶点，并标为已访问
 }
 }
 return count;
 }
 public void bfs(int u, boolean[] visited, Map<Integer, List<Integer>> graph){
 Queue<Integer> q = new ArrayDeque<>();
 q.add(u);
 while(!q.isEmpty()){
 u = q.remove();
 visited[u] = true; // 在出队时置为已访问
 List<Integer> uAdj = graph.get(u);
 if(uAdj != null){
 for(int v : graph.get(u)){
 if(!visited[v]) q.add(v); // 已访问的顶点属于此前搜索过的连通分量
 }
 }
 }
 }
}
```

```java
// 以 List 建图
class Solution {
 public int countComponents(int n, int[][] edges) {
 // 1. 建图
 List<List<Integer>> graph = new ArrayList<>();
 for(int i = 0; i < n; ++i) graph.add(new ArrayList<>());
 for(int[] edge : edges){
 int u = edge[0], v = edge[1];
 graph.get(u).add(v); // 无向图边 (u,v)
 graph.get(v).add(u); // 无向图边 (v,u)
 }
 // 2. 计算连通分量
 boolean[] visited = new boolean[n];
 int count = 0;
 for(int u = 0; u < n; ++u){
 if(!visited[u]){ // 以未访问过的 u 为起始顶点
 count++; // 只要顶点 u 此时尚未被访问，说明它不在此前的链路(连通分量)中，那么就以它为新的连通分量起点，连通分量数量+1
 bfs(u, visited, graph); // 通过 bfs 寻找与 u 处于同一连通分量的顶点，并标为已访问
 }
 }
 return count;
 }
 public void bfs(int u, boolean[] visited, List<List<Integer>> graph){
 Queue<Integer> q = new ArrayDeque<>();
 q.add(u);
 while(!q.isEmpty()){
 u = q.remove();
 visited[u] = true; // 在出队时置为已访问
 for(int v : graph.get(u)){
 if(!visited[v]) q.add(v); // 已访问的顶点属于此前搜索过的连通分量
 }
 }
 }
}
```

```java
// 链式向前星存图
class Solution {
 public int countComponents(int n, int[][] edges) {
 List<List<Integer>> graph = new ArrayList<>();
 int m = edges.length, edgeNum = 0;
 int[] ends = new int[2 * m + 1], nexts = new int[2 * m + 1];
 int[] heads = new int[n];
 boolean[] visited = new boolean[n];
 for(int[] edge : edges){
 int u = edge[0], v = edge[1];
 // 添加边 (u, v)
 ++edgeNum;
 ends[edgeNum] = v;
 nexts[edgeNum] = heads[u];
 heads[u] = edgeNum;
 // 添加边 (v, u)
 ++edgeNum;
 ends[edgeNum] = u;
 nexts[edgeNum] = heads[v];
 heads[v] = edgeNum;
 }
 int count = 0;
 for(int u = 0; u < n; u++){
 if(!visited[u]) {
 count++; // 只要顶点 u 此时尚未被访问，说明它不再此前的链路(连通分量)中，以它为新的连通分量起点
 bfs(u, visited, heads, ends, nexts);
 }
 }
 return count;
 }
 private void bfs(int u, boolean[] visited, int[] heads, int[] ends, int[] nexts){
 Queue<Integer> q = new ArrayDeque<>();
 q.add(u);
 visited[u] = true;
 while(!q.isEmpty()){
 int v = q.remove();
 for(int edgeNum = heads[v]; edgeNum != 0; edgeNum = nexts[edgeNum]) {
 int w = ends[edgeNum];
 if(!visited[w]) {
 q.add(w);
 visited[w] = true;
 }
 }
 }
 }
}
```

这就是图的 **最基本** 的 $bfs$ 写法，也是后续应用了 $bfs$ 的更高级的图论算法的基础，读者应当熟练掌握。

#### DFS

若搜索采用 $dfs$ ，每次对「未访问」的顶点 $u$ 执行「搜索」，进入 $dfs$ 方法后立即置 $visited[u] = true$ ，然后以 $for$ 循环依次地，对其「未访问」的邻接顶点执行 $dfs$ 即可。$dfs$ 结束时，$u$ 所在连通分量的所有顶点 **必然** 都被标记为「已访问」。代码如下。

```java
class Solution {
 public int countComponents(int n, int[][] edges) {
 List<List<Integer>> graph = new ArrayList<>();
 for(int i = 0; i < n; i++) graph.add(new ArrayList<>());
 for(int[] edge : edges){ // 建图
 int u = edge[0], v = edge[1];
 graph.get(u).add(v); // 无向图边 (u,v)
 graph.get(v).add(u); // 无向图边 (v,u)
 }
 boolean[] visited = new boolean[n];
 int count = 0;
 for(int u = 0; u < n; u++){
 if(!visited[u]) {
 count++; // 只要顶点 u 此时尚未被访问，说明它不在此前的链路(连通分量)中，以它为新的连通分量起点
 dfs(u, visited, graph);
 }
 }
 return count;
 }
 private void dfs(int u, boolean[] visited, List<List<Integer>> graph){
 visited[u] = true; // 立即置为已访问
 for(int v : graph.get(u)) {
 if(!visited[v]) dfs(v, visited, graph);
 }
 }
}
```

这就是图的 **最基本** 的 $dfs$ 写法，也是后续应用了 $dfs$ 的更高级的图论算法的基础，读者应当熟练掌握。

#### 时空复杂度

**时间复杂度:**

无论是 $bfs$ 实现还是 $dfs$ 实现，遍历顶点 $v$ 并从 $v$ 开始泛洪。考虑图所有顶点构成 [完全图](https://en.wikipedia.org/wiki/Complete_graph)  (任意两个顶点间都有边连接)，那么对第一个顶点 $v$ 执行搜索后，每个顶点都会询问所有他的 $|V| - 1$ 个邻接顶点是否已被访问。最坏和平均时间复杂度为 $O(|V|^2)$。

**空间复杂度:** 存图空间 $O(|V|+|E|)$ ， $visited$ 空间 $O(|V|)$，递归栈或队列空间 $O(|V|)$。总的空间复杂度为 $O(|V|+|E|)$ ，该空间体现了图的规模，也称图的 **线性空间复杂度** 。

#### 并查集

并查集是一种用来解决「连通分量」问题的专用性很强的数据结构，对于 323 题，最为直观合适且高效的办法是「并查集」。并查集本身也属「图论」范畴，我已经在另一篇文章中做过讲解，因此本文不再重复。作为图论的重要一环，并查集的学习是非常必要的，在后续「最小生成树」一节中，我们会再次看到它的身影。总之，如果你还不熟悉并查集，可以阅读我写的 [并查集从入门到出门](https://leetcode.cn/circle/discuss/qmjuMW/) (全文1w+字，尝试透彻分析并查集的基本内容，2022年5月中旬在力扣讨论区发布后半个月内收获 5k 阅读量，500+ 收藏，100+ 点赞) 。

### 判断图是否有圈

下面我们考察如何判断图是否有圈。以 [684. 冗余连接](https://leetcode.cn/problems/redundant-connection/) 一题学习如何利用 $bfs / dfs$  **在无向图中判圈** ，以 [207. 课程表](https://leetcode.cn/problems/course-schedule/) 一题学习如何利用 $bfs / dfs$  **在有向图中判圈** 。通过这两道题目，我们进一步加深对 $bfs / dfs$ 的理解，并体会它们此处的应用相比在「无向图连通性」应用中的变化。我们还会看到在「无向图」和「有向图」中，利用「加边法」或「减边法」判圈的代码，只有很细微的差别。

#### 无向图判圈

对于 [684. 冗余连接](https://leetcode.cn/problems/redundant-connection/)，题目要求我们找到使得图产生圈的 (在 $edges$ 中)  **最后出现的边** 。有了上一节的经验，我们很容易想到，从某顶点 $v$ 出发，对其执行 $bfs$ 或 $dfs$ ，若能在此过程中找到 $v$ ，则我们确定 $v$ 是该圈上的一个顶点。对于所有的顶点，我们都执行同样的搜索，就可以确定圈上的所有顶点，然后对照 $edges$ ，就可以找出最后出现的边。但这种通过点来找边的做法比较繁琐，我们可以直接从「边」入手解决本题。现给出如下 **「加边法」** 和 **「减边法」** ，均为「泛洪法」。

**加边法 & 减边法**

1. 加边法: 建图过程中，每加入一条边 $(u, v)$ 前，搜索在当前图上，能否从 $u$ 搜索到 $v$，如果可以，则说明此时 $u$ 与 $v$ 已经连通，再加入 $(u, v)$ 将导致成圈。由于我们从前到后依次取 $edges$ 中的边加入，因此导致成圈的那条边就是所求。

2. 减边法：加边法的逆过程。先完整建图，之后从 $edges$ 中逆序取边 $(u, v)$ ，从当前图中减去该边并检测从 $u$ 是否能连通  $v$，若仍能连通，说明 $(u, v)$ 是圈上的一条边，由于我们逆序取边，则该边就是所求。

这两种方法都很好理解，应用 $bfs / dfs$ 执行搜索，我们给出如下加边法的两份代码，减边法和其他方法代码此处不列出，读者若想查看具体写法，可参考「实战应用」中本题的 [题解](https://leetcode.cn/problems/redundant-connection/solution/-by-yukiyama-mlqi/) 。

比较此处的代码与「无向图连通性」一节的代码，可以看到基本框架一样，仅有以下不同，这些不同都是为适应本题所做的简单调整。

- 本题通过 $bfs/dfs$ 寻找成圈的最后一条边。
- 本题中，每次搜索结束后，若未找到圈，需要重置 $visited$。

##### BFS 加边法代码

```java
// 加边法 + bfs
class Solution {
 public int[] findRedundantConnection(int[][] edges) {
 int n = edges.length;
 boolean[] visited = new boolean[n];
 List<List<Integer>> graph = new ArrayList<>();
 for(int i = 0; i < n; ++i) graph.add(new ArrayList<>());
 for(int[] edge : edges){
 int u = edge[0] - 1, v = edge[1] - 1;
 if(bfs(u, v, visited, graph)) { // 通过 bfs 判断 u, v 是否连通
 return new int[]{u + 1, v + 1};
 }
 graph.get(u).add(v); // 加边 (u, v)
 graph.get(v).add(u); // 加边 (v, u)
 Arrays.fill(visited, false);
 }
 return null; // 本题保证必有答案
 }
 public boolean bfs(int u, int v, boolean[] visited, List<List<Integer>> graph){
 Queue<Integer> q = new ArrayDeque<>();
 q.add(u);
 while(!q.isEmpty()){
 u = q.remove();
 visited[u] = true;
 for(int w : graph.get(u)){
 if(w == v) return true; // 判明 u, v 连通立即返回 true
 if(!visited[w]) q.add(w);
 }
 }
 return false;
 }
}
```

##### DFS 加边法代码

```java
// 加边法 + dfs
class Solution {
 boolean hasCycle = false;
 public int[] findRedundantConnection(int[][] edges) {
 int n = edges.length;
 boolean[] visited = new boolean[n];
 List<List<Integer>> graph = new ArrayList<>();
 for(int i = 0; i < n; ++i) graph.add(new ArrayList<>());
 for(int[] edge : edges){
 int u = edge[0] - 1, v = edge[1] - 1;
 if(dfs(u, v, visited, graph)) { // 通过 dfs 判断 u, v 是否连通
 return new int[]{u + 1, v + 1};
 }
 graph.get(u).add(v); // 加边 (u, v)
 graph.get(v).add(u); // 加边 (v, u)
 Arrays.fill(visited, false); // 每次搜索后要重置 visited
 }
 return null; // 本题保证必有答案
 }
 public boolean dfs(int u, int v, boolean[] visited, List<List<Integer>> graph){
 visited[u] = true;
 for(int w : graph.get(u)){
 if(w == v) hasCycle = true;
 if(!visited[w]) hasCycle = dfs(w, v, visited, graph);
 }
 return hasCycle;
 }
}
```

##### 时空复杂度

**时间复杂度:** 最坏和平均时间复杂度都是 $O(|V|^2)$。分析与「无向图连通性」的泛洪解法一致，不再赘述。

**空间复杂度:** 存图空间 $O(|V|+|E|)$ ， $visited$ 空间 $O(|V|)$，递归栈或队列空间 $O(|V|)$ 。总体为线性空间复杂度 $O(|V|+|E|)$ 。

#### 有向图判圈

684 题的图为无向图，现在我们通过 [207. 课程表](https://leetcode.cn/problems/course-schedule/) 一题来学习应用 $bfs / dfs$ 在 **有向图中判圈** 。

读题后不难看出课程之间的依赖关系可抽象成「图」。每一门课程为一个顶点，课程 $v$ 依赖课程 $u$ 表示有向边 $(u, v)$ 。仔细理解题意后我们有如下结论，**当且仅当** 这些课程构成的有向图 **「无圈」** 时，能够完成所有课程的学习。也就是我们只需要根据输入构建有向图，然后判断该图是否有圈即可，无圈返回 $true$ ， 有圈返回 $false$ 。

类似「无向图判圈」，我们同样可以用「加边法」或「减边法」来求解此题。差别仅在于如下几点。

- 本题为有向图，建图时只需单向建边。
- 考察边 $(u, v)$ 加入 (加边法) 或减去 (减边法) 后，该边两点是否还连通时，根据圈方向的 **单向性** ，应当以 $v$ 作为起点， $u$ 作为目标来搜索。
- 若存在自环，即 $(u, u)$ 这样的圈，加边前或减边后都无法再搜索到 $target$ (即 $u$ ) ，将导致误判。因此对于自环，需要特殊判断。

这些差别体现在代码中只有两三行的区别，有了之前的经验，我们能够轻松实现。应用 $bfs / dfs$ 执行搜索，给出如下加边法的两份代码，减边法和其他方法代码此处不列出，可参考「实战应用」中本题的 [题解](https://leetcode.cn/problems/course-schedule/solution/yukiyama-by-yukiyama-lbz3/) 。

##### BFS 加边法代码

```java
// 加边法 + BFS
class Solution {
 public boolean canFinish(int numCourses, int[][] prerequisites) {
 List<List<Integer>> graph = new ArrayList<>();
 boolean[] visited = new boolean[numCourses];
 for(int i = 0; i < numCourses; ++i) {
 graph.add(new ArrayList<>());
 }
 for(int[] edge : prerequisites){ // 建图
 int v = edge[0], u = edge[1]; // 要学习 v 先学习 u，因此 u -> v
 if(u == v) return false; // 自环特判
 if(bfs(v, u, visited, graph)) return false; // 根据有向图特点，检测是否可以从 v 到 u
 Arrays.fill(visited, false); // 重置 visited
 graph.get(u).add(v); // 加边 (u, v)
 }
 return true;
 }
 private boolean bfs(int u, int target, boolean[] visited, List<List<Integer>> graph){
 Queue<Integer> q = new ArrayDeque<>();
 q.add(u);
 while(!q.isEmpty()){ 
 u = q.remove();
 visited[u] = true; // 出队时置为true
 for(int v : graph.get(u)){
 if(v == target) return true; // 找到 target 表示有圈
 if(!visited[v]) q.add(v);
 }
 }
 return false;
 }
}
```

##### DFS 加边法代码

```java
// 加边法 + DFS
class Solution {
 boolean hasCycle = false;
 public boolean canFinish(int numCourses, int[][] prerequisites) {
 List<List<Integer>> graph = new ArrayList<>();
 boolean[] visited = new boolean[numCourses];
 for(int i = 0; i < numCourses; ++i) {
 graph.add(new ArrayList<>());
 }
 for(int[] edge : prerequisites){ // 建图
 int v = edge[0], u = edge[1]; // 要学习 v 先学习 u，因此 u -> v
 if(u == v) return false; // 自环特判
 if(dfs(v, u, visited, graph)) return false; // 根据有向图特点，检测是否可以从 v 到 u
 Arrays.fill(visited, false); // 重置 visited
 graph.get(u).add(v); // 加边 (u, v)
 }
 return true;
 }
 private boolean dfs(int u, int target, boolean[] visited, List<List<Integer>> graph){
 visited[u] = true;
 for(int v : graph.get(u)){
 if(v == target) hasCycle = true;
 if(!visited[v]) hasCycle = dfs(v, target, visited, graph);
 }
 return hasCycle;
 }
}
```

##### 时空复杂度

**时间复杂度:** 最坏和平均时间复杂度都是 $O(|V|^2)$。分析与「无向图连通性」的泛洪解法一致，不再赘述。

**空间复杂度:** 存图空间 $O(|V|+|E|)$ ， $visited$ 空间 $O(|V|)$，递归栈或队列空间 $O(|V|)$ 。总体为线性空间复杂度 $O(|V|+|E|)$ 。

### 小结

在本节中，我们通过「无向图的连通性」展示了图搜索 (遍历) 最基本的 $bfs / dfs$ 写法。接着，在「判断图是否有圈」中，进一步展示了在 **「无向图」和「有向图」** 中如何应用节本的 $bfs / dfs$ 写法，通过些许调整来适应新的场景。

当我们重新审视「图判圈」问题时，我们会感觉到泛洪做法中有很多重复操作。我们每次加边前 (或减边后) 泛洪都是在当前整张图上进行的，我们自然会想，能否通过对原图的一次「遍历」来找到圈呢？答案是可以的，只需要在基本 $bfs$ / $dfs$ 的基础上，配合其他一些量再做调整即可，该方法就是著名的 **「拓扑排序」** ，属于图论算法中比 $bfs$ / $dfs$ 稍微进阶一些的算法。利用「拓扑排序」来判圈，可将时间复杂度从 $O(|V|^2)$ 降为 $O(|V|+|E|)$ 。在「拓扑排序」一节的最后，我们将给出相应代码。

现在你已经牢固掌握了图的 $bfs$ / $dfs$ 原理和写法，接下来我们就可以满怀信心地从「拓扑排序」开始学习更高级更复杂的图论算法。

## 拓扑排序

[拓扑排序 (Topological Sorting)](https://en.wikipedia.org/wiki/Topological_sorting) : 对有向图的顶点的排序，如果存在从顶点 $u$ 到顶点 $v$ 的路径，那么拓扑排序要求 $u$ 一定在 $v$ 之前，一定不能出现 $v$ 在 $u$ 之前的排序结果。由此可以看出，拓扑排序存在的前提是 **有向图无圈**。且只要图为 $DAG$ (Directed Acyclic Graph, 有向无圈图)，则该图 **至少存在一种拓扑排序结果** 。此外，是否存在拓扑排序与图是否存在不连通的分量无关，这是显然的，因为互不连通的分量互不依赖，在拓扑排序中这些分量的顺序是任意的。

拓扑排序的主要实现为基于 $BFS$ 的 **「Kahn算法」** 以及基于 $DFS$ 的 **「Tarjan拓扑排序算法」** 。我们将看到，这两种算法实现的拓扑排序在求解过程上是 **「互逆」** 的。wiki 中对拓扑排序有如下 **更准确的表述** ，后续我们会再次提到该「表述」。

> Precisely, a topological sort is a graph traversal in which each node $v$ is visited only after all its dependencies are visited. 
>
> 更准确地，拓扑排序是对图的一种遍历，在这种遍历中，对一个顶点 $v$ 的访问只发生在它所依赖的顶点被访问之后。

※ 大家思考过为什么这种排序要冠以「拓扑」之名吗？根据作者有限的了解，「拓扑学 (Topology)」研究的是平面或立体图形 (多维?) 连续变形过程中的性质。说一个什么事物是「拓扑的 (Topological)」似乎在表达这个事物变形前后的关系，看起来「拓扑排序」跟数学上的「拓扑」并没有什么关联，因为点或边或整张图并未有什么变化。查了一下，这篇讨论 [Why is "topological sorting" topological?](https://cstheory.stackexchange.com/questions/30659/why-is-topological-sorting-topological) 的高赞回答表示该命名大概只是想体现 "network topology" 的味道 (sense)。

作者点评: 适当地探索一个技术名词的「语源」，能够加深我们对其的理解 🤔。

在前一节中，我们提到「图判圈」问题，也就是 [684. 冗余连接](https://leetcode.cn/problems/redundant-connection/) 和 [207. 课程表](https://leetcode.cn/problems/course-schedule/) 两题可通过「拓扑排序」解决，且时间复杂度为 $O(|V|+|E|)$。但解决的过程中并不会真正地「排序」。为了能体现完整的拓扑排序算法，我们先以 [210. 课程表 II](https://leetcode.cn/problems/course-schedule-ii/) 一题为分析对象，该题目描述的内容常作为介绍拓扑排序的一个经典的现实例子 (具体看原题描述)。在本节最后再给出 684 和 207 题的「拓扑排序」解法，在学完本节后，相应解法是很容易写出的。更多「拓扑排序」相关题目请参考「实战应用」。

### Kahn

#### 算法描述

[Kahn算法](https://en.wikipedia.org/wiki/Topological_sorting)：基于 $BFS$ 的拓扑排序算法。之前我们提到过「拓扑排序准确表述」，该算法通过 **入度** 这一概念很好地体现了「表述」，即当访问一个顶点 $v$ ，若其 **「入度」** 为 0 ，即说明它所依赖的所有顶点一定已经被访问过了，此时即可将其输出 (将其排序)。具体来说，先计算所有顶点的入度，然后将入度为 0 的顶点放入队列中，从队列输出队首顶点并依次将其所有 **邻接顶点入度减 1** ，每一个邻接顶点入度减 1 后，判断其入度是否减至 0 ，若为 0 将其入队。重复上述过程，直到队列为空 (所有顶点均已入队又出队) 。容易看出，一个顶点入度减至 0 ，**当前仅当** 它所依赖的顶点的入度在此之前已减至 0。算法结束时，顶点出队的顺序即为拓扑排序，这是一个 **「顺序」** 拓扑排序过程。

判圈: 某个节点出队时对其存在的邻边入度减 1 后，若这些邻边入度均未减至 0，则说明该图 **有圈** 。可以通过在 $while$ 结束后考察 **出队顶点数与总顶点数是否相等** 来判圈。

> A. B. Kahn于1962年发表的 [*Topological Sorting of Large Networks* ](https://dl.acm.org/doi/pdf/10.1145/368996.369025) 论文中描述了该算法。

#### 算法过程

算法的详细过程如下，也即该算法求解拓扑排序问题时的编程范式。具体代码见「代码」部分，在参考之前，你应当通过此处给出的算法过程尝试自己写出。

1. 根据输入建图及计算入度。

2. 建图。

3. 计算入度。

入度信息一般用大小为顶点数的数组 $indegrees[]$ 表示，入度计算通常与建图同时进行。遍历输入信息，遇到边 $(u, v)$ 时，执行 `indegree[v]++` 。当所有边都被考察后，入度信息即已完备。

4. 拓扑排序。
   有了入度信息和图信息，开始拓扑排序。

1. 设置一个队列 $q$ 、一个用于保存拓扑排序结果的列表 $res$ 、一个用于后续判断图是否有圈的计数变量 $count$ 。
   2. 遍历 $indegrees$ 数组将入度为 0 的顶点入队 (若已知图为有向无圈 **连通图** ，则 **有且只有一个** 顶点入度为 0，可在找到后立即跳出遍历)。
   3. 以一个 $while$ 检查当前队列是否为空，不空则队首顶点 $u$ 出队，放入输出结果 $res$ 中。同时 `count++` ，表明 $u$ 已被排序。
   4. 遍历 $u$ 的邻接顶点 $v$ ，使 $v$ 的入度减 1，并检查减 1 后是否为 0 ，为 0 则 $v$ 入队。
   5. 当 $while$ 结束后，在返回前判圈。 **图有圈则存在入度不可能减至 0  的顶点** ，则已拓扑排序 (已出队) 的顶点个数 $count$ 必小于顶点总数。若满足 $count == n$ 则返回拓扑排序结果，否则无结果。

#### 时空复杂度

**时间复杂度:**

1. 建图及计算所有顶点入度需遍历所有边，时间复杂度为 $O(|E|)$。
2. 队列中每个顶点均入队一次，出队一次，$O(|V|)$ 。
3. 更新并检查邻接顶点的 $for$ 中，更新和检查的总次数等于边数 $O(|E|)$ 。

故总的时间复杂度为 $O(|V|+|E|)$ 。此时间复杂度体现了图的规模，因此也称之为图的 **线性时间复杂度** 。 若图是连通的 ，由于 $|E| ≥ |V|$ (仅在图为链状有向图时 $|E| = |V| - 1$)，因此通常也可以粗略地记做 $O(|E|)$ 。

**空间复杂度:** 存图空间 $O(|V|+|E|)$ ， $res / indegrees$ 空间 $O(|V|)$，队列空间 $O(|V|)$。总体为线性空间复杂度 $O(|V|+|E|)$ 。

#### 代码

Kahn 拓扑排序算法实现 [210. 课程表 II](https://leetcode.cn/problems/course-schedule-ii/) 。在掌握了 $BFS$ 算法写法及理解 Kahn 算法过程的基础上，我们很容易写出如下代码。

第一份代码以 **哈希表** 存图，适合于无法用连续的整数来表示顶点的场景。本题中，顶点可以被表示为 $\{0, 1,2,3,...n - 1\}$ ，因此采用第二份以 **线性表** 存图的代码效率更高。此写法为普遍的标准的 Kahn 拓扑排序写法，读者应对该写法 **熟稔于心** 。

```java
// 以HashMap存图
class Solution {
 public int[] findOrder(int numCourses, int[][] prerequisites) {
 // 1. 【建图 + 计算入度】
 int[] res = new int[numCourses], indegrees = new int[numCourses];
 Map<Integer, List<Integer>> graph = new HashMap<>();
 for(int[] edge : prerequisites){ // 建图 & 计算入度
 int v = edge[0], u = edge[1]; // u是v的先修课程, u -> v
 List<Integer> adjs = graph.getOrDefault(u, new ArrayList<>()); // u的邻接表
 adjs.add(v); // v为u的邻接顶点
 graph.put(u, adjs);
 indegrees[v]++; // v的入度加1
 }
 // 2. 【拓扑排序】
 // 2-1. 遍历入度数组，将入度为 0 的顶点入队。
 int count = 0;
 Queue<Integer> q = new ArrayDeque<>();
 for(int u = 0; u < numCourses; u++){ // 找到入度为0的顶点并入队
 if(indegrees[u] == 0) q.add(u);
 }
 // 2-2. 利用队列完成拓扑排序
 while(!q.isEmpty()){
 int u = q.remove();
 res[count++] = u; // 入度为0，输出到res，同时count++
 List<Integer> adjs = graph.get(u);
 if(adjs != null){ // 有的顶点可能无邻接顶点
 for(int v : adjs){
 indegrees[v]--; // v的入度减1
 if(indegrees[v] == 0) q.add(v);
 }
 }
 }
 // 2-3. 返回前判圈。
 return count == numCourses ? res : new int[]{}; 
 }
}
```

```java
// 以List存图
class Solution {
 public int[] findOrder(int numCourses, int[][] prerequisites) {
 int[] res = new int[numCourses];
 // 1. 【建图 + 计算入度】
 List<List<Integer>> graph = new ArrayList<>();
 for(int i = 0; i < numCourses; ++i){
 graph.add(new ArrayList<>());
 }
 int[] indegrees = new int[numCourses];
 for(int[] edge : prerequisites){ // 计算入度 & 建图
 int u = edge[1], v = edge[0];
 indegrees[v]++;
 graph.get(u).add(v);
 }
 // 2. 【拓扑排序】
 // 2-1. 遍历入度数组，将入度为 0 的顶点入队。
 Queue<Integer> q = new ArrayDeque<>();
 for(int u = 0; u < numCourses; ++u){ // 初始化队列 q
 if(indegrees[u] == 0) q.add(u); // 初始入度为 0 的顶点入队
 }
 // 2-2. 利用队列完成拓扑排序
 int count = 0;
 while(!q.isEmpty()){
 int u = q.remove(); // 队首 u 出队
 res[count] = u; // 写入拓扑排序结果
 count++; // 累计已完成拓扑排序的顶点数量
 for(int v : graph.get(u)){
 indegrees[v]--; // 调整入度
 if(indegrees[v] == 0) q.add(v); // 若 v 的入度减至 0，入队
 }
 }
 // 2-3. 返回前判圈。
 return count == numCourses ? res : new int[]{}; // 判圈
 }
}
```

### Tarjan (Topological Sorting)

#### 算法描述

[Tarjan拓扑排序算法](https://en.wikipedia.org/wiki/Topological_sorting)：基于 $DFS$ 的拓扑排序算法。回顾之前提到的「拓扑排序准确表述」中的「对一个顶点 $v$ 的访问只发生在它所依赖的顶点被访问之后」，我们从中可以嗅到「层层深入」的味道，即对于 $v$ ，「层层深入」它所依赖的顶点后访问到它，这是一个 $dfs$ 的过程，「表述」中要求，完成 $v$ 的访问的前提是完成它所依赖的顶点的访问，那么我们可以在 $dfs$ 到 $v$ 的过程中，**「缓存」** 路径上 $v$ 所依赖的顶点的状态 (即暂不处理)，当我们要处理 $v$ 的时候，已经保证了它所依赖的顶点会在此后「回溯」的过程中处理，因为它们此刻都在 **递归栈的更靠顶部的空间中 (也就是在返回路径上)** 缓存着。换句话说，我们只需要将 $v$ 放在当前用于存放拓扑排序结果的空间的最后侧 (这是栈的特点，我在这里称其为「排序结果栈」)，此后的回溯一定会将它所依赖的顶点放在它的前面。那么我们什么时候处理 $v$ 呢？自然是无法从它再深入到任何顶点的时候，可以是其无 (依赖关系的) 后继顶点时，也可以是其后继顶点均已被排序 (被放入结果栈中) 时。理解了这一点，我们即可给出如下 Tarjan 拓扑排序的主要过程。建图过程无需多言。

顶点在算法过程中有三个状态， **未搜索，搜索中、已完成 (访问)** 。算法从遍历顶点开始，每遇到一个「未搜索」的顶点 $u$ ，就以其为起点开始 $dfs$ 。进入 $dfs$ 方法时我们首先将 $u$ 标记为「搜索中」，然后以 $for$ 循环依次考察 $u$ 的邻接顶点 $v$ 。

- 若其状态为「未搜索」，对其递归调用 $dfs$ ，重复前述过程。
- 若其状态为「搜索中」，表明我们此前进入过 $v$ 的 $dfs$ 过程，而此时又遇到了 $v$ ，显然 $v$ 是通过一个圈回到了 $v$。于是将 $hasCycle$ 标记为 $true$ 并返回。
- 注意我们不必处理「已完成」的 $v$ ，无判断分支会直接跳过。

如前一段所说，当 $u$ 无法再深入到任何顶点时，我们标记其状态为「已完成」。每以一个「未搜索」的顶点为起点完成 $dfs$ 后，检测一次 $hasCycle$ 是否为 $true$，是则结束，否则当程序终止时，顺序输出结果栈即为正确的拓扑排序。

> 该算法并不总是被冠以 Tarjan 之名，在 wiki 中有下面这段话，注意「...seems to...」。另外，Cormen et al. (2001) 指的是那本著名的「算法导论」。
>
> This depth-first-search-based algorithm is the one described by [Cormen et al. (2001)](https://en.wikipedia.org/wiki/Topological_sorting#CITEREFCormenLeisersonRivestStein2001), it seems to have been first described in print by Tarjan in [1976](https://link.springer.com/article/10.1007/BF00268499).

※ 之所以称「Tarjan拓扑排序算法」而非「Tarjan算法」，是因为由 [Tarjan](https://en.wikipedia.org/wiki/Robert_Tarjan) 发明或合作发明或有重大贡献的算法和数据结构非常之多，如「[最近公共祖先(LCA)](https://en.wikipedia.org/wiki/Lowest_common_ancestor#History)」、「[强连通分量(SCC)](https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm#cite_note-Tarjan-1)」、「[伸展树 (Splay Tree)](https://en.wikipedia.org/wiki/Splay_tree)」、「[斐波那契堆 (Fibonacci Heaps)](https://en.wikipedia.org/wiki/Fibonacci_heap)」、「[并查集 (Union-Find Set)](https://en.wikipedia.org/wiki/Disjoint-set_data_structure)」等等。狭义上的「Tarjan算法」指的是「强连通分量」算法。实际上将基于 $BFS$ 的拓扑排序算法冠以 Kahn 之名比之将基于 $DFS$ 的拓扑排序冠以 Tarjan 之名更为流行，原因除了前者发明时间更早，且更易于理解之外，还在于后者只是 Tarjan 所发明的寻找「强连通分量」算法的副产品，而未作为一个独立的算法发表 (由此也可见 Tarjan 之强大)。详见 [Does Tarjan's SCC algorithm give a topological sort of the SCC?](https://stackoverflow.com/questions/32750511/does-tarjans-scc-algorithm-give-a-topological-sort-of-the-scc)。

> ... And his algorithm (SCC) also does topological sorting **as a byproduct**. ---- by Knuth

#### 算法过程

1. 根据输入建图及准备 $visited$ 数组、 $hasCycle$ 布尔值、拓扑排序结果栈 $res$ 以及栈底下标 $idx$ (初始时为 $|V| - 1$)。

1. 建图。与 kahn 算法一致。

2. $visited$ 数组下标为顶点，有三种取值，表示顶点在拓扑排序过程中的三种状态。0: 未搜索 1: 搜索中 2: 已完成 (搜索)。初始时 $hasCycle = false$ 。

2. 拓扑排序。遍历所有顶点，对「未搜索」状态的顶点 $u$ 执行 $dfs$ 。

1. 进入 $dfs$ 后，首先置 $visited[u] = 1$，表示 $u$ 处于搜索中状态。
   2. 以 $for$ 循环依次考察 $u$ 的邻接顶点 $v$ 。
      1. 若 $visited[v] == 0$ ，状态为「未搜索」。对其递归调用 $dfs$ ，也就是看它是否是其他顶点的「依赖」，使其置于「缓存」之中。
      2. 若 $visited[v] == 1$ ，状态为「搜索中」。表明我们此前进入过 $v$ 的 $dfs$ 过程，而此时又遇到了 $v$ ，显然 $v$ 是通过一个圈回到了 $v$。于是将 $hasCycle$ 标记为 $true$ 并返回。
      3. 若 $visited[v] == 2$ ，状态为「已完成」。跳过。
   3. 对于 $u$，若其完成了 $for$，表明要么其无 (依赖关系中的) 后继顶点，要么其后继顶点均已被排序 (被放入结果栈中)。也就是 $u$ 是当前所有未完成排序的顶点中位于依赖关系最后面的顶点，于是将其放入当前结果栈中的的底部。

3. 若能完成所有顶点的遍历而无圈，说明所有顶点已被拓扑排序，返回 $res$。

#### 时空复杂度

**时间复杂度:**

1. 建图及需遍历所有边，时间复杂度为 $O(|E|)$。

每个顶点至多被标记两次，$O(|V|)$ 。

2. 检查邻接顶点的 $for$ 的总次数等于边数 $O(|E|)$ 。

故总的时间复杂度为同 Kahn 算法一样也是线性时间复杂度 $O(|V|+|E|)$ 。若图是连通的 ，由于 $|E| ≥ |V|$ (仅在 $|V| = 2$，且只有一条边时 $|E| < |V|$)，因此通常也可以粗略地记做 $O(|E|)$ 。

**空间复杂度:** 存图空间 $O(|V|+|E|)$ ， $res / visited$ 空间 $O(|V|)$，递归栈空间 $O(|V|)$。总体为线性空间复杂度 $O(|V|+|E|)$ 。

#### 代码

Tarjan 拓扑排序算法实现 [210. 课程表 II](https://leetcode.cn/problems/course-schedule-ii/) 。此写法为普遍的标准的 Tarjan 拓扑排序写法，读者应对该写法 **熟稔于心** 。

```java
class Solution {
 List<List<Integer>> graph;
 int[] visited, res;
 boolean hasCycle = false;
 int idx;
 public int[] findOrder(int numCourses, int[][] prerequisites) {
 // 1. 建图 + 准备 visited / hasCycle / res / idx
 this.graph = new ArrayList<>();
 this.visited = new int[numCourses]; // 0: 未搜索 1: 搜索中 2: 已完成
 this.res = new int[numCourses]; // 存储拓扑排序结果的栈
 this.idx = numCourses - 1; // 栈底下标
 for(int i = 0; i < numCourses; i++) {
 graph.add(new ArrayList<>());
 }
 for(int[] edge : prerequisites){ // 建图
 int v = edge[0], u = edge[1]; // 要学习v先学习u，因此 u -> v
 graph.get(u).add(v);
 }
 // 2. 遍历所有顶点，对「未搜索」状态的顶点 u 执行 dfs
 for(int u = 0; u < numCourses; u++){
 if(visited[u] == 0) { // 对未搜索的顶点执行 dfs
 dfs(u);
 if(hasCycle) return new int[]{}; // 每次搜索后，若检测出圈，返回空数组
 }
 }
 return res;
 }
 private void dfs(int u){
 if(hasCycle) return;
 visited[u] = 1; // 立即标记为搜索中
 for(int v : graph.get(u)) {
 if(visited[v] == 0) dfs(v); // 邻接顶点为「未搜索」状态，dfs之
 else if(visited[v] == 1) { // 若邻接顶点为「搜索中」状态，说明有圈
 hasCycle = true;
 return;
 }
 }
 visited[u] = 2; // 完成搜索，表明在对u进行dfs的过程中未遇到正在搜索中的其他顶点
 res[idx--] = u; // 此时u所依赖的顶点都在栈中「缓存」等待后续处理，因此可以将其放入此时结果栈中的底部。
 }
}
```

### 拓扑排序判圈

在学习了本节内容后，我们再回到 [684. 冗余连接](https://leetcode.cn/problems/redundant-connection/) 和 [207. 课程表](https://leetcode.cn/problems/course-schedule/) 这两题的，给出它们的拓扑排序解法。需要注意的是，应用 Kahn 拓扑排序时，对于「无向图」上的顶点，考虑的是无关方向的 **「度」** ，开始排序时要将 **度为 1** 的顶点入队；对于「有向图」上的顶点，考虑的是 **「入度」** ，开始排序时要将 **入度为 0** 的顶点入队。

#### 无向图判圈

对于 684 题，因为题目要求返回构成圈的在 $edges$ 中的最后一条边，因此只「判圈」还不够，若应用 Kahn 拓扑排序算法，则排序结束后可根据度大于 1 的顶点信息，在 $edges$ 中找到符合要求的最后的那条边。 **若只要求判圈，那么也可以采用Tarjan拓扑排序算法** 。如下我们只给出 Kahn 排序算法解 684 题的代码。

- 时间复杂度: 由于本题  $|V| = |E|$，因此拓扑排序时间复杂度为 $O(|V|)$，排序结束后在 $edges$ 中寻找「构成圈的最后一条边」的时间复杂度为 $O(|V|)$ 。
- 空间复杂度: 存图空间 $O(|V|)$ ， $degrees$ 空间 $O(|V|)$，队列空间 $O(|V|)$。总体为线性空间复杂度 $O(|V|)$ 。

```java
class Solution {
 public int[] findRedundantConnection(int[][] edges) {
 int n = edges.length;
 int[] degrees = new int[n];
 List<List<Integer>> graph = new ArrayList<>();
 for(int i = 0; i < n; i++) graph.add(new ArrayList<>());
 for(int[] edge : edges){ // 建图 + 计算顶点的度
 int u = edge[0] - 1, v = edge[1] - 1;
 degrees[u]++; // u 的度加 1
 degrees[v]++; // v 的度加 1
 graph.get(u).add(v);
 graph.get(v).add(u);
 }
 Queue<Integer> q = new ArrayDeque<>();
 for(int i = 0; i < n; i++) { // 度为 1 的顶点入队
 if(degrees[i] == 1) q.add(i);
 }
 while(!q.isEmpty()){ // 拓扑排序过程
 int u = q.remove();
 for(int v : graph.get(u)){
 degrees[v]--;
 if(degrees[v] == 1) q.add(v);
 }
 }
 for(int i = n - 1; i >= 0; i--){ // 在 edges 中从后往前寻找圈上的边，该边的两个顶点的度均大于1
 int u = edges[i][0] - 1, v = edges[i][1] - 1;
 if(degrees[u] > 1 && degrees[v] > 1){
 return new int[]{u + 1, v + 1};
 }
 }
 return null; // 本题保证必有解
 }
}
```

#### 有向图判圈

对于 [207. 课程表](https://leetcode.cn/problems/course-schedule/) 题，其拓扑排序解法与 [210. 课程表 II](https://leetcode.cn/problems/course-schedule-ii/) 题的区别仅在于前者无需真正排序，只需判断是否存在圈即可。以下给出 Kahn 和 Tarjan 两种拓扑排序算法的代码。

**Kahn拓扑排序算法**

- 时间复杂度: 拓扑排序时间复杂度为 $O(|V|+|E|)$ 。
- 空间复杂度: 存图空间 $O(|V|+|E|)$ ， $indegrees$ 空间 $O(|V|)$，队列空间 $O(|V|)$。总体为线性空间复杂度 $O(|V|+|E|)$ 。

```java
// Kahn拓扑排序
class Solution {
 public boolean canFinish(int numCourses, int[][] prerequisites) {
 List<List<Integer>> graph = new ArrayList<>();
 int[] indegrees = new int[numCourses];
 for(int i = 0; i < numCourses; i++) {
 graph.add(new ArrayList<>());
 }
 for(int[] edge : prerequisites){ // 建图 & 计算入度
 int v = edge[0], u = edge[1]; // 要学习v先学习u，因此 u -> v
 graph.get(u).add(v);
 indegrees[v]++;
 }
 Queue<Integer> q = new ArrayDeque<>();
 for(int u = 0; u < numCourses; u++){ // 入度为0的顶点入队
 if(indegrees[u] == 0) q.add(u);
 }
 int count = 0; // 已拓扑排序的顶点数
 while(!q.isEmpty()){ // 拓扑排序
 int u = q.remove();
 count++;
 for(int v : graph.get(u)){
 indegrees[v]--;
 if(indegrees[v] == 0) q.add(v);
 }
 }
 return count == numCourses;
 }
}
```

**Tarjan拓扑排序算法**

- 时间复杂度: 拓扑排序时间复杂度为 $O(|V|+|E|)$ 。
- 空间复杂度: 存图空间 $O(|V|+|E|)$ ， $visited$ 空间 $O(|V|)$，递归栈空间 $O(|V|)$。总体为线性空间复杂度 $O(|V|+|E|)$ 。

```java
// Tarjan拓扑排序
class Solution {
 List<List<Integer>> graph;
 int[] visited;
 boolean hasCycle = false;
 public boolean canFinish(int numCourses, int[][] prerequisites) {
 this.graph = new ArrayList<>();
 this.visited = new int[numCourses]; // 0: 未搜索 1: 搜索中 2: 已完成
 for(int i = 0; i < numCourses; i++) {
 graph.add(new ArrayList<>());
 }
 for(int[] edge : prerequisites){
 int v = edge[0], u = edge[1]; // 要学习v先学习u，因此 u -> v
 graph.get(u).add(v);
 }
 for(int u = 0; u < numCourses; u++){
 if(visited[u] == 0) {
 dfs(u);
 if(hasCycle) return false; // 每次搜索后，若检测出圈，返回false
 }
 }
 return true;
 }
 private void dfs(int u){
 if(hasCycle) return;
 visited[u] = 1; // 搜索中
 for(int v : graph.get(u)) {
 if(visited[v] == 0) dfs(v);
 else if(visited[v] == 1) {
 hasCycle = true;
 return;
 }
 }
 visited[u] = 2; // 完成搜索，表明在对u进行dfs的过程中未遇到正在搜索中的其他顶点
 }
}
```

### 小结

在本节中，我们分别介绍了基于 $bfs$ 的 Kahn 算法和基于 $dfs$ 的 Tarjan 拓扑排序算法，并给出了这两种方法解决 [210. 课程表 II](https://leetcode.cn/problems/course-schedule-ii/) 一题的代码。我们还展示了利用「拓扑排序」，可以在「图判圈」这一问题上，实现线性时间复杂度求解，比「初探图搜索 (遍历)」一节的方法更好，显示了拓扑排序这一方法的优点。在之后的章节中，我们还会看到拓扑排序是如何继续发挥作用的。

## 最短路径

本节我们将学习图论算法中古老而经典的「[最短路径](https://en.m.wikipedia.org/wiki/Shortest_path_problem)」问题，该算法在地图、交通等许多领域中的重要性无须多言。我们将按照如下三大类进行讲解。

- **无权单源最短路：** *(Single Source Shortest Path, SSSP)* 给定一张无权图 $G$ 和一个顶点 $s$ ，找出从 $s$ 到 $G$ 中每一个顶点的最短路径。
- **带权单源最短路：** *(Single Source Shortest Path, SSSP)* 给定一张带权图 $G$ 和一个顶点 $s$ ，找出从 $s$ 到 $G$ 中每一个顶点的最短路径。

- **带权全源最短路：** *(All Pairs Shortest Path, APSP)* 给定一张带权图 $G$  ，找出 $G$ 中所有点对的最短路径。

我们指出，除了特定情形的图 (如 DAG)， 最短路径算法不区分图的边是否有向，建图时对有向图/无向图正确建图即可 (有向图单向建边，无向图双向建边)。为了使读者在学习过程中及时地得到反馈，我将在介绍每一种算法后，利用该算法实际解决如下对应题目。读者应当在理解算法内容之后尝试独立求解，然后再与文中给出的代码相比照。

| 最短路分类 | 配套例题 |
| -------------- | ------------------------------------------------------------ |
| 无权单源最短路 | 814. 无向图中的最短路径 |
| 带权单源最短路 | [743. 网络延迟时间](https://leetcode.cn/problems/network-delay-time/) |
| 带权全源最短路 | [743. 网络延迟时间](https://leetcode.cn/problems/network-delay-time/) [1334. 阈值距离内邻居最少的城市](https://leetcode.cn/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/) |

### 无权单源最短路

我们首先介绍最简单的「无权单源最短路」，力扣上似乎没有相应的题目，不过力扣友商平台上的 **814.无向图中的最短路径** 一题比较匹配 (请自行搜索)，我们通过这题来学习本节。虽然该题只须求给定两点之间的最短距离，但我们仍然按给定一点 (源点 $s$)，求其到其他所有顶点的距离来做，最后只须返回指定顶点的距离即可。

需要注意的是，本小节给出的例题的图虽是无向图，但有向图解法是一致的。「有向无权单源最短路」与「无向无权单源最短路」的求解方法的唯一区别只在与建图时是双向建边 (无向图) 还是单向 (有向图) 建边。后续「带权图」的最短路问题也一样，有向无向并不影响算法过程，因此 **对于「最短路」问题，通常不强调「无向」还是「有向」** 。

#### 朴素版

虽然我们早已熟悉利用队列来辅助 $bfs$ 过程的写法，但我还是决定先介绍不用队列的 **朴素版本** ，以此为契机再次感受使用队列实现 $bfs$ 的优点。如果你确信自己理解了这一点，你也可以跳过「朴素版」直接看「队列优化版」。

##### 算法描述

在熟悉 $bfs$ 泛洪算法后我们很容易想到无权单源最短路的解法。从源点 $s$ 开始，以 $bfs$ 方式确定 $s$ 到其他所有顶点的最短路径。首先，程序主体为一个使得距离 (指源点到其他顶点的距离，此后若无特别说明，「距离」一词均为此意) 能够按层推进的 $for$ 循环，`for(int dist = 0; dist < |V| - 1; dist++)` ，$dist = 0$ 表示一开始距离为 0 ，此后会逐层增加距离。该 $for$ 内接着一个内层 $for$ 循环，用于 **遍历所有顶点** ，找到那些 **距离已确定** 且为当前 $dist$ 顶点 $u$。对每一个 $u$ ，再以一个 $for$ 循环遍历它的邻接顶点 $v$ ，使那些 **距离未确定** 的 $v$ 的距离为 $dist + 1$。这样就能够按层推进访问所有顶点并确定这些顶点的距离。

具体来说，对于 $s$ ，首先置其距离为 0，然后开始外层 $for$ 。遍历顶点后只有 $s$ 满足条件，于是其 **邻接顶点** 的距离 +1，(如果要求返回具体路径，可以在此时将其前驱顶点置为 $s$ ，以便将来用于返回路径)。接着遍历顶点，对上一层顶点，也就是之前距离被置为 1 的顶点 $u$ 考察它们的 **距离未确定** 的邻接顶点 $v$ ，使 $v$ 的距离 +1，(如前，若需要，此时将 $v$ 的前驱顶点置为 $u$ )。以 $for$ 循环重复上述过程，循环开始时 $dist = 0$，循环次数上限为顶点个数减 1，每次执行后 $dist+1$，表示距离不断按层递增，且距离 $≤|V|-1$ (当图为链状时取到最大距离，为 $|V|-1$ )。

##### 算法过程

1. 设置一个用于泛洪标记 (访问状态) 的 $visited$ 哈希表，一个记录所有顶点距离的哈希表 $dists$ 。
2. 置给定源点 $s$ (题中的 $A$) 的距离为 0，并立即置其为「已访问」。
3. 外层 (第一层) $for$ 循环按距离递增。初始 $dist=0$ ，以 $|V| - 1$ 为最大遍历次数，每次 $dist$ 加 1，表示距离以 1 为单位不断递增，最大不超过 $|V|-1$。
   1. 第二层 $for$ 循环遍历所有顶点，找到距离已确定且为 $dist$ 的顶点 $u$ (即刚刚处理完的上一层顶点)。
      1. 第三层 $for$ 循环遍历 $u$ 的邻接顶点 $v$ ，置其中距离未确定的 $v$ 的距离为 $dist+1$ 。(若有需要，可在此时置 $v$ 的前驱为 $u$ ，本题不需要)。

4. 最外层 $for$ 循环结束后所有顶点距离被确定，算法结束。

※ 该题的输入中，顶点的 $label$ 虽是唯一的，但并不连续，因此对于 $visited$ 和 $dists$ ，不适合用我们之前已经习惯的数组来表示，改用哈希表表示。另外，此题输入已经给出了图的完整邻接表信息，无需建图过程。

##### 时空复杂度

时间复杂度：虽然程序有三层循环，但总体的效果是对所有顶点询问一次它们的邻接顶点，并不总能进入第三层，因此时间复杂度取决于前两层 $for$  的时间复杂度，为 $O(|V|^2)$ 。

空间复杂度： 存图空间 $O(|V|+|E|)$ (本题已给出，实际上无需此空间)， $visited/dists$ 空间 $O(|V|)$。总体为线性空间复杂度 $O(|V|+|E|)$  (对于本题实际上是 $O(|V|)$ )。

##### 代码

```java
/**
 * Definition for Undirected graph.
 * class UndirectedGraphNode {
 * int label;
 * List<UndirectedGraphNode> neighbors;
 * UndirectedGraphNode(int x) {
 * label = x;
 * neighbors = new ArrayList<UndirectedGraphNode>();
 * }
 * }
 */

public class Solution {
 public int shortestPath(List<UndirectedGraphNode> graph, UndirectedGraphNode A, UndirectedGraphNode B) {
 if(A == B) return 0; // 特判
 int n = graph.size(), a = A.label, b = B.label;
 Set<Integer> visited = new HashSet<>();
 Map<Integer, Integer> dists = new HashMap<>();
 dists.put(a, 0); // 首先置源点距离为0
 visited.add(a); // 立即置为已访问
 for(int dist = 0; dist < n - 1; dist++){ // 按层推进
 for(UndirectedGraphNode uNode : graph){ // 遍历顶点
 int u = uNode.label;
 if(visited.contains(u) && dists.get(u) == dist){ // 寻找刚确定好距离的上一层顶点
 for(UndirectedGraphNode vNode : uNode.neighbors){
 int v = vNode.label;
 if(!visited.contains(v)) { // 距离未确定的v
 dists.put(v, dist + 1); // 确定当前层顶点的距离
 visited.add(v); // 立即置为已访问
 }
 }
 }
 }
 } // 外层for结束后求得源点A到所有顶点的距离
 return visited.contains(b) ? dists.get(b) : -1;
 }
}
```

#### 队列优化版

##### 算法描述

朴素版做法的明显缺点是在程序运行到后期，大部分顶点的距离已确定，但每次距离加 1 后，仍要遍历所有顶点，我们已经知道使用队列可以优化这部分时间。从源点 $s$ 开始执行 $bfs$ ，一开始将 $s$ 放入队列中。每次处理一层顶点，在一个 $for$ 循环内依次将该层顶点出队，对每一个当前层的顶点 $u$ ，遍历它的邻接顶点 $v$ ，只要它未被标记为「已访问」，则它是下一层顶点，此时即可赋予其当前距离，此距离每处理一层增加 1，将 $v$ 入队并置 $v$ 为「已访问」。当 $q$ 中顶点全都出队时，我们就得到了 $s$ 到所有顶点的最短路径距离。

##### 算法过程

1. 设置一个队列 $q$ ，一个用于泛洪标记 (访问状态) 的 $visited$ 哈希表，一个记录所有顶点距离的哈希表 $dists$ 。
2. 首先将源点 $s$ 入队，并立即置其访问状态为「已访问」。
3. 执行 $while(!q.isEmpty())$ ，开始 $bfs$ 泛洪。每次以一个 $for$ 循环处理 **一层** 顶点，$dist++$ ，表示当前层的距离。
   1. 对每一个当前层的顶点 $u$ ，以一个 $for$ 循环遍历它的邻接顶点 $v$ ，只要它未被标记为「已访问」，则它是下一层顶点，此时即可赋予其当前距离，将 $v$ 入队 并置 $v$ 为「已访问」。
4. 当 $q$ 中顶点全都出队时，我们就得到了 $s$ 到所有顶点的最短路径距离。

##### 时空复杂度

时间复杂度: $BFS$ 一次泛洪的时间复杂度 $O(|V|+|E|)$ 。可如此分析: 每个顶点均入队一次出队一次，时间复杂度为 $O(|V|)$ ，每个顶点都会遍历其邻接顶点，总的来看就是总边数，时间复杂度为 $O(|E|)$。因此总时间复杂度为线性时间复杂度 $O(|V|+|E|)$ 。

空间复杂度: 存图空间 $O(|V|+|E|)$ (本题已给出，实际上无需此空间)， $visited/dists/q$ 空间 $O(|V|)$。总体为线性空间复杂度 $O(|V|+|E|)$  (对于本题实际上是 $O(|V|)$ )。

##### 代码

给出如下代码。由于该题的输入中，顶点的 $label$ 虽是唯一的，但并不连续，因此对于 $visited$ 和 $dists$ ，用哈希表来代替数组。该题入参 $graph$ 已经包含了完整的邻接表信息，无需再建图。

```java
public class Solution {
 public int shortestPath(List<UndirectedGraphNode> graph, UndirectedGraphNode A, UndirectedGraphNode B) {
 if(A == B) return 0;
 int n = graph.size(), dist = 0, a = A.label, b = B.label;
 Set<Integer> visited = new HashSet<>(); // 用set来存放已访问元素
 HashMap<Integer, Integer> dists = new HashMap<>(); // 用哈希表记录每个顶点的距离
 Queue<UndirectedGraphNode> q = new ArrayDeque<>();
 q.add(A);
 visited.add(a); // 将源点置为「已访问」
 while(!q.isEmpty()){ // 泛洪
 dist++; // 当前层顶点的「距离」
 int size = q.size();
 for(int i = 0; i < size; i++){ // 一次处理一层
 UndirectedGraphNode uNode = q.remove();
 for(UndirectedGraphNode vNode : uNode.neighbors){
 int v = vNode.label;
 if(!visited.contains(v)){ // 若v「未访问」
 dists.put(v, dist); // v的距离在此时确定
 q.add(vNode);
 visited.add(v); // 立即置为「已访问」
 }
 }
 }
 }
 return visited.contains(b) ? dists.get(b) : -1;
 }
}
```

如果只是为了求解该题，无需记录所有顶点的距离，只要遇到顶点 $B$，返回当前距离即可，如下。(有意思的是用数组 $visited$ 也能通过所有样例，不过这不重要。)

```java
public class Solution {
 public int shortestPath(List<UndirectedGraphNode> graph, UndirectedGraphNode A, UndirectedGraphNode B) {
 if(A == B) return 0; // 特判
 int n = graph.size(), dist = 0;
 boolean[] visited = new boolean[n + 1];
 Queue<UndirectedGraphNode> q = new ArrayDeque<>();
 q.add(A);
 visited[A.label] = true;
 while(!q.isEmpty()){
 dist++;
 int size = q.size();
 for(int i = 0; i < size; i++){
 UndirectedGraphNode uNode = q.remove();
 for(UndirectedGraphNode vNode : uNode.neighbors){
 int v = vNode.label;
 if(vNode == B) return dist;
 else if(!visited[v]){
 q.add(vNode);
 visited[v] = true;
 }
 }
 }
 }
 return -1;
 }
}
```

### 带权单源最短路

当图为有权图时，我们将无法简单地通过层数增加来确定每一层顶点的距离，因为从源点若有多条路径可到达顶点 $v$，更深的路径完全可以比更浅的路径具有更短的路径长 (路径上的边的权之和) 。本节我们将学习几种不同的 **「带权单源最短路」** 算法来求解经典的带权单源最短路问题 [743. 网络延迟时间](https://leetcode.cn/problems/network-delay-time/) 。再次强调，图「有向」或「无向」，对于这些算法，区别仅在于建图时为双向边还是单向边，除非特别说明 (例如 DAG )，否则 **最短路算法不区分有向图或是无向图** 。

#### Dijkstra

一种基于贪心思想的求解 **无负边图单源最短路径** 的算法 (后续会说明为何不适用于负边图)。该算法可能是「最短路」算法家族中最知名的一个。Dijkstra 算法提出年代早，为贪心思想的极佳应用，另外，其在「20分钟」内被发明的故事也为人所乐道，具体可看相关 wiki 词条。

> Dijkstra 在1956年构思出此算法，并于1959年发表的 [*A Note on Two Problems in Connexion with Graphs* ](http://www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.pdf) 论文中描述了该算法。

本节中，我将仍旧先给出「朴素版」，专注学习 Dijkastra 的过程，并给出严谨的正确性证明。随后，我们提出应用 「优先队列」 的改进版，并通过对这两个版本时间复杂度的分析，指出对于「稠密图」，应当使用「朴素版」，对于「稀疏图」，应当使用「优先队列版」。接着，我会以一个小例子直观地展示为何 Dijkstra 无法处理具有负边的图。

##### 朴素版

###### 算法描述

[Dijkstra算法 (狄杰斯特拉)](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm): Dijkstra 算法的 **基本操作** 是将所有顶点区分为距离 **已确定** 和 **未确定** 的顶点。算法开始前所有顶点的距离均未确定(一般置为$Infinity$)，初始时置 $s$ 的距离为 0。以一个 $while$ 循环查询当前 **是否有距离未确定** 的顶点，若有则将 **其中距离最小者**  $u$ 选为 **当前顶点**，并**使其距离已知**。然后以 $bfs$ 的方式松弛 $u$ 的邻接顶点 $v$ ，如之前所述，若要求返回完整路径，则可在此时更新 $v$ 的前驱为 $u$。当不再有未确定距离的顶点时算法结束，此时每一个顶点的距离均最小，若需要返回源点到某顶点的完整路径，可通过不断寻找节点的前驱得到 $s$ 到该顶点的具体的最短路径。

**松弛操作 (relax)** 是 Dijkstra 算法的关键，也是后续其他最短路径算法的关键。「松弛」指的是在确定当前顶点 $u$ 的距离 (最新成为已确定距离的顶点) 后，立即尝试更新其邻接顶点 $v$ 的距离。更新条件为 $du + |(u,v)| < dv$ ，表示当前从源点经过 $u$ 到达 $v$ 的距离，要小于此时 $v$ 的距离，也就是发现了一条比当前源点到 $v$ 的路径距离更短的路径。以下图举例说明。

$s$ 经过若干个顶点 (用曲线表现经过多个顶点的路径) 到 $a$ 和 $b$，$a$ 和 $b$ 邻接 $c$。假设此时 $dv = Inifinity$，$da = 5$，$db = 7$。

- 松弛顺序为先 $a$ 后 $b$
 - $a$ 成为当前顶点时，由于 $da + |(a, v)| = 9 < Infinity$，故 $a$ 松弛 $dv$，(若需要，此时可将 $v$ 的前驱置为 $a$ )。
 - $b$ 成为当前顶点时，由于 $db + |(b, v)| = 8 < 9$，故 $b$ 松弛 $dv$，(若需要，此时可将 $v$ 的前驱置为 $b$ )。
- 松弛顺序为先 $b$ 后 $a$
 - $b$ 成为当前顶点时，由于 $db + |(b, v)| = 8 < Infinity$，故 $b$ 松弛 $dv$，(若需要，此时可将 $v$ 的前驱置为 $b$ )。
 - $a$ 成为当前顶点时，由于 $da + |(a, v)| = 9 >= 8$，故 $a$ 无法松弛 $dv$。

![image.png](https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/posts_img/algorithms/graph/dijkstra-example.png)

通过这个例子我们能够直观地观察到，来自 $v$ 的所有入边的松弛，使得 $dv$ 总是有机会更新至所有可能的路径距离的最小值 (而无论先通过那一条入边来松弛)。后续讲解 Bellman-Ford 和 Floyd 算法时，我们还会继续强调松弛操作。另外，松弛这一动词的宾语，现实生活中一般是「松弛边」，不过算法里的松弛，实际上是更新一个点的距离，虽说这个距离是源点到该点的路径长，但毕竟是该点的一个属性。总之你也会看「松弛顶点」的表述，不用特意区分。

至此我们已能够理解如下内容。Dijkstra 算法分成 $|V|$ 个阶段，每个阶段确定当前距离最小者的顶点 $v$ 的距离 $dv$ 为最短距离 (第一个阶段直接给出 $s$ 的距离为 0)，$|V|$ 个阶段即可确定所有顶点的距离。一个阶段确定一个顶点距离正是该算法 **「贪心」** 的体现，其正确性在于，之后不可能通过除 $v$ 外的其他顶点来松弛 $v$ ，因为其他能够用来松弛它的顶点的距离都大于等于此时的 $dv$ ，而那些距离未更新的 (仍为 $Infinity$ ) 的顶点，在此后的松弛中，距离也一定是大于 $dv$ 的，因为松弛它的必定是此前具有有效距离的顶点。总之，我们能够不很严谨地理解 Dijkstra 算法的正确性。如果读者诸君仍觉不放心，也不必担心，我将在「正确性证明」中，用结合「反证法」的「数学归纳法」，严格地证明 Dijkstra 算法的正确性。

###### 算法过程

1. 建图及初始化。
   1. 构建带权图。
   2. 设置一个大小为 $|V|$ 的用于标记顶点距离是否「已确定」的 $boolean$ 数组 $visited[]$ ，下标表示顶点。
   3. 设置一个大小为 $|V|$ 的距离数组 $dists[]$ ，下标表示顶点。初始化所有顶点到源点 $s$ 的距离为 $Infinity$ ，表示该顶点到 $s$ 的距离尚未确定。
   4. 置 $s$ 到其自身距离为 0。

2. 以一个循环寻找 **当前距离未确定顶点中距离最小者** $u$ ，立即置 $u$ 的距离为「已确定」。
3. 松弛操作。尝试松弛 $u$ 的所有 **距离未确定的** 邻接顶点 $v$ 的距离 $dv$。即 $dv = min\{dv, du + |(u,v)|\}$ 。若需要求完整路径，可在松弛的同时更新 $v$ 的前驱为 $u$。

4. 循环结束时，每个顶点到源点的最短路径距离被求出。

设下图 $v_1$ 为源点，应用 Dijkstra 算法求解的过程如下。

| 阶段 | 距离已确定 | 距离未确定 (括号内表示距离)                                  | 松弛                                   |
| ---- | ---------- | ------------------------------------------------------------ | -------------------------------------- |
| 初始 |            | $v_1(∞)$, $v_2(∞)$, $v_3(∞)$, $v_4(∞)$, $v_5(∞)$, $v_6(∞)$, $v_7(∞)$ | $v_1(0)$                               |
| 1    | $v_1(0)$   | $v_2(∞)$, $v_3(∞)$, $v_4(∞)$, $v_5(∞)$, $v_6(∞)$, $v_7(∞)$   | $v_2(2),$ $v_4(1)$                     |
| 2    | $v_4(1)$   | $v_2(2)$, $v_3(∞)$, $v_5(∞)$, $v_6(∞)$, $v_7(∞)$             | $v_3(3)$, $v_5(3)$, $v_6(9)$, $v_7(5)$ |
| 3    | $v_2(2)$   | $v_3(3)$, $v_5(3)$, $v_6(9)$, $v_7(5)$                       |                                        |
| 4    | $v_3(3)$   | $v_5(3)$, $v_6(9)$, $v_7(5)$                                 | $v_6(8)$                               |
| 5    | $v_5(3)$   | $v_6(8)$, $v_7(5)$                                           |                                        |
| 6    | $v_7(5)$   | $v_6(8)$                                                     | $v_6(5)$                               |
| 7    | $v_6(5)$   |                                                              |                                        |

![image.png](https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/posts_img/algorithms/graph/dijkstra-example2.png)

###### 正确性证明

如下，利用数学归纳法 (结合反证法) 严格证明 Dijkstra 算法正确性。

> 本证明参考了[这个帖子](https://www.zhihu.com/question/57206374)。

a) 首先回顾数学归纳法的证明过程。

1. 起始验证。对于命题 $P(n)$，当 $n = 1$ 时命题 $P$ 成立。
2. 假设命题成立。即假设命题 $P(n)$ 在 $n = m (m > 1, m ∈ N)$ 时成立。
3. 递推证明。根据 2 的假设，若能证明 $n = m + 1$ 时命题 $P$ 成立，则命题得证。

例如，有命题 $P：1+2+3...+n = n*(n+1)/2$，按照数学归纳法证明如下：

1. 起始验证。当 $n$ 等于 $1$ 时，$1 = 1*(1+1)/2$，命题成立。

2. 假设命题成立。假设命题等于 $m$ 时成立，$1+2+3+...+m = m*(m+1)/2$。

3. 递推证明。根据 2 的假设，如果能证明 $n = m+1$ 时命题正确，则命题 $P$ 成立。

证明：在 2 所示式子左右两边加上 $m+1$，得到 $1+2+3+...+m+(m+1) = m*(m+1)/2 + (m+1)$

等号右边可以写成 $(m+1)*(m+2)/2$，显然该形式就是将 $n = m+1$代入原命题 $P$ 的形式，证毕。

b) 利用数学归纳法证明如下命题。

命题 $P$：Dijkstra 算法第 $n$ 次进入 $wh ile$ 时，会将第 $n$ 个顶点加入距离已确定顶点集合 $A$ 中，此时对于顶点 $∀v ∈ A($共 $n$ 个)，总有 $dv = δv$。

※ $dv$ 表示由 Dijkstra 算法得到的最短距离估计 ( *tentative shortest distance* )，对于源点 $s$ ，在程序开始时赋予 $ds = 0$，对于其他顶点，由松弛操作得到。$δv$ 表示实际的顶点 $v$ 到源点的最短距离。

1. 起始验证。当 $n$ 等于 $1$ 时，$A$ 集合中只有源点 $s$ 自身，$ds = 0$ (程序开始时赋值得到)，且知 $δv = 0$，故 $n=1$ 时命题正确。

2. 假设命题成立。假设命题 $P$ 在 $n$ 等于 $m$ 时，$P(m)$ 成立，即算法经过 $m$ 次while，得到具有 $m$ 个顶点的集合 $A$，对于顶点 $∀v ∈ A$ (共 $m$ 个)，总有 $dv = δv$。

3. $P(m+1)$ 递推证明。根据 2 的假设，如果能证明第 $m+1$ 个顶点 $u$ 被放入集合 $A$ 时有 $du = δu$，则命题 $P$ 成立。

更详细地，$|A| = m$ 时，在点集 $B (B = S - A)$ 中根据算法规则找到距离最短的顶点 $u$，将该顶点将作为第 $m+1$ 个顶点放入 $A$ 中，放入后 $|A| = m + 1$，如果能证明 $du = δu$，使得 $P(m+1)$ 成立，则对于顶点 $∀v ∈ A$ (共 $m+1$ 个)，有 $dv = δv$。

以反证法证明之。

3.1 假设 $m+1$ 时 $du = δu$ 不成立，即有如下式(1)， 之后的目标是根据已知条件导出某种矛盾情形，推翻该假设。

(1) $δu < du$

※ $δu$ 是实际的 $u$ 到源点的最短距离，$du = δu$ 不成立时只能是 $δu < du$。算法保证了从 $s$ 到 $u$ 的过程一定是一条由图中的有向边构成的连续路径，只要是连续路径，无论有多少条这样的路径。一定有一条最短路径，其长度记作 $δu$。

3.2 根据3.1的假设，存在一条从源点 $s$ 到 $u$ 的路径 $Pu$，该路径是 $s$ 到 $u$ 的最短路径，即 $|Pu| = δu < du$。路径 $Pu$ 一定有不在 $A$ 集内的顶点 (至少有 $u$ 不在 $A$ 集中)，同时也有在 $A$ 集中的点 (至少有 $s$ 点在 $A$ 集中)，可以假设 $Pu$ 经过 $x$ 和 $y$，其中 $x$ 在 $A$ 中 (可以是 $s$ 本身)，$y$ 在 $B$ 中 (可以是 $u$ 本身)，$y$ 到 $u$ 的过程中也可以再进入 $A$，如下图。$Px$ 为 $Pu$ 在顶点 $x$ 结束的子路径，因为路径 $Px + (x, y)$ 为路径 $Pu$ 的一部分，所以有：

(2)    $|Px| + |(x, y)| ≤ |Pu| = δu$

这是显然的，因为 $Px + (x, y)$ 是 $Pu$ 的一部分，当 $y=u$ 时取到等号。

![image.png](https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/posts_img/algorithms/graph/dijkstra-proof.png)

3.3 在 $x$ 被选中进入 $A$ 集内时，对其邻接顶点 $y$ 执行过 **松弛操作**，该操作会比较 $dx + |(x, y)|$ 是否小于 $dy$，若小于则以 $dx + |(x, y)|$ 更新 $dy$ 的值，所以如果更新了，更新之后有 $dy = dx + |(x, y)|$ ，如果没更新，说明 $dy < dx + |(x, y)|$。假设之后 $y$ 还会被 $y$ 的其他前驱顶点更新 $dy$ 值 (当该前驱顶点进入 $A$ 集时)，那 $dy$ 只会变得更小，所以一定有：

(3)    $dy ≤ dx + |(x, y)|$

比较式 (2) 和式 (3) 中的 $|Px|$ 和 $dx$，因为 $dx = δx$  (由步骤2的 $P(m)$ 假设给出，顶点 $x$ 是 $P(m)$ 假设的 $m$ 个顶点之一)，而 $Px$ 只是若干从 $s$ 到 $x$ 的路径之一，因此必有 $d(x) ≤ |Px|$，当 $Px$ 恰是 $s$ 到 $x$ 的最短路径时取到等号。所以根据式 (2) 和式 (3) 有：

$dy ≤ dx + |(x, y)| ≤ |Px| + |(x, y)| ≤ |Pu|$，即

(4)    $dy ≤ |Pu| = δu$

3.4 顶点 $y$ 与 $u$ 均在 $B$ 集中，根据算法规则，$u$ 之所以是第 $m+1$ 个被放入 $A$ 集中的顶点，是因为第 $m+1$ 次进入while时，$u$ 在 $B$ 集中相比于 $B$ 集中的其他顶点(自然也包括 $y$ )，到源点 $s$ 的距离最小，显然有：

(5)    $du ≤ dy$

结合式 (1)，式 (4)，式 (5) 得到：

(6) $δu < du ≤ dy ≤ |Pu| = δu$ ，即 $δu < δu$

至此，由 3.1 的假设 「$d(u) = δ(u)$ 不成立」导出了矛盾，所以 $d(u) = δ(u)$ 是成立的，**Dijkstra 算法正确性得证** 。

###### 时空复杂度

时间复杂度：$O(|V|^2 + |E|)$，由于 $|E| < |V|^2$ ，所以也可以写为 $O(|V|^2)$ 。

1. 寻找拥有最小距离的顶点的时间为 $O(|V|^2)$ 。 每次遍历寻找时间复杂度为 $O(|V|)$ ，需寻找 $|V|$ 次 。

2. 所有顶点的距离被松弛的次数上限为 $O(|E|)$ 。由算法可知顶点距离松弛只发生在找到当前距离未确定且距离最小的顶点之后，一次更新的次数是该顶点的邻接顶点数 (即出边数，出度)。每一次循环松弛某一个顶点的所有出边。所有顶点的出边数即总边数 $|E|$ 。故总松弛次数，也即所有顶点的距离被更新的次数时间复杂度为 $O(|E|)$ 。

空间复杂度：存图空间 $O(|V|+|E|)$ ， $visited/dists$ 空间 $O(|V|)$。总体为线性空间复杂度 $O(|V|+|E|)$ 。

###### 代码

现在，我们利用上述知识来实际编程解决 [743. 网络延迟时间](https://leetcode.cn/problems/network-delay-time/) 。仔细读题后可知，从某个节点 $k$ 发出一个信号，要使所有节点都收到信号，只要使距离 $k$ 最远的那个顶点收到信号即可。所以这题是典型的带权单源最短路问题，应用本节的朴素版 Dijkstra 算法，以顶点 $k$ 为源点，求出其他所有顶点到 $k$ 的最短路长度，返回其中最大者即可。需要注意以下几点。

- 构建带权图时，需要记录边权，因此顶点的邻接表以 `List<int[]>` 表示，对于顶点 $u$ ，其邻接表中的 `int[] v_weight` ，`v_weight[0]` 为 $u$ 的邻接顶点， `v_weight[1]` 为边权 $|(u, v)|$ 。
- 为了清晰地看出「在当前距离未确定的顶点中找到距离最小者」这一「贪心」动作，我们将其写为 $getMin$ 方法。
- 当存在与源点不连通的顶点时，该顶点的距离将得不到松弛，因此存在未松弛顶点时返回 -1。

```java
class Solution {
 public int networkDelayTime(int[][] times, int n, int k){
 List<List<int[]>> graph = new ArrayList<>();
 for(int i = 0; i < n; i++) graph.add(new ArrayList<>());
 for(int[] edge : times){ // 建带权图
 int u = edge[0] - 1, v = edge[1] - 1, weight = edge[2];
 graph.get(u).add(new int[]{v, weight});
 }
 int max = 0, INF = Integer.MAX_VALUE; // max为距离源点最远顶点的距离，INF为所有顶点距离初始值
 int[] dists = new int[n];
 boolean[] visited = new boolean[n];
 Arrays.fill(dists, INF); // 距离初始化
 dists[k - 1] = 0; // 源点距离置0
 int u = -1; // 当前距离未确定顶点中的距离最小者
 while((u = getMin(dists, visited)) != -1) { // 遍历顶点，寻找当前距离未确定顶点中的距离最小者
 visited[u] = true; // 立即置为距离已确定
 for (int[] v_weight : graph.get(u)) {
 int v = v_weight[0], weight = v_weight[1];
 if(!visited[v]) { // 对于u的距离未确定的邻接顶点v，松弛v的距离
 int dv = dists[u] + weight;
 if(dv < dists[v]) { // 松弛条件
 dists[v] = dv; // 更新dv
 }
 }
 }
 }
 for(int dist : dists){ // 找最短路长度最大者
 if(dist == INF) return -1; // 存在距离未更新的顶点直接返回 -1
 if(dist > max) max = dist;
 }
 return max;
 }
 private int getMin(int[] dists, boolean[] visited){ // 在当前距离未确定的顶点中找距离最小者
 int n = dists.length, min = Integer.MAX_VALUE, minVertex = -1;
 for (int u = 0; u < n; u++) {
 if(!visited[u] && dists[u] < min) { 
 min = dists[u];
 minVertex = u;
 }
 }
 return minVertex;
 }
}
```

##### 优先队列版

###### 算法描述

针对朴素版「算法过程」第 2 步「在当前距离未确定顶点中寻找距离最小者」，我们很容易想到利用优先队列 (小顶堆) $pq(priority\_queue)$ 来优化，除此之外其他过程与朴素版一致。需要注意的是一个顶点 $v$ 的距离在被确定前可能经过多次松弛，每次松弛都会进入 $pq$ ，于是同一时间，堆中可能有多个相同的顶点 (松弛过几次就有几个) 。这其中最靠顶的将会先出堆，出堆即表明该顶点距离已确定，所以顶点出堆时要判断是否是第一次出堆，若不是则跳过。

###### 算法过程

1. 建图及初始化。
   1. 构建带权图。
   2. 设置一个小顶堆 $pq$ 。
   3. 设置一个大小为 $|V|$ 的用于标记顶点距离是否「已确定」的 $boolean$ 数组 $visited[]$ ，下标表示顶点。
   4. 设置一个大小为 $|V|$ 的距离数组 $dists[]$ ，下标表示顶点。初始化所有顶点到源点 $s$ 的距离为 $Infinity$ ，表示该顶点到 $s$ 的距离尚未确定。
   5. 置 $s$ 到其自身距离为 0。
   6. $s$ 入堆。
2. 一次出堆完成一个顶点最短路径的确定。以 $while$ 循环对 $pq$ 判空，若不空，堆顶顶点 $u$ 出堆，此时 $u$ 为距离未确定顶点中距离最小者，置 $u$ 的距离为已确定。
3. 松弛操作。尝试松弛 $u$ 的所有 **距离未确定的** 邻接顶点 $v$ 的距离 $dv$。即 $dv = min\{dv, du + |(u,v)|\}$ 。若需要求完整路径，可在松弛的同时更新 $v$ 的前驱为 $u$。
4. 循环结束时，每个顶点到源点的最短路径距离被求出。

###### 时空复杂度

时间复杂度：$O(|E|log|E|+|E|log|E|)$ ，化简为 $O(|E|log|E|)$ ，可进一步化简为 $O(|E|log|V|)$  ，具体如下。

1.  **在当前距离未确定顶点中寻找距离最小者的总时间复杂度** 为 $O(|E|log|E|)$ 。

1. $while$ 中 $pq$ 判空次数与堆大小有关，堆的大小为 $O(|E|)$ ，注意不是 $O(|V|)$ 而是 $O(|E|)$，后述。
    2. 获取距离最小者耗时为堆的查找时间复杂度， $O(log|E|)$ 。
    3. 故此部分时间复杂度为 $O(|E|log|E|)$ 。

※ 优先队列判空操作 $isEmpty()$ 本身是常数时间操作，但总共要执行 $O(|E|)$ 次。

2. 考虑所有顶点的距离被更新 (松弛) 导致的 **总的顶点入堆时间复杂度** 为 $O(|E|log(|E|))$ 。

1. 由算法可知顶点 $u$ 松弛其邻接顶点 $v$ 的距离只发生在找到 $u$ 为当前距离未确定且距离最小的顶点之后 ( $u$ 出堆后)。(尝试) 松弛的次数是其邻接顶点 $v$ 的个数 (即 $u$ 的出边数，出度)。每一次循环确定一个这样的顶点，也就是每一次循环尝试松弛 **当前距离被确定的顶点** 的所有出边。所有顶点的出边即总边数为 $|E|$ 。故总松弛次数，也即所有顶点的距离被更新的次数，也即顶点入堆总次数为 $O(|E|)$ 。
   2. $dv$ 被松弛时 $v$ 入堆，插入操作的时间复杂度为 $O(log|E|)$。由上述，入堆次数与更新次数相同，于是 **所有顶点的距离更新** 以及该更新导致的 **顶点入堆的总时间复杂度** 为 $O(|E| + |E|log|E|)$ 。

※ 根据上述顶点入堆次数取决于总边数的分析，堆的大小上限不是 $O(|V|)$ 而是 $O(|E|)$ ，所以 $dv$ 更新时 $v$ 入堆的时间复杂度为 $O(log|E|)$ ，只是借助边数与顶点数的关系，可化简为 $O(log|V|)$ 。 $|E| < |V|^2$ ，即有 $log|E| < 2log|V|$，可化简为 $O(log|V|)$ 。

空间复杂度：存图空间 $O(|V|+|E|)$ ， $visited/dists$ 空间 $O(|V|)$， $pq$ 空间 $O(|E|)$ 。总体为线性空间复杂度 $O(|V|+|E|)$ 。

> ※ tip1: 连通图顶点数与边数有如下关系。
>
> 无向连通图：$|V| - 1 <= |E| <= |V|*(|V| - 1) / 2$ 
>
> 链状时 $|E|$ 取到最小 $|V|-1$ ，完全连通即两两相连时取到最大 $|V|*(|V| - 1) / 2$ 。
>
> 有向连通图：$|V| - 1 <= |E| <= |V|*(|V| - 1)$ 
>
> 链状时 $|E|$ 取到最小 $|V|-1$ ，完全连通即两两相连且正反向成对时取到最大 $|V|*(|V| - 1)$ 。
>
> 
>
> ※ 利用 Fibonacci堆的 Dijkstra 算法时间复杂度为 $O(|E|+|V|log|V|)$ ，本文不做介绍 (我不会)。

对比「朴素版」的时间复杂度，不难看出，当图为 **「稠密图」** 时，「优先队列版」复杂度可表为 $O(|V|^2log|V|)$ ，这是比「朴素版」更差的复杂度。因此对于稠密图，我们可采用更优的「朴素版」。当图为 **「稀疏图」** 时，「优先队列版」复杂度可表为 $O(|V|log|V|)$ ，显然此时应采用「优先队列版」。

###### 代码

现在，我们给出如下利用优先队列的 Dijkstra 算法代码来解决 [743. 网络延迟时间](https://leetcode.cn/problems/network-delay-time/) 。其与朴素版的差别仅在于每个「阶段」寻找当前距离未确定顶点中距离最小者的方式不同。该写法为 Dijkstra 算法写法的模版写法，读者应 **牢记于心** 。

```java
// Dijkstra优先队列 (邻接表存图)
class Solution {
 public int networkDelayTime(int[][] times, int n, int k){
 List<List<int[]>> graph = new ArrayList<>();
 for(int i = 0; i < n; i++) graph.add(new ArrayList<>());
 for(int[] edge : times){ // 建带权图
 int u = edge[0] - 1, v = edge[1] - 1, weight = edge[2];
 graph.get(u).add(new int[]{v, weight});
 }
 int max = 0, INF = Integer.MAX_VALUE; // max为距离源点最远顶点的距离，INF为所有顶点距离初始值
 int[] dists = new int[n];
 boolean[] visited = new boolean[n];
 Arrays.fill(dists, INF); // 距离初始化
 dists[k - 1] = 0; // 源点距离置0
 PriorityQueue<int[]> pq = new PriorityQueue<>(((u, v) -> u[1] - v[1])); // 小顶堆
 pq.add(new int[]{k - 1, 0}); // 源点入堆
 while(!pq.isEmpty()) { 
 int[] u_dist = pq.remove();
 int u = u_dist[0];
 visited[u] = true; // 立即置u的距离为已确定
 for (int[] v_weight : graph.get(u)) {
 int v = v_weight[0], weight = v_weight[1];
 if(!visited[v]) { // 对于u的距离未确定的邻接顶点v，松弛v的距离
 int dv = dists[u] + weight;
 if(dv < dists[v]) { // 松弛条件
 dists[v] = dv; // 更新dv
 pq.add(new int[]{v, dv}); // v入堆
 }
 }
 }
 }
 for(int dist : dists){ // 找最短路长度最大者
 if(dist == INF) return -1; // 存在距离未更新的顶点
 if(dist > max) max = dist;
 }
 return max;
 }
}
```

```java
// Dijkstra优先队列 (链式向前星存图)
class Solution {
 public int networkDelayTime(int[][] times, int n, int k){
 int m = times.length, edgeNum = 0;
 int[] heads = new int[n];
 int[] ends = new int[m + 1], nexts = new int[m + 1], weights = new int[m + 1];
 for(int[] edge : times){ // 建带权图
 int u = edge[0] - 1, v = edge[1] - 1, weight = edge[2];
 edgeNum++;
 weights[edgeNum] = weight;
 ends[edgeNum] = v;
 nexts[edgeNum] = heads[u];
 heads[u] = edgeNum;
 }
 int max = 0, INF = Integer.MAX_VALUE; // max为距离源点最远顶点的距离，INF为所有顶点距离初始值
 int[] dists = new int[n];
 boolean[] visited = new boolean[n];
 Arrays.fill(dists, INF); // 距离初始化
 dists[k - 1] = 0; // 源点距离置0
 PriorityQueue<int[]> pq = new PriorityQueue<>(((u, v) -> u[1] - v[1])); // 小顶堆
 pq.add(new int[]{k - 1, 0}); // 源点入堆
 while(!pq.isEmpty()) { 
 int u = pq.remove()[0];
 if(visited[u]) continue;
 visited[u] = true; // 立即置u的距离为已确定
 for (int edgeNo = heads[u]; edgeNo != 0; edgeNo = nexts[edgeNo]) {
 int v = ends[edgeNo], weight = weights[edgeNo];
 if(!visited[v]) { // 对于u的距离未确定的邻接顶点v，松弛v的距离
 int dv = dists[u] + weight;
 if(dv < dists[v]) { // 松弛条件
 dists[v] = dv; // 更新dv
 pq.add(new int[]{v, dv}); // v入堆
 }
 }
 }
 }
 for(int dist : dists){ // 找最短路长度最大者
 if(dist == INF) return -1; // 存在距离未更新的顶点
 if(dist > max) max = dist;
 }
 return max;
 }
}
```

##### 负边图

以下图为例说明 Dijkstra 算法为何无法处理负边图。

顶点 $s$ 是源点，从 $s$ 开始执行算法，$du$ 和 $dv$ 被更新为 1, 2，在距离未确定的顶点 $u$ 和 $v$ 中 $du$ 更小，$u$ 的距离设为已确定，$du = 1$ 。然而实际上从 $s$ 到 $v$ 再到 $u$ 会得到一条长度为 -1 的更短的路径。

由此我们也可以看到，Dijkstra 「贪心」能够成立的一个隐含前提是路径边数的增长 **必须** 使得路径长 (边权和) 是 **「非递减」** 的。存在负边则导致路径边数增长后边权和递减，使得「贪心」成立的前提不成立。

![image.png](https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/posts_img/algorithms/graph/dijkstra-negtive-edge.png)

#### DAG SSSP

##### 算法描述

若最短路的求解对象是 DAG ，那么根据其无圈的特点，可以采用「拓扑排序」的方式求单源最短路，使得时间复杂度仅为线性的 $O(|V|+|E|)$ 。

**有向无圈图** 一定存在拓扑排序，从一个入度为 0 的源点 $s$ 开始以拓扑排序方式实现 Dijkstra 算法。具体而言，准备一个普通队列 $q$ ，首先将 $s$ 入队，然后开始 $while(!q.isEmpty())$ 。每次将入度为 0 的顶点 $u$ 出队，由于其已无入边，故该顶点距离 $du$ 不会再被更新，此时 $du$ 即已为确定的最短距离。标准的 Dijkstra 算法总是通过这样的操作来确定一个顶点的距离，即「在当前距离未确定的顶点中寻找距离最小者，并置其距离为已确定」，所以也可以将 DAG 情形的算法看作是省去了上述关键操作的 Dijkstra 算法，也就是顶点 $u$  **入队** 时其距离即确定。

##### 有负边的 DAG

DAG版的 Dijkstra 算法 **可应用于有负边的DAG。** 因为对任意顶点 $u$ ，仅在其入度减为 0 时其距离才被确定，而此时来自其入边的松弛一定都已执行过，因此 $u$ 是否存在负权值的入边，$du$ 都可以被正确松弛到最短。以下图为例，从 $s$ 开始执行算法，$s$ 出队，$du$ 和 $dv$ 被更新为 1 和 2 ，然后 $u, v$ 入度减为 1, 0，$v$ 无入边，其距离不会再被更新，即 $dv = 2$ 即为 $v$ 的最终距离，$v$ 入队。接着 $v$ 出队，$du$ 被更新为 -1 ，$u$ 的入度减为 0，此时 $u$ 无入边，其距离不会再被更新，即其距离被最终确定为 $du = -1$ 。可以看到 $u$ 的距离 **在其入度减至 0 的过程中总会更新至最短** 。

![image.png](https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/posts_img/algorithms/graph/dijkstra-negtive-edge.png)

#####  贪心 & 动态规划

这个小部分是我的一点思考🤔，与读者们探讨一下 Dijkstra 和 DAG 拓扑排序式的 SSSP 算法所分别体现的「贪心」和「动态规划」思想。

我们已经知道，无论是一般的 Dijkstra 还是本节的 DAG 上的 SSSP 算法，在求顶点 $v$ 的距离时，本质上都是通过这样的「动态规划」式的递推式求解的， $(u, v)$ 是所有 $v$ 的入边。

$$dv = min\{dv, du + |(u, v)|\}, (u, v) ∈ E$$

主要区别在于，在 Dijkstra 中，我们不必 **「全部算完」** 所有入边带来的松弛，而是在 $dv$ 为当前未确定距离顶点中最小时，就「提前」确定了距离。因此它既是「动态规划」，又因为这个「提前」确定的特点，更多地被人强调为「贪心」。而本节 DAG 的 SSSP 算法，一定会计算所有入边的松弛，因此他更具有典型的「打表」式的「动态规划」特点。这大概是 Dijkstra 总与「贪心」相联系而不太被人指出其「动态规划」的特点的原因？

##### 算法过程

1. 建图及初始化。
   1. 设置一个大小为 $|V|$ 的入度数组 $indegrees[]$ ，下标表示顶点。
   2. 构建带权图并同时计算入度。
   3. 设置一个队列 $q$ 。
   4. 设置一个大小为 $|V|$ 的距离数组 $dists[]$ ，下标表示顶点。初始化所有顶点到源点 $s$ 的距离为 $Infinity$ ，表示该顶点到 $s$ 的距离尚未确定。
   5. 置 $s$ 到其自身距离为 0。
   6. $s$ 入队。
2. 通过 $while(!q.isEmpty())$ 不断将当前入度为 0 的顶点出队，出队时置其距离已确定。
3. 松弛操作。尝试松弛 $u$ 的所有 **距离未确定的** 邻接顶点 $v$ 的距离 $dv$。即 $dv = min\{dv, du + |(u,v)|\}$ 。若需要求完整路径，可在松弛的同时更新 $v$ 的前驱为 $u$。
4. 将上述 $v$ 的入度减 1，并考察是否减至 0，若减至 0，则 $v$ 的距离在此时确定， $v$ 入队。
5. 循环结束时，每个顶点到源点的最短路径距离被求出。

##### 时空复杂度

时间复杂度：即拓扑排序的时间复杂度，为线性时间复杂度 $O(|V|+|E|)$ 。

空间复杂度：存图空间 $O(|V|+|E|)$ ， $visited/dists$ 空间 $O(|V|)$， $q$ 空间 $O(|V|)$ 。总体为线性空间复杂度 $O(|V|+|E|)$ 。

##### 代码

如下是假设 [743. 网络延迟时间](https://leetcode.cn/problems/network-delay-time/) 的输入为无圈图的前提下的代码。但实际部分测试用例是有圈的，测试了一下只能过 15 个用例，然后就碰到有圈图了。等找到合适的输入限制为 DAG 图的题之后再更新。总之，DAG 上「拓扑排序」式的 SSSP 算法，或者干脆称 DAG 版的 Dijkstra 算法的写法如下。如果我们确定输入为 DAG，则应该优先考虑此版本算法， **以获得线性时间复杂度** 。

```java
class Solution {
 public int networkDelayTime(int[][] times, int n, int k){
 List<List<int[]>> graph = new ArrayList<>();
 int[] indegrees = new int[n]; // 入度信息
 for(int i = 0; i < n; i++) graph.add(new ArrayList<>());
 for(int[] edge : times){ // 建带权图 & 计算入度
 int u = edge[0] - 1, v = edge[1] - 1, weight = edge[2];
 graph.get(u).add(new int[]{v, weight});
 indegrees[v]++;
 }
 int max = 0, INF = Integer.MAX_VALUE; // max为距离源点最远顶点的距离，INF为所有顶点距离初始值
 int[] dists = new int[n];
 Arrays.fill(dists, INF); // 距离初始化
 dists[k - 1] = 0; // 源点距离置0
 Queue<Integer> q = new ArrayDeque<>(); 
 q.add(k - 1); // 源点入队
 while(!q.isEmpty()) { // 拓扑排序过程
 int u = q.remove();
 for (int[] v_weight : graph.get(u)) {
 int v = v_weight[0], weight = v_weight[1];
 int dv = dists[u] + weight;
 if(dv < dists[v]) { // 松弛条件
 dists[v] = dv; // 更新dv
 }
 indegrees[v]--; // v入度减1
 if(indegrees[v] == 0) q.add(v); // v入队
 }
 }
 for(int dist : dists){ // 找最短路长度最大者
 if(dist == INF) return -1; // 存在距离未更新的顶点
 if(dist > max) max = dist;
 }
 return max;
 }
}
```

#### Bellman-Ford

之前我们指出，Dijkstra 算法因其「贪心」的特点，在还未穷尽顶点所有入边的松弛时就「过早地」确定了该顶点的距离，导致其无法处理具有负边的图。与之相对地， DAG 最短路算法中，通过「入度」信息， **确保了任意顶点一定能够穷尽所有入边的松弛** ，因此可以适用于有负边的图 (DAG) ，但为了确保入度能减至 0 ，要求图不能有圈。我们自然会想，有没有什么办法能够结合二者的优点，使得最短路算法能够同时处理有圈且有负边的图呢？答案是肯定的，只要我们通过某种方式，在不借助入度的情况下保证所有顶点都能够执行其所有入边的松弛，就可以实现上述要求。本节介绍的 Bellman-Ford 算法就是具有这样特点的最短路算法。

本节中我会给出叙述式的 Bellman-Ford 算法正确性证明 (说明)，并展示其「动态规划」的本质。为了能够更好地理解算法过程，在「实例说明」中展示算法运行的详细过程。在「负边图 & 负圈图」一节中说明该算法能够处理负边图以及不能够处理负圈图的原因。

在「代码」中，我们仍旧通过 [743. 网络延迟时间](https://leetcode.cn/problems/network-delay-time/) 一题来展示 Bellman-Ford 的写法。

> Bellman-Ford 在1950年代中后期被多个学者独立发明，以至于在算法冠名权上有些争议。Jeff Erickson 在他的 *Algorithms* 一书的 8.7 节开头，做了如下介绍。
>
> The simplest implementation of Ford’s generic shortest-path algorithm was first sketched by Alfonso Shimbel in 1954, described in more detail by Edward Moore in 1957, and independently rediscovered by Max Woodbury and George Dantzig in 1957, by Richard Bellman in 1958, and by George Minty in 1958. (Neither Woodbury and Dantzig nor Minty published their algorithms.) In full compliance with Stigler’s Law, the algorithm is almost universally known as **Bellman-Ford**, because Bellman explicitly used Ford’s 1956 formulation of relaxing edges, although some authors refer to “Bellman-Kalaba” and a few early sources refer to “Bellman-Shimbel”.
>
> 于是 Jeff Erickson 干脆十分公允地写道:
>
> The Shimbel / Moore / Woodbury-Dantzig / Bellman-Ford / Kalaba / Minty / Brosh algorithm can be summarized in one line:
>
> Bellman-Ford: Relax **ALL** the tense edges, then recurse.

##### 算法描述

[Bellman-Ford Algorithm(贝尔曼-福特算法)](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm): 与 Dijkstra 算法的相同点是对边 (或者说对顶点) **不断执行松弛操作** ，以逐渐得到所有顶点到源点的最短距离。Dijkstra 每次循环「贪心地」完成 **一个** 顶点最短路径的确定，而 BF 算法则对图的 **所有边** ( $|E|$ 条边) ，简单地进行 $|V|-1$ 次 **全量松弛操作** ，第 $i$ 次「全量松弛」使得位于第 $i+1$ 层的顶点的距离被确定。从一次全量松弛确定一层顶点距离这个角度上来说， BF 算法也是「贪心」思想的应用。任意顶点最多居于第 $|V|$ 层 (以源点 $s$ 为第 1 层)，因此算法结束时，保证 (无负圈图) 所有顶点距离最短。

※ 实际上任何最短路算法都无法求出「负圈图」的最短路，因为通过在负圈上不断绕圈，路径长度可以无限小，也就是 **负圈上的顶点不存在「最短路」** 。后面我们将看到，虽无法给出负圈图的最短路结果 (因为本来就没有)，但 **BF 算法能够判断图是否存在负圈** 。

※ 作者看过一些资料称全量松弛次数为 $|V|$ 次，这是不够严谨的，只需 $|V| - 1$ 次即可。

##### 算法过程

1. 建图及初始化。
 1. 构建带权图。
 2. 设置一个大小为 $|V|$ 的距离数组 $dists[]$ ，下标表示顶点。初始化所有顶点到源点 $s$ 的距离为 $Infinity$ ，表示该顶点到 $s$ 的距离尚未确定。
 3. 设置一个 $finished$ 布尔变量用于实现「提前结束优化」(不是必须的)。
 4. 置 $s$ 到其自身距离为 0。
2. 外层循环执行 $|V|-1$ 次，每一次都 **「松弛所有边」** 。
 1. 进入外层循环后按顶点顺序依次对所有顶点 $u$ 考察其所有邻接顶点 $v$ 是否有 $du + |(u, v)| < dv$，若有，松弛之，即令 $dv = du + |(u, v)|$。同时置 $finished = false$ ，表示松弛未结束。若需要求完整路径，可在松弛的同时更新 $v$ 的前驱为 $u$。

2.  在一次「松弛所有边」的操作中，若没有任何边被松弛，表明所有可能的松弛已完成 (负圈图除外)， 此时可 **「提前」退出最外层循环** 。
3. 外层循环结束时，(若无负圈) 每个顶点到源点的最短路径距离被求出。
4. 检查图是否有负圈。再次对所有边执行松弛操作， **若有边可被松弛，则有负圈** ，结束程序，否则正常结束，所有顶点最短路径被求出。

##### 正确性证明 (说明)

1.  已知若一个顶点 $v$ 的所有入边若完成了所有可能的松弛 (一条入边可被多次松弛)，则在 **最后一次松弛** 后，必有 $dv=δv$ 。 ($dv$ 表示由算法得到的 $v$ 的距离， $δv$ 表示实际的 $v$ 的最短距离)。

2.  易知，第 $i$ 次全量松弛，第 $i$ 层顶点的出边 **必被松弛** 。例如第 1 次全量松弛，$s$ (第 1 层顶点) 的出边必被松弛。第 2 次全量松弛，由于有了第 1 次全量松弛的结果，第 2 层顶点 ($s$ 的邻接顶点) 的出边必被松弛。

3.  $|edges(s, v)|$ 表示 $s$ 到 $v$ 的路径的边数，最多为 $|V|-1$ ，当 $s$ 到 $v$ 为链状时为 $|V|-1$  。当 $v$ 的入边是第 1 层入边时，将在第 1 次全量松弛时被松弛，若是第 2 层入边，则会在第 2 次全量松弛时被松弛 (这条入边的发出顶点在第 1 次全量松弛时已被松弛)，以此类推，第 $i$ 层入边会在第 $i$ 次全量松弛时被松弛。所有顶点的入边组成了该图的所有边，任意一边一定是某一层次的入边 (可以同时属于多个层次) 。

4.  由此，$v$ 的入边能否被全部松弛只取决于其最深的入边能否被松弛 (当一条入边属于多个层次时，取其最深层次)，也即取决于 $s$ 到 $v$ 的最长路径 $\max\{|edges(s, v)|, v ∈ V\}$ 的边数。如前述，  $\max\{|edges(s, v)|, v ∈ V\} ≤ |V|-1$ ，故至多经过 $|V| - 1$ 次全量松弛， **图的所有入边必定都松弛过且完成了所有可能的松弛**  (某条入边属于多个层次时，可能经过多次松弛) 。如果把图看成以 $s$ 为根的树，也可以说为了求得所有顶点的最短路径，所需的全量松弛的次数取决于 **树的高度** 。对某一顶点，可以说该顶点至多经过其 **最大深度减 1 次** 全量松弛后取得最短路径。

5.  上述过程对任意顶点均成立，故 BF 算法正确性得证。

此证明也可以看作如下「动态规划」过程。为单串 $O(1)$ 依赖动态规划 (「 $O(1)$ 依赖」指当前元素的更新只依赖常数个元素)。

1.  定义: $dp[j]$ 表示源点 $s$ 到顶点 $j$ 的最短路径长度。

2.  边界: $dp[s] = 0$ 。

3.  递推: $dp[j] = dp[j - 1] + |(j - 1, j)|$ 。$j - 1$ 表示 $s-j$ 最短路径上的前一个顶点。

根据前述，$j - 1$ 顶点最大层深必比 $j$ 小 1，故 $dp[j - 1]$ 一定在求 $dp[j]$ 之前就已求出，递推式成立。

##### 实例说明

以下实际考察 BF 算法对下图的求解过程，重点关注顶点 $v$ 。 (图裂了的话可以看[这里](https://tva1.sinaimg.cn/large/008i3skNly1gyelpsd4sfj30f60cqdga.jpg))

![image.png](https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/posts_img/algorithms/graph/bf-example.png)

$p(s, v)$ 有如下四种可能：

$p1: s > v ，|p1| = 15$ ，$(s, v)$ 是 $v$ 的第 1 层入边

$p2: s > a > v，|p2| = 14$ ，$(a, v)$ 是 $v$ 的第 2 层入边

$p3: s > b > a > v ，|p3| = 12$ ，$(a, v)$ 是 $v$ 的第 3 层入边

$p4: s > b > c > v ，|p4| = 6$ ，$(c, v)$ 是 $v$ 的第 3 层入边

可以看到 $(a, v)$ 边同时属于 $v$ 的第 2 和第 3 层入边。这四条路径最长者长 3 (指边数，$p3$ 和 $p4$ )，根据上述分析，只需要执行 3 次全量松弛即可完成对 $v$ 最短路径的确定。又因为源点到所有顶点的所有路径中最长的长度也是 3，所以执行 3 次全量松弛可以确定所有顶点的最短路径。假设全量松弛时顶点的处理顺序为 $s, a, c, b, v$ ，下表展示算法对该图的运行过程 (第 3 次之后的全量松弛不会再松弛任何边，省略)。

| 松弛过程      | $ds$       | $da$           | $dc$           | $db$           | $dv$                 |
| ------------- | ---------- | -------------- | -------------- | -------------- | -------------------- |
| 初始          | **0 (\*)** | ∞              | ∞              | ∞              | ∞                    |
| 第1次全量松弛 | 0          | **∞ > 9**      | ∞              | **∞ > 3 (\*)** | **∞ > 15**           |
| 第2次全量松弛 | 0          | **9 > 7 (\*)** | **∞ > 5 (\*)** | 3              | **15 > 14**          |
| 第3次全量松弛 | 0          | 7              | 5              | 3              | **14 > 12 > 6 (\*)** |

```
备注：
1. 初始时令 ds 为0，(*)表示已取得该顶点最短路径。
2. 第1次。(s, a), (s,b), (s, v)属于第1层入边，被松弛。
   且b只有一条入边，即经过这趟松弛操作，使得 db = δb。
3. 第2次。第1层入边不会再被松弛。第2层入边(a, v), (b, a), (b, c)被松弛。
   经过这趟松弛操作，a, c的全部入边松弛完毕，使得 da = δa，dc = δc。
4. 第3次。第1，2层入边不会再被松弛，第3层入边(a, v), (c, v)被松弛。
   v 的全部入边松弛完毕，使得 dv = δv。
```

##### 负边图 & 负圈图

-   负边图。由于该算法在 $|V|-1$ 次对所有边的松弛操作中会穷尽所有边被松弛的可能，类似以拓扑排序方式针对 DAG 图的 Dijkstra 算法 (通过入度为 0 保证穷尽所有松弛的可能)，所以也适用于有负边的图。

-   负圈图。当图存在负圈时，$s$ 到圈上任意顶点的距离都可以通过不断绕圈趋于无限小。因此若不能保证输入的图无负圈，可以在 $|V| - 1$ 次全量松弛后再执行一次全量松弛，若仍有边可被松弛，说明存在负圈。

##### 提前结束优化

当某一次全量松弛过程中没有边被松弛，说明所有可能的松弛已被穷尽，可提前结束程序。

##### 最坏情形

当图中存在两点间路径长度为 $|V|-1$ ，且在最后一次「全量松弛」时仍有边被松弛时间达到最坏情形。此情况下，需要对所有边执行 $|V|-1$ 次松弛后才能求得所有顶点的最短路径。对于一链状图 $s > a > b > c > v$ ，其中 $|(s, a)| = 1$，$|(a, b)| = 2$，$|(b, c)| = 3$，$|(c, v)| = 4$。 (图裂了的话可以看[这里](https://tva1.sinaimg.cn/large/008i3skNgy1gxekg5u1idj30ts04i0sz.jpg))

![image.png](https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/posts_img/algorithms/graph/bf-worst.png)

##### 时空复杂度

时间复杂度：每次全量松弛要操作 $|E|$ 条边，共 $|V|-1$ 次，复杂度为 $O((|V|-1)|E|)$ ，即 $O(|V||E|)$  。

空间复杂度：存图空间 $O(|V|+|E|)$ ， $dists$ 空间 $O(|V|)$。总体为线性空间复杂度 $O(|V|+|E|)$ 。

##### 代码

如下是 [743. 网络延迟时间](https://leetcode.cn/problems/network-delay-time/) 的 Bellman-Ford 解法。代码中设置了 $finished$ 布尔变量实现「提前结束优化」，并在通过在外层 $for$ 结束后再执行一次全量松弛实现「负圈检测」，由于本题已保证了不存在负值边，也就不存在负圈，因此负圈检测可以省略。

此代码是 Bellman-Ford 算法的较为普遍的写法 (提前结束优化 + 负圈检测)，读者应熟练掌握。

```java
// 提前退出优化 Bellman-Ford ，带「负圈检测」
class Solution {
 public int networkDelayTime(int[][] times, int n, int k){
 List<List<int[]>> graph = new ArrayList<>();
 for(int i = 0; i < n; i++) graph.add(new ArrayList<>());
 for(int[] edge : times){ // 建带权图
 int u = edge[0] - 1, v = edge[1] - 1, weight = edge[2];
 graph.get(u).add(new int[]{v, weight});
 }
 int max = 0, INF = Integer.MAX_VALUE; // max为距离源点最远顶点的距离，INF为所有顶点距离初始值
 int[] dists = new int[n];
 Arrays.fill(dists, INF); // 距离初始化
 dists[k - 1] = 0; // 源点距离置0
 boolean finished = true;
 for(int i = 0; i < n - 1; i++) { // |V| - 1次 
 for (int u = 0; u < n; u++) { // 全量松弛
 for(int[] v_weight : graph.get(u)){
 int v = v_weight[0], weight = v_weight[1];
 long dv = (long) dists[u] + (long) weight; // 等号右边可能会溢出，临时转为long
 if(dv < dists[v]) { // 松弛条件
 dists[v] = (int) dv; // 更新dv
 finished = false;
 }
 }
 }
 if(finished) break; // 某一次全量松弛未松弛任何边时，提前结束
 else finished = true; // 否则finished置回true
 }
 // 负圈检测
 for (int u = 0; u < n; u++) { // 执行一次全量松弛
 for(int[] v_weight : graph.get(u)){
 int v = v_weight[0], weight = v_weight[1];
 long dv = (long) dists[u] + (long) weight; // 等号右边可能会溢出，临时转为long
 if(dv < dists[v]) { // 发现仍能松弛，表明存在负圈
 System.out.println("Negtive Cycle Found!");
 }
 }
 }
 for(int dist : dists){ // 找最短路长度最大者
 if(dist == INF) return -1; // 存在距离未更新的顶点
 if(dist > max) max = dist;
 }
 return max;
 }
}
```

#### SPFA (BFM)

学习 Bellman-Ford 时我们隐隐感觉到「全量松弛」做了许多无意义的松弛尝试，自然地，我们想能否优化松弛次数，在保证穷尽顶点所有入边松弛这一前提下，尽量少地松弛呢？或者干脆说，我们希望所有的松弛，都是有效松弛，也就是顶点所有入边的松弛是无遗漏且不重复的。本节中，我们将看到 SPFA (BFM) 算法在 BF 的基础上是如何借助队列轻松地实现这一改进的。

> BFM 即 Bellman-Ford-Moore，这一改进由 Edward F. Moore 他于1959 年发表的 [*The shortest path through a maze*](https://mathscinet.ams.org/mathscinet-getitem?mr=0114710) 论文中提出。1994年，西南交通大学的段凡丁在该年4月的《西南交通大学学报》里发表了题为[关于最短路径的SPFA快速算法](https://link.zhihu.com/?target=https%3A//xueshu.baidu.com/usercenter/paper/show%3Fpaperid%3D39798c8bf2d1b5236cdaae3152d490ed%26site%3Dxueshu_se) 的论文，**重新提出了Moore的改进** ，并且给了个比较通俗的名字 Shortest Path Fast Algorithm。

##### 算法描述

[SPFA算法(最短路径快速算法)](https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm)：SPFA 算法是对 BF 算法的一种改进。在BF 算法的说明中我们指出，第 $i$ 次「全量松弛」操作，只有第 $i+1$ 层的顶点距离会被更新至最短，也就是说每次全量松弛中，有效的松弛都是「一层」顶点，这明显地具有 $bfs$ 特点，因此可以考虑不通过「全量松弛」来松弛第 $i+1$ 层顶点，而是以 $bfs$ 的方式，借助队列 $q$ ，每松弛一层顶点，将它们入队，出队时，尝试松弛到其所有邻接顶点的距离，即可在第 $i$ 层顶点出队时松弛第 $i+1$ 顶点并使这些第 $i+1$ 顶点距离取得最小。因为顶点「按层」入队出队，层深最大为 $|V|$ (无负圈图)，因此算法可以结束。

我们还可以这样看，一个顶点 $v$ 的距离能够被更新，隐含着这样一个 **前提** ：$v$ 的前驱 $u$ 的距离被更新过 。因为 $du + |(u, v)| < dv$ 时才会更新 $dv$，而 $|(u, v)|$ 是不变的，初始时 $du$ 和 $dv$ 都是无穷大，所以只有 $du$ 更新 (变小)，$dv$ 才有机会更新 (变小)。从源点出发指向其邻接顶点，对一个连通的有向图，总能遍历所有顶点，每次考察已松弛的顶点 $u$ 是否能松弛其邻接顶点 $v$ ，$v$ 成为已松弛的顶点后再考察是否能松弛 $v$ 的邻接顶点，重复此操作直到「当前已松弛顶点均无法再松弛任何顶点」为止。设置一个队列 $q$，程序开始时置源点s的距离为 0，$s$ 入队。$while$ 对 $q$ 判空，不空时队首顶点 $u$ 出队，松弛其边 (更新 $u$ 的邻接顶点 $v$ 的距离)，根据上述分析，如果 $dv$ 被更新，那它的邻接顶点将 **有机会被更新** ，所以将 $v$ 入队，等待之后出队时尝试松弛 $v$ 的边。 **需要注意的是** ，$v$ 入队前需要检查当前队列中是否已有 $v$ ，若有则无需入队。该检查使得时间复杂度为 $O(|V||E|)$ ， **否则这一复杂度将无法得到保证** 。重复上述过程，当 $q$ 为空时 (无负圈图) 代表所有被更新过距离的顶点，都 **无法再触发其邻接顶点距离的更新** 。也可以说对任意一个顶点 $u$ 来说，$s$ 到 $u$ 的所有路径带来的所有可能的对 $du$ 的更新已被穷尽。程序结束时得到所有顶点到源点的最短路径。

##### 算法过程

1. 建图及初始化。
   1. 构建带权图。
   2. 设置一个大小为 $|V|$ 的距离数组 $dists[]$ ，下标表示顶点。初始化所有顶点到源点 $s$ 的距离为 $Infinity$ ，表示该顶点到 $s$ 的距离尚未确定。
   3. 设置一个大小为 $|V|$ 的距离数组 $inCounts[]$ ，下标表示顶点。记录顶点的入队次，用于负圈检测 (不是必须的)。
   4. 设置一个队列 $q$ 。
   5. 置 $s$ 到其自身距离为 0。
   6. $s$ 入队。

2. 通过 $while(!q.isEmpty())$ 不断将队首顶点 $u$ 出队，对 $u$ **尝试松弛其所有邻边** 。
 1. 对顶点 $u$ 考察其所有邻接顶点 $v$ 是否有 $du + |(u, v)| < dv$，若有，松弛之，即令 $dv = du + |(u, v)|$。同时考察是否有 `inCounts[v] > |V| - 1` ，若满足，说明存在负圈，可直接结束程序，否则 `inCounts[v]++` 。若需要求完整路径，可在松弛的同时更新 $v$ 的前驱为 $u$。

3. $while$ 结束时，(若无负圈) 每个顶点到源点的最短路径距离被求出。

##### 正确性证明 (说明)

SPFA 算法与 BF 算法的核心内容都在于 **穷尽所有路径带来的所有可能的松弛** 。BF 算法通过 $|V|-1$ 次全量松弛来实现这一点，但第 $i$ 次全量松弛中， **有效松弛** 仅作用于第 $i+1$ 层顶点，其他层深顶点不能够被松弛却还是会被尝试，这就产生了冗余操作。SPFA 算法利用前述顶点的距离能够被松弛的隐含前提， **通过队列来减少松弛的次数** 。第 $i$ 层顶点出队时发生的松弛，效果上相当于 BF 算法外层循环第 $i$ 次对所有边的全量松弛。在连通且无负圈的情况下，按层推进一定能够执行最大层深第 $|V|$ 层，因此该算法是正确的。

##### 实例说明

仍以前一张网络图为例考察 SPFA 算法的求解过程，进一步看清其正确性及 SPFA 与 BF 的关系。

第 1 层顶点只有 $s$ ，所以第 2 步 $s$ 出队相当于 BF 算法中第 1 次全量松弛。$a,b,v$ 是第 2 层顶点，所以第 3，4，5 步相当于 BF 算法中第 2 次全量松弛。此时 $v,a,c$ 是第 3 层顶点 (根据所在路径层深的不同，一个顶点可以属于不同层) ，所以接下来的第 6，7 相当于 BF 算法中的第 3 次全量松弛。最后一步使得队列为空，结束。

| 松弛过程 | $ds$       | $da$           | $dc$           | $db$           | $dv$            | 队列 $q$     |
| -------- | ---------- | -------------- | -------------- | -------------- | --------------- | ------------ |
| 1. 初始  | **0 (\*)** | ∞              | ∞              | ∞              | ∞               | s;           |
| 2. s出   | 0          | **∞ > 9**      | ∞              | **∞ > 3 (\*)** | **∞ > 15**      | **a, b, v**; |
| 3. a出   | 0          | 9              | ∞              | 3              | **15 > 14**     | b, v;        |
| 4. b出   | 0          | **9 > 7 (\*)** | **∞ > 5 (\*)** | 3              | 14              | v; **a, c**  |
| 5. v出   | 0          | 7              | 5              | 3              | 14              | a, c;        |
| 6. a出   | 0          | 7              | 5              | 3              | **14 > 12**     | c; **v**     |
| 7. c出   | 0          | 7              | 5              | 3              | **12 > 6 (\*)** | v;           |
| 8. v出   | 0          | 7              | 5              | 3              | 14              | 空           |

```text
1. 初始时令 ds 为0，(*)表示已取得该顶点最短路径。「;」是层的分隔符。
2. s 出队时松弛 (s, a), (s,b), (s, v)。
   且 b 只有一条路径，即经过这趟松弛操作，使得 db = δb。
3. a 出队时松弛 (a, v)，这是 v 的距离第 2 次被松弛。
4. b 出队时松弛 (b, a), (b, c)，a 有两条路径，c 只有一条，
   于是 da = δa，dc = δc。
5. 无可松弛边。
6. a 出队时松弛 (a, v)，这是 v 的距离第 3 次被松弛。
7. c 出队时松弛 (c, v)，这是 v 的距离第 4 次被松弛。
   此时 p(s, v) 所有可能的路径带来的 v 的入边的松弛均已完成，于是 dv = δv 。
8. 无可松弛边，队列空，程序结束。
```

##### 负边图 & 负圈图

-   负边图。**SPFA 能够处理有负权的非负圈图** ，原因与 BF 算法一样，因为算法会处理所有顶点的 **所有入边的松弛** 。

-   负圈图。若图存在负圈，负圈上的顶点将无限循环入队，算法无法结束。

**负圈判定：** 记录每个顶点入队的次数，顶点 $v$ 的距离更新后判断当前更新次数是否超过了 $|V|-1$ 次，若超过则说明存在负圈，若不超过则将更新次数加 1。以层为单位追踪顶点入队出队的过程，不难理解无负圈情况下，一个顶点的距离至多被松弛 (顶点入队) $|V|-1$ 次，若超过则说明存在经过该顶点的负圈。

当图只有一个节点时，要小心处理负圈检测。如下伪代码，次数检测写在次数加一之前可以 **避免单节点图被误判为负圈** 。

```text
if(!q.contains(w)) { // 检查w是否已经在q中
    q.add(w) // 将w加入队列  
    if(w.inCount > |V| - 1) { // 若大于|V|-1则检出负圈
        System.err.println("存在负圈！")
    }
    else w.inCount++ // 记录入队次数
}
```

当然也可以调换次数检测和加一的顺序，并把  $> |V| - 1$ 改成  $> |V|$ ，如下，效果相同。

```text
if(!q.contains(w)) { // 检查w是否已经在q中
    q.add(w) // 将w加入队列  
    w.inCount++ // 记录入队次数
    if(w.inCount > |V|) { // 若大于|V|则检出负圈
        System.err.println("存在负圈！")
    }
}
```

##### Bellman-Ford-Moore 和 SPFA

本节开头我们已经说过，SPFA 实际上应当称作 Bellman-Ford-Moore 算法。根据Wiki词条 [Bellman-Ford algorithm](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm) 的介绍，「对所有的边，简单地松弛 $|V| - 1$ 轮」的朴素 BF 算法在相近的几年里被三个人分别独立发明。只是不知道什么原因算法名称后来定型成了 Bellman-Ford。

```text
1955年 Alfonso Shimbel
1956年 Lester Ford Jr.
1958年 Richard Bellman
```

又过了一年，1959年的时候 Edward F. Moore 提出了 BF 算法的一个[改进](https://link.zhihu.com/?target=https%3A//mathscinet.ams.org/mathscinet-getitem%3Fmr%3D0114710)，即前文的伪代码 (SPFA / Bellman-Ford-Moore) 。

> A variation of the Bellman-Ford algorithm known as [Shortest Path Faster Algorithm](https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm), first described by [Moore (1959)](https://en.wikipedia.org/wiki/Bellman–Ford_algorithm#CITEREFMoore1959), reduces the number of relaxation steps that need to be performed within each iteration of the algorithm.

1994年，西南交通大学的段凡丁在该年4月的《西南交通大学学报》里发表了题为《[关于最短路径的SPFA快速算法](https://link.zhihu.com/?target=https%3A//xueshu.baidu.com/usercenter/paper/show%3Fpaperid%3D39798c8bf2d1b5236cdaae3152d490ed%26site%3Dxueshu_se)》的论文，**重新提出了Moore的改进** ，并且给了个比较通俗的名字 Shortest Path Fast Algorithm。段老师显然没看过 Moore 当初的论文，否则不会给出一个错误的复杂度估计（给出的复杂度是 $O(k|E|)$ ）。有意思的是，现在用 Google 搜 SPFA，即便在英文论坛，许多人对这个改进也称之为 SPFA，而非 BFM，可谓是「喧宾夺主」了。

##### 时空复杂度

时间复杂度：$O(|V||E|)$ 。为严谨说明，列出 SPFA 伪代码如下。

```text
SPFA (Bellman-Ford-Moore) 算法伪代码:
1 Queue q
2 q.add(s) // s的距离初始为0, 其他顶点的距离初始为Infinity
3 while(!q.isEmpty())
4 v = q.remove()
5 for (w : v.adjs) // w是v的邻接顶点
6 if(dv + d(v, w) < dw)
7 dw = dv + d(v, w)
8 if(!q.contains(w)) //检查w是否在当前队列中，不在则入队
9 q.add(w)
```

按层分析很容易得到 SPFA 的复杂度。顶点一层一层地入队出队，一张图最多有 $|V|$ 层 (以 $s$ 为第 1 层)，所以 **按层计** ，任何顶点最多只能入队 $|V| - 1$ 次 (应用第8行入队前检查)。第 1 层顶点个数为 1，其余每层顶点数不会超过 $|V| - 1$ （第8行所保证）。再次强调，虽然一个顶点可能会通过不同的路径重复属于某一层，例如 $s > a > c，s > b > c$ ，$c$ 在第 2 层中出现两次，但有了第 8 行的检查，使得 **一个顶点最多只能在一层顶点里出现一次** 。考虑每层顶点个数小于 $|V|$ ，每层顶点的松弛次数少于 $|E|$ 次，因此复杂度为 $O(|V||E|)$ 。

第 8 行 `if(!q.contains(w))` 是SPFA 作为改进 BF 的关键，有必要继续进一步说明为何加了这个检查优化 **不影响结果的正确性** 。假设从 $s$ 经过长度相同的不同路径到达若干个不同顶点，这些顶点都指向 $v$ ，每条路径带来的松弛都能执行到 (BFS 所保证)，只是除了第一次之外不把 $v$ 放入队列。将 $v$ 放入队列的目的是在之后使其邻接顶点 $w$ 有被松弛的机会。对于 $w$ ，来自 $v$ 的松弛机会只需一次即可，所以无需每次都将 $v$ 放入队列中。

SPFA 每出队第 $i$ 层顶点，使得在最短路径上第 $i+1$ 层的顶点得到松弛。不厌其烦地，SPFA第 $i$ 层顶点出队的效果等同于 BF 第 $i$ 轮对边的全量松弛的效果，比 BF 的操作更有效率的地方在于，SPFA 仅仅松弛它够得着得邻边。BF 暴力地松弛所有边，但有效的只有第 $i+1$ 层，其他更深或更浅的顶点无法松弛，但一律以 `if(dv + |(v, w)| < dw)` 询问了一次。于是，SPFA 便实现了对顶点的 **「无遗漏且不重复」** 的松弛这一改进。

空间复杂度：存图空间 $O(|V|+|E|)$ ， $dists/inCounts/q$ 空间 $O(|V|)$。总体为线性空间复杂度 $O(|V|+|E|)$ 。

对时间复杂度的分析可以看出，稀疏图中顶点 $v$ 的 $p(s, v)$ 路径平均条数很少，相比 BF，SPFA 实际运行速度会很快，稠密图下则无明显优势。

##### 代码

如下是 [743. 网络延迟时间](https://leetcode.cn/problems/network-delay-time/) 的 SPFA(BFM) 解法。代码中应用了「负圈检测」，由于本题已保证了不存在负值边，也就不存在负圈，因此负圈检测可以省略。

此代码是 SPFA 算法的较为普遍的写法 (带负圈检测)，读者应熟练掌握。

```java
// SPFA(BFM)+负圈检测
class Solution {
 public int networkDelayTime(int[][] times, int n, int k){
 List<List<int[]>> graph = new ArrayList<>();
 for(int i = 0; i < n; i++) graph.add(new ArrayList<>());
 for(int[] edge : times){ // 建带权图
 int u = edge[0] - 1, v = edge[1] - 1, weight = edge[2];
 graph.get(u).add(new int[]{v, weight});
 }
 int max = 0, INF = Integer.MAX_VALUE; // max为距离源点最远顶点的距离，INF为所有顶点距离初始值
 int[] dists = new int[n], inCounts = new int[n]; // inCounts记录顶点入队次数，用于负圈检测
 Arrays.fill(dists, INF); // 距离初始化
 dists[k - 1] = 0; // 源点距离置0
 Queue<Integer> q = new ArrayDeque<>();
 q.add(k - 1); // 源点入队
 while(!q.isEmpty()){
 int u = q.remove();
 for(int[] v_weight : graph.get(u)){ // 松弛u的邻接顶点
 int v = v_weight[0], weight = v_weight[1];
 int dv = dists[u] + weight;
 if(dv < dists[v]){
 dists[v] = dv;
 if(!q.contains(v)) { // 入队的前提是此时v不在q中，否则程序虽正确，但复杂度将不再是O(|V||E|)
 q.add(v);
 if(inCounts[v] > n - 1) { // 负圈检测 (本题不需要)
 System.out.println("Negtive Cycle Found!");
 return -1;
 }
 else inCounts[v]++;
 }
 }
 }
 }
 for(int dist : dists){ // 找最短路长度最大者
 if(dist == INF) return -1; // 存在距离未更新的顶点
 if(dist > max) max = dist;
 }
 return max;
 }
}
```

### 带权全源最短路

在「带权单源最短路」中，我们介绍了 Dijkstra / DAG SSSP (归为特殊 Dijkstra) / Bellman-Ford / SPFA (BFM) 最短路算法。若想求图上任意两点的距离，在这些算法中将不得不一个个计算，我们不禁会想，有没有什么算法可以一次求解所有顶点对 (all pairs) 的最短路径呢？本节我们介绍的就是这样一种一次性求解所有点对最短距离的算 Floyd-Warshall 算法。

> Jeff Erickson 在他的 *Algorithms* 一书的 9.8 节开头，介绍了 Floyd-Warshall 算法被多人相继独立发明 (发现) 的历史。
>
> ...A difffferent formulation of shortest paths that removes this logarithmic factor was proposed twice in 1962, first by Robert Floyd and later independently by Peter Ingerman, both slightly generalizing an algorithm of Stephen Warshall published earlier in the same year. In fact, Warshall’s algorithm was previously discovered by Bernard Roy in 1959, and the underlying recursion pattern was used by Stephen Kleene in 1951.

除了展示 Floyd-Warshall 算法可用于解决求单源最短路的 [743. 网络延迟时间](https://leetcode.cn/problems/network-delay-time/) 一题，我们还会展示更适合用它来求解的全源最短路问题 [1334. 阈值距离内邻居最少的城市](https://leetcode.cn/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/) 。

#### Floyd-Warshall

[Floyd-Warshall算法(弗洛伊德算法)](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm): 求解图中任意两点的最短路径的算法。算法以 3 重循环考察任意顶点 $i$ 到任意顶点 $j$ 是否有经过任意顶点 $k$ 的可松弛路径，即对每一个顶点 $k$ (外层循环)，考察是否有 $d(i, k) + d(k, j) < d(i, j)$ ，若有则更新 $d(i, j) = d(i, k) + d(k, j)$ 。

可以这样理解其工作过程。已知确定的任意两点 $i, j$ 间有确定的最短路径 $p(i, j)$ （只要无负圈，必有最短路径，不连通时最短路径长度为 $Infinity$ ），$p(i, j)$ 由多次松弛操作得到。先假设算法是正确的 (详细证明见后述)，那么在 $p(i, j)$ 的最后一次松弛后 (通过顶点 $y$ 松弛)，得到 $p(i, j) = p(i, y) + p(y, j)$ 。同理，$p(i, y)$ 和 $p(y, j)$ 是 $p(i, j)$ 的两个部分，它们由之前的松弛操作得到。例如松弛顶点 $x$ 后得到 $p(i, y)$ ，可知 $p(i, y) = p(i, x) + p(x, y)$ ，松弛顶点 $z$ 后得到 $p(y, j)$ ，可知 $p(y, j) = p(y, z) + p(z, j)$ 。路径 $p(i, j)$ 的构建过程可以一直拆分溯源到某三个相邻顶点的连接。例如在 $p(i, j)$ 上有三个相邻顶点为 $i > a > b$ ，那么在外层循环处理 $a$ ，中层循环处理 $i$ ，内层循环处理 $b$ 时，松弛操作将 $i > a > b$ **「连接起来」**（因为 **最短路径上的任意子路径都是最短的** ，必松弛）。顺着算法执行过程不难看出，算法通过外循环的 $k$ 来连接边，通过不断连接短路径产生长路径，最终增长为完整的最短路径。

在「正确性证明 (说明)」中我们将进一步透过「动态规划」来把握该算法正确性。

##### 算法过程

1. 建图及初始化。

1. 构建带权图。在 Floyd-Warshall 算法中，以「邻接矩阵」构建带权图是更方便也更普遍的做法。
   2. 设置一个大小为 $|V|*|V|$ 的距离矩阵 (二维数组) $dists[][]$ ，下标表示顶点。初始化所有顶点对距离为 $Infinity$ ，表示所有点对间距离尚未确定。若要求输出入境本身，还需设置一个 $|V|*|V|$ 大小的路径信息矩阵。

2. 外层循环执行  $|V|$ 次， 每次固定顶点 $k$。

1. 中层循环执行 $|V|$ 次，每次固定顶点 $i$ 。

1. 内层循环执行 $|V|$ 次，每次固定顶点 $j$ 。

考察是否有 $d(i, k) + d(k, j) < d(i, j)$ ，若有，松弛之，即令 $d(i, j) = d(i, k) + d(k, j)$ 。若要求输出入境本身，还要对应更新路径信息矩阵。

3.  外层循环结束时，(若无负圈) 所有顶点对的最短路径距离被求出。

4.  检查图是否有负圈。再次对所有边执行松弛操作， **若有边可被松弛，则有负圈** ，结束程序，否则正常结束，所有顶点最短路径被求出。

※ 以下展示如何通过路径信息的矩阵 $p$ ，递归地输出路径。

$p[i] [j]$ 的值是 $k$ ，即 $i$ 经过 $k$ 到 $j$ ，在每次松弛时更新 $k$ 。例如有最短路径 $i > a > b > c > j$ 。程序结束后得到的路径信息矩阵如下。

| 顶点 | $i$    | $a$    | $b$    | $c$    | $j$    |
| ---- | ------ | ------ | ------ | ------ | ------ |
| $i$  | $null$ | $null$ | $a$    | $null$ | $b$    |
| $a$  | $null$ | $null$ | $null$ | $null$ | $null$ |
| $b$  | $null$ | $null$ | $null$ | $null$ | $c$    |
| $c$  | $null$ | $null$ | $null$ | $null$ | $null$ |
| $j$  | $null$ | $null$ | $null$ | $null$ | $null$ |

利用该矩阵，通过递归即可找到 $i > a > b > c > j$ 。递归过程大致如下，顶点输出顺序即为路径顺序。

```
i > j, 找到b
  i > b，找到a
    i > a为null，输出i
    a > b为null，输出a
  b > j，找到c
    b > c为null，输出b
    c > j为null，输出c
 最后输出j
```

##### 正确性证明 (说明)

该算法的 **本质是动态规划** ，以状态转移方程的形式描述如下，其中 $dp[k][i][j]$ 表示 **经过前 $k$ 个顶点的松弛，得到的顶点 $i$ 到顶点 $j$ 的最短路径长度** 。注意第一维的 $k$ 表示 $k$ 个顶点，第二维和第三维表示具体的顶点。

```
1. 定义: dp[k][i][j] 表示经过前 k 个顶点的松弛，得到的顶点 i 到顶点 j 的最短路径长度。
2. 边界: dp[0][i][j] = Infinity
3. 递推: dp[k][i][j]  = min{dp[k-1][i][j], dp[k-1][i][k]  + dp[k-1][k][j]}
```

最短路径 **不经过** 第 $k$ 个顶点 (顶点 $k$ ): $dp[k][i][j] = dp[k-1][i][j]$

最短路径 **经过** 第 $k$ 个顶点 (顶点 $k$ ):   $dp[k][i][j] = dp[k-1][i][k] + dp[k-1][k][j]$

```java
// floyd核心伪代码
for(k : V)
 for(i : V)
 for(j : V)
 if(d(i, k) + d(k, j) < d(i, j))
 d(i, j) = d(i, k) + d(k, j)
```

补充说明：已知点 $i, j$ 之间的最短路径为 $p(i, j)$ ，那么 $p(i, j)$ 上的任意两点 $a, c$ 的最短路径确定在 $p(i, j)$ 上。反证法简单可证。假设 $p(i, j)$ 上两点 $a, c$ 之间的最短路径经过一不在 $p(i, j)$ 上的顶点 $b$ ，那 $i, j$ 的最短路径也就不是 $p(i, j)$ ，而是 $p(i, a) + p(a, b) + p(b, c)+ p(c, j)$ 。

##### 实例分析

下面通过一个例子观察 Floyd 算法的动态规划过程，对其正确性可以有更直观的感受。由于算法总是在整张图上进行处理，展示整张图将使过程变得杂乱，因此我们只选取一条 $i$ 到 $j$ 的最短路径，展现该路径的构建过程。由于这条路径是随意选取的，其他所有在图上的 **任意两点** 的路径的构成都是类似的。

设图 $G$ 中 $i, j$ 间最短路径 $p$ 为  $i > a > b > c > d > e > f > g > h > j$ 。最外层循环对该路径上顶点的处理顺序可以是任意顺序，例如 $b, h, i, g, a, e, j, f, c, d$ (分别标上序号 1, 2, 3, 4, 5, 6, 7, 8, 9, 10，表示外层循环处理的先后顺序)。现在我们以溯源的方式从处理最后一个顶点 $d$ 得到 $d(i, j)$ 开始观察，且只观察程序对上述十个顶点的处理（对其他顶点的处理形成其他路径）。该路径的取得只与三个循环对该路径上的顶点的操作有关，循环对其他顶点的操作不影响结果，因为其他顶点不在该最短路径上，由它们导致的松弛不影响路径 $p$ ，或者说 $p$ 会从若干条 $i$ 到 $j$ 的路径中胜出。

外层循环处理 $d$ 之后由 $d(i, d) + d(d, j)$ 的结果得到 $i$ 到 $j$ 的最短路径长 $d(i, j)$ ，因此 $d(i, d)$ 和 $d(d, j)$ 此时必是已知的。继续溯源，看看 $d(i, d)$ 和 $d(d, j)$ 是如何得到的。到 $d$ 的路径上 $c$ 是最后被处理的，处理 $c$ 时计算 $d(i, d) = d(i, c) + d(c, d)$ ，其中 $d(c, d)$ 是边长，这是程序开始时已知， $d(i, c)$ 需要继续溯源， $d(i, c) = d(i, a) + d(a, c)$ ，其中 $d(i, a)$ 是边长， $d(a, c) = d(a, b) + d(b, c)$ ， $d(a, b)$ 和 $d(b, c)$ 是边长。其余过程如图，标红处表示相邻的顶点的边长，在程序开始时得到。

可以看出，外层循环处理 i 到 j 的最短路径的所有顶点的过程中，先处理的顶点得到 **子路径总能够为后处理的顶点构建更长的子路径** ，直到处理 (最短路径上的) 最后一个顶点时，将两个子路径连接起来形成最终的最短路径，这正是动态规划过程的体现。

不同于 BF 动态规划过程的单串 $O(1)$ 依赖，Floyd 动态规划是单串 **$O(n)$ 依赖** 的。也可以描述为某一次的松弛形成的路径 **不一定直接作用于下一次松弛** ，而是在之后某一次松弛中发生作用。例如处理 $b(1)$ 和处理 $h(2)$ 是外层循环的两次相邻的操作，它们分别产生了两条不相连的子路径 $a>b>c$ 和 $g>h>j$ 。之后外层循环处理 $a(5)$ 时 $a>b>c$ 增长为 $i>a>b>c$ ，处理 $c(9)$ 时增长为 $i>a>b>c>d$ 。 $g>h>j$ 在外层循环处理 $g(4)$ 时增长为 $f>g>h>j$ ，处理 $f(8)$ 时增长为 $d>e>f>g>h>j$  ( $d>e>f$  在外层循环处理 $e(6)$ 时得到)。最终在处理 $d(10)$ 时得到 $i > a > b > c > d > e > f > g > h > j$ 。

![image.png](https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/posts_img/algorithms/graph/floyd-example.png)

![flyod_demo.gif](https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/posts_img/algorithms/graph/floyd-example-gif.gif)

总结 Floyd 算法的过程，外层循环执行完第 $k$ 次，给出由 $k+1$ 条边组成的路径，下一次会利用长度为 $1, 2, ... , k+1$ 的路径连接出长度为 $k+2$ 的路径。这就好像将任意两点连成单边线（只要这两点之间存在路径），然后再将两条单边线作为零件连成长度为 2 的线，因为具备所有单边线，所以无论长度为 2 的线是由哪些单边线组成的，都可以找到并连起来。然后再利用长度为 1，2 的线作为零件连成长度为 3 的线，因为无论一条长度为 3 的线是如何构成的，构成它的单边线和 2 边线都已具备。以此类推直到连出所有可能长度的线。

##### 负边图 & 负圈图

-   负边图。**Floyd-Warshall 能够处理有负权的非负圈图** ，原因与 BF 算法一样，因为算法会处理所有顶点的 **所有入边的松弛** 。

-   负圈图。当图存在负圈时，$s$ 到圈上任意顶点的距离都可以通过不断绕圈趋于无限小。因此若不能保证输入的图无负圈，可以在 3 重循环后再执行一次全量松弛，若仍有边可被松弛，说明存在负圈。

##### 时空复杂度

时间复杂度: 3 重循环，$O(|V|^3)$ 。

空间复杂度: 邻接矩阵、距离矩阵、路径信息矩阵 (若有的话) 均为 $O(|V|^2)$ 。总的空间复杂度为 $O(|V|^2)$ 。

##### 代码

如下是 [743. 网络延迟时间](https://leetcode.cn/problems/network-delay-time/) 的 Floyd-Warshall 解法。代码中应用了「负圈检测」，由于本题已保证了不存在负值边，也就不存在负圈，因此负圈检测可以省略。另外，此实现采用了 **「邻接矩阵」** 存图。

此代码是 Floyd-Warshall 算法的较为普遍的写法 (带负圈检测)，读者应熟练掌握。

```java
// Floyd-Warshall (带负圈检测)
class Solution {
 public int networkDelayTime(int[][] times, int n, int k){
 int[][] dists = new int[n][n];
 int max = 0, INF = Integer.MAX_VALUE; // max为距离源点最远顶点的距离，INF为所有顶点距离初始值
 for(int[] distRow : dists) Arrays.fill(distRow, INF); // 距离初始化
 for(int u = 0; u < n; u++) dists[u][u] = 0; // 顶点到自身距离为0
 for(int i = 0; i < times.length; i++){ // 建图 (邻接矩阵)
 int u = times[i][0] - 1, v = times[i][1] - 1, weight = times[i][2];
 dists[u][v] = weight;
 }
 for(int k1 = 0; k1 < n; k1++) { // 对所有顶点 k
 for (int i = 0; i < n; i++) { // 对所有顶点 i
 for(int j = 0; j < n; j++){ // 对所有顶点 j
 long ik = dists[i][k1], kj = dists[k1][j], ij = dists[i][j]; // 为防止溢出，临时转为 long
 if(ik + kj < ij) { // 松弛条件
 dists[i][j] = (int) (ik + kj);
 }
 }
 }
 }
 for(int dist : dists[k - 1]){ // 注意题目为「单源」
 if(dist == INF) return -1; // 存在距离未更新的顶点
 if(dist > max) max = dist;
 }
 // 负圈检测
 for (int u = 0; u < n; u++) { // 全量松弛
 for(int v = 0; v < n; v++){
 long dv = (long) dists[k - 1][u] + (long) dists[u][v]; // 等号右边可能会溢出，临时转为long
 if(dv < dists[k - 1][v]) { // 松弛条件
 System.out.println("Negtive Cycle Found!");
 }
 }
 }
 return max;
 }
}
```

现在，我们展示 Floyd-Warshall 解决 [1334. 阈值距离内邻居最少的城市](https://leetcode.cn/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/) 一题的代码如下。该题是典型的「所有点对」最短距离问题。求解过程十分简单。

1. 应用 Floyd-Warshall 算法求出所有点对间最短距离，存于矩阵 $dists[][]$ 中。
2. 遍历 $dists$ 矩阵，统计每一个顶点在距离阈值内 (小于等于) 的邻接顶点个数，实时地记录其中最小者。
3. 因为 $u$ 是从小到大遍历的，若有多个满足要求的顶点，记录的就是编号最大的那一个。

```java
class Solution {
 public int findTheCity(int n, int[][] edges, int distanceThreshold) {
 int INF = Integer.MAX_VALUE;
 int[][] dists = new int[n][n];
 for(int[] distRow : dists) Arrays.fill(distRow, INF);
 for(int u = 0; u < n; u++) dists[u][u] = 0;
 for(int[] edge : edges){
 int u = edge[0], v = edge[1], weight = edge[2];
 dists[u][v] = weight;
 dists[v][u] = weight;
 }
 for(int k = 0; k < n; k++){ // floyd求出dists
 for(int i = 0; i < n; i++){
 for(int j = 0; j < n; j++){
 long ik = dists[i][k], kj = dists[k][j], ij = ik + kj;
 if(ij < dists[i][j]){
 dists[i][j] = (int) ij;
 }
 }
 }
 }
 int ans = 0, minCount = n;
 for(int u = 0; u < n; u++){ // 遍历dists寻找答案
 int count = 0;
 for(int v = 0; v < n; v++){
 if(dists[u][v] <= distanceThreshold) count++;
 }
 if(count <= minCount) {
 minCount = count;
 ans = u;
 }
 }
 return ans;
 }
}
```

### 小结

总结「最短路径」算法如下。

| 算法                | 时间复杂度 | 负边 | 正圈        | 负圈         |
| ------------------- | ---------- | ---- | ----------- | ------------ |
| **无权 SSSP**       |            |      |             |              |
| ● 朴素版            | $O(V^2)$   | -    | Yes         | -            |
| ● 队列版            | $O(V+E)$   | -    | Yes         | -            |
| **带权 SSSP**       |            |      |             |              |
| ● Dijkstra 朴素版   | $O(V^2)$   | No   | Yes         | No(不可检测) |
| ● Dijkstra 小顶堆版 | $O(ElogV)$ | No   | Yes         | No(不可检测) |
| ● Dijkstra DAG      | $O(V+E)$   | Yes  | No (可检测) | No (可检测)  |
| ● Bellman-Ford      | $O(VE)$    | Yes  | Yes         | No (可检测)  |
| ● SPFA (BFM)        | $O(VE)$    | Yes  | Yes         | No (可检测)  |
| **带权 APSP**       |            |      |             |              |
| ●Floyd-Warshall     | $O(V^3)$   | Yes  | Yes         | No (可检测)  |

※ 本文未涉及「无权 APSP」，无权图的所有点对最短路可通过对所有顶点执行无权单源最短路算法求得，时间复杂度为 $O((|V|+|E|)*|V|)$ 。对此问题有更多兴趣的读者可参考 [All pairs shortest path in undirected and unweighted graphs](https://math.stackexchange.com/questions/58198/all-pairs-shortest-path-in-undirected-and-unweighted-graphs) 。

※ 空间复杂度主要取决于建图方式，以「邻接矩阵」建图时为 $O(|V|^2)$，以「邻接表」建图时为 $O(|V|+|E|)$ ，表中不再列出。

## 最小生成树

在最短路径问题中，研究的是如何找到图中两点的最短路径，当我们将整张图作为对象考虑时，很自然地会想，在图上所有顶点都互相连通的基础上，如何找到最小的总路径和呢？这有点像是 **以图为整体的「最短路径」** 。很容易找到这个问题的现实意义，例如给一个科技园区铺装光纤，要求所有办公楼和厂房都互相连通且尽可能节省光纤用量。办公楼和厂房为图中顶点，互相之间的距离为边权，该场景实际上是要求找到能将所有顶点连通且边权和最小的边集。这个边集就是本节要介绍的 **「最小生成树」** 。

[最小生成树 ( *Minimum Spanning Tree, MST* )](https://en.wikipedia.ahmu.cf/wiki/Minimum_spanning_tree): 通常指的无向图中的一个边集，该边集使得图中所有顶点互相连通，且边权总和最小。由于此边集构成的子图必然无圈，该子图为一棵树，因此称该边集为「最小生成树」。

本节讲解求图上 MST 的两种算法:  Prim 和 Kruskal，我们将看到前者几乎和 Dijkstra 一致，而后者只是并查集思想的简单应用。同样，为了在学习这两个算法过程中及时得到反馈，我们将以 [1135. 最低成本联通所有城市](https://leetcode.cn/problems/connecting-cities-with-minimum-cost/) 一题作为配套，有了 Dijkstra 和并查集的基础，MST 的学习是十分轻松的。

### Prim

Prim 算法与 Dijkstra 算法无论是从思想还是实际代码表现上都非常类似，在理解了 Dijkstra 的基础上，学习 Prim 几乎没有思考成本。后续我们以一个表格逐行比较二者的内容，读者将发现 **二者最根本的差别只在于顶点距离的更新方法** 。由于有了 Dijkstra 的基础，行文中，我们着重对比二者，对 Prim 算法只做必要的简略讲解。我们仍循前例，先介绍「朴素版」再介绍「优先队列版」。读者务必在阅读本节之前还阅读 Dijkstra 章节。

> 与之前的几个算法类似，Prim算法也曾被多人在不同时间相继独立发明 (发现) 。Jeff Erickson 在他的 *Algorithms* 一书的 7.4 节开头，做了如下介绍。
>
> The next oldest minimum spanning tree algorithm (Prim's algorithm) was first described by the Czech mathematician Vojtěch Jarník in a 1929 letter to Borůvka; Jarník published his discovery the following year. The algorithm was independently rediscovered by Joseph Kruskal in 1956, (arguably) by Robert Prim in 1957, by Harry Loberman and Arnold Weinberger in 1957, and finally by Edsger Dijkstra in 1958. Prim, Lobermand and Weinberger, and Dijkstra all (eventually) knew of and even cited Kruskal’s paper, but since Kruskal also described two other minimum spanning-tree algorithms in the same paper, *this* algorithm is usually called “Prim’s algorithm”, or sometimes “the Prim/Dijkstra algorithm”, even though by 1958 Dijkstra already had another algorithm (inappropriately) named after him.
>
> Jeff Erickson 在他的书中几乎只将此算法称为 Jarník 算法，不过本文还是按照流行的说法称为 Prim 算法。

#### 朴素版

##### 算法描述

[Prim (普里姆算法)](https://en.wikipedia.ahmu.cf/wiki/Prim%27s_algorithm):  一种基于贪心思想的求解无向图上 MST 的算法。我们直接将 Prim 算法和 Dijkstra 二者对比如下。

| Dijkstra | Prim |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
| 贪心算法 | 贪心算法 |
| 顶点分为 **距离已确定** 和 **距离未确定** 顶点 | 顶点分为 **距离已确定 (已加入生成树)** 和 **距离未确定 (未加入生成树)** 顶点 |
| 所有顶点距离初始化为 $Infinity$ | 所有顶点距离初始化为 $Infinity$ |
| 源点 $s$ 的距离初始化为 0 | 生成树起始点 $s$ 的距离初始化为 0 |
| 以一个循环寻找 **当前距离未确定顶点中距离最小者** $u$ ， 立即置 $u$ 的距离为「已确定」。 | 以一个循环寻找 **当前距离未确定顶点中距离最小者** $u$ ， 立即置 $u$ 的距离为「已确定」。 |
| 尝试以如下方式更新 (松弛) $u$ 的邻接顶点的距离 $dv = min(dv, du + d(u, v))$ | 尝试以如下方式更新 $u$ 的邻接顶点的距离 $dv = min(dv, d(u,v))$ |
| $while$ 结束时所有顶点最短路径及其距离被求出 | $while$ 结束时 MST 及其所有边权被求出 |

我们看到这两个算法的每一步都几乎相同，不同点主要有三处，最主要的是第 3 点。

1. Prim 用于在「无向图」中求 MST，因此建图时要「双向建边」。Dijkstra 应用于有向图时单向建边，应用于无向图时双向建边。
2. Dijkstra 中的「距离」指的是顶点到源点的距离。Prim 中的「距离」指的是顶点到其已在生成树上的邻接顶点 (父顶点) 的距离。
3.  **顶点距离更新方式不同** 。

##### 算法过程

1. 建图及初始化。
   1. 构建双向带权图。
   2. 设置一个大小为 $|V|$ 的用于标记顶点距离是否「已确定」的 $boolean$ 数组 $visited[]$ ，下标表示顶点。
   3. 设置一个大小为 $|V|$ 的距离数组 $dists[]$ ，下标表示顶点。初始化所有顶点的距离为 $Infinity$ ，表示所有顶点的距离尚未确定。
   4.  **任意选取** 一个顶点作为起始顶点，置距离为 0，通常我们将第一个顶点的距离置为 0 。

2. 以一个循环寻找 **当前距离未确定顶点中距离最小者** $u$ ，立即置 $u$ 的距离为「已确定」。
3. 距离更新。尝试更新 $u$ 的所有 **距离未确定的** 邻接顶点 $v$ 的距离 $dv$。即 $dv = min\{dv, |(u,v)|\}$ 。

4. 循环结束时，所有顶点距离被求出，也就是 MST 所有边权被求出。

##### 正确性证明

> 如下证明参考了 [参考1](https://home.uncg.edu/cmp/faculty/srtate/330/primsproof.pdf) 以及 [参考2](https://www.cnblogs.com/sky-view/p/3250972.html)。

虽然 Prim 算法过程与 Dijkstra 类似，但证明过程并不通用。如下是 Prim 算法的证明过程。

证明：在图 $G$ 上执行 Prim 算法得到的生成树 $S$ 是 MST。

1. 记 $G$ 上的 MST (之一) 是生成树 $S_{min}$，即证明 $|S| = |S_{min}|$ ，绝对值表示生成树的边权和。
2. 在 $S$ 生长过程中，**首次** 遇到的不属于 $S_{min}$ 的边为 $e=(u, v)$ ，$u$ 在此前得到的点集中，$v$ 在剩余的顶点中。从 $S$ 中拿走 $e$ ，则 $S$ 剩下的不连通的两部分分别为包含 $u$ 的子树 $U$ 以及包含 $v$ 的子树 $V$ 。
3. $S_{min}$ 是 MST，其上必存在 $u$ 到 $v$ 的路径，且已知 $u$ 在 $U$ 中，$v$ 在 $V$ 中，由于 $(u,v)∉S_{min}$ ，则必然存在边 $f=(a,b)∈S_{min}$ 穿过 $U → V$，即 $a$ 在 $U$ 中， $b$ 在 $V$ 中  (若 $a$ 是 $u$ ，则 $b$ 不是 $v$；若 $b$ 是 $v$，则 $a$ 不是 $u$) 。
4. 当 $e$ 即将被加入 $S$ 时，顶点 $a$ 已在 $U$ 中 ( $U$ 是 $S$ 当前生长到的部分)。
   1. 此时 $a$ 是「距离未确定」的顶点。因为如果 $a$ 是距离已确定的顶点，则在 $U$ 中存在一条边 $g$ 连接 $a$ 和另一顶点，我们已经知道 $e$ 是 $S$ 生长过程中 **首次** 遇到的不属于 $S_{min}$ 的边，也就是说 $g∈S_{min}$ ，这与 $f∈S_{min}$ 矛盾，因为 $a$ 一旦「距离确定」，后续就不会考察 $a$ 的连边，$f$ 也就不可能加入 $S_{min}$ 。
   2. 由于 $a$ 是「距离未确定」的顶点，考察顶点 $u$ 的连边时，顶点 $a$ 的连边也一定会被考察。由于 $e$ 在此轮考察中被 Prim 算法选入 $S$ 中，而 $f$ 未被选择，可知 $|e|≤|f|$ 。

5. 对于 $S_{min}$ ，断开 $f=(a,b)$ ，则 $S_{min}$ 被分成不连通的两棵子树 $A$ 和 $B$，且 $u → a → b → v$ 被断开，说明 $u$ 与 $v$ 分别在不连通的两棵子树 $A, B$ 上。此时连上 $e=(u,v)$ 得到的 $S_{AeB}$ 显然是一棵生成树。因为 $|e|≤|f|$ ，则必然有 $|e|=|f|$ ， 否则 $S_{AeB}$ 边权之和更小，与 $S_{min}$ 是 MST 矛盾。因此 $|S_{AeB}|=|S_{min}|$，即 $S_{AeB}$ 也是 MST。
6. 重复上述过程，继续考察 $S$ 中下一条不属于 $S_{min}$ 的边，直到得到 $S$ 。每一次考察，都可以得到上述 5 的结论，最终有 $|S|=|S_{min}|$，即 $S$ 是 MST。

![image.png](https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/posts_img/algorithms/graph/prim-proof.png)

##### 时空复杂度

与朴素版 Dijkstra 算法相同，不赘述。

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

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

##### 代码

[1135. 最低成本联通所有城市](https://leetcode.cn/problems/connecting-cities-with-minimum-cost/) 一题是非常典型的求 MST 的题目，应用本节的朴素 Prim 解法轻松可解，而且你会发现，只需对 [743. 网络延迟时间](https://leetcode.cn/problems/network-delay-time/) 的朴素 Dijkstra 解法做几行修改即可得到此代码。求解时需要注意以下两点。

- 构建带权图时要双向建边。
- 当存在距离未更新的顶点时说明图不连通时，返回 -1。

```java
class Solution {
 public int minimumCost(int n, int[][] connections){
 List<List<int[]>> graph = new ArrayList<>();
 for(int i = 0; i < n; i++) graph.add(new ArrayList<>());
 for(int[] edge : connections){ // 建带权图
 int u = edge[0] - 1, v = edge[1] - 1, weight = edge[2];
 graph.get(u).add(new int[]{v, weight}); // 建边 (u,v)
 graph.get(v).add(new int[]{u, weight}); // 建边 (v,u)
 }
 int sum = 0, INF = Integer.MAX_VALUE; // max为距离源点最远顶点的距离，INF为所有顶点距离初始值
 int[] dists = new int[n];
 boolean[] visited = new boolean[n];
 Arrays.fill(dists, INF); // 距离初始化
 dists[0] = 0; // 生成树起始点距离置0 (可任选一个顶点)
 int u = -1; // 当前距离未确定顶点中的距离最小者
 while((u = getMin(dists, visited)) != -1) { // 遍历顶点，寻找当前距离未确定顶点中的距离最小者
 visited[u] = true; // 立即置为距离已确定
 for (int[] v_weight : graph.get(u)) {
 int v = v_weight[0], weight = v_weight[1];
 if(!visited[v]) { // 对于u的距离未确定的邻接顶点v，更新v的距离
 if(weight < dists[v]) { // 更新条件
 dists[v] = weight; // 更新dv
 }
 }
 }
 }
 for(int dist : dists){ // 计算 MST 边权和
 if(dist == INF) return -1; // 若有不连通的城市，返回 -1
 sum += dist;
 }
 return sum;
 }
 private int getMin(int[] dists, boolean[] visited){ // 在当前距离未确定的顶点中找距离最小者
 int n = dists.length, min = Integer.MAX_VALUE, minVertex = -1;
 for (int u = 0; u < n; u++) {
 if(!visited[u] && dists[u] < min) { 
 min = dists[u];
 minVertex = u;
 }
 }
 return minVertex;
 }
}
```

#### 优先队列版

##### 算法描述

与 Dijkstra 一样，Prim 也可用优先队列 (小顶堆) 优化，内容一致，不赘述。

##### 算法过程

1. 建图及初始化。
   1. 构建双向带权图。
   2. 设置一个小顶堆 $pq$ 。
   3. 设置一个大小为 $|V|$ 的用于标记顶点距离是否「已确定」的 $boolean$ 数组 $visited[]$ ，下标表示顶点。
   4. 设置一个大小为 $|V|$ 的距离数组 $dists[]$ ，下标表示顶点。初始化所有顶点距离为 $Infinity$ ，表示所有顶点距离尚未确定。
   5. 置任意一个顶点的距离为 0，通常我们将第一个顶点的距离置为 0 。
   6. 上述顶点入堆。
2. 一次出堆完成一个顶点距离的确定，即将该顶点加入 MST。以 $while$ 循环对 $pq$ 判空，若不空，堆顶顶点 $u$ 出堆，此时 $u$ 为距离未确定顶点中距离最小者，置 $u$ 的距离为已确定。
3. 更新操作。尝试更新 $u$ 的所有 **距离未确定的** 邻接顶点 $v$ 的距离 $dv$。即 $dv = min\{dv, |(u,v)|\}$ 。
4. 循环结束时，所有顶点距离被求出，也就是 MST 所有边权被求出。

##### 时空复杂度

与优先队列版 Dijkstra 算法相同，不赘述。

时间复杂度：$O(|E|log|V|)$

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

同样地，当图为 **「稠密图」** 时，采用更优的「朴素版」；当图为 **「稀疏图」** 时，采用更优的「优先队列版」。

##### 代码

现在，我们给出如下利用优先队列的 Prim 算法代码来解决 [1135. 最低成本联通所有城市](https://leetcode.cn/problems/connecting-cities-with-minimum-cost/) 。同样地，只需对 [743. 网络延迟时间](https://leetcode.cn/problems/network-delay-time/) 的优先队列版 Dijkstra 解法做几行修改即可得到此代码。

```java
class Solution {
 public int minimumCost(int n, int[][] connections){
 List<List<int[]>> graph = new ArrayList<>();
 for(int i = 0; i < n; i++) graph.add(new ArrayList<>());
 for(int[] edge : connections){ // 建带权图
 int u = edge[0] - 1, v = edge[1] - 1, weight = edge[2];
 graph.get(u).add(new int[]{v, weight}); // 建边 (u,v)
 graph.get(v).add(new int[]{u, weight}); // 建边 (v,u)
 }
 int sum = 0, INF = Integer.MAX_VALUE; // sum为MST边权和，即本题所求。INF为所有顶点距离初始值。
 int[] dists = new int[n];
 boolean[] visited = new boolean[n];
 Arrays.fill(dists, INF); // 距离初始化
 dists[0] = 0; // 生成树起始点距离置0 (可任选一个顶点)
 PriorityQueue<int[]> pq = new PriorityQueue<>((u, v) -> u[1] - v[1]); // 小顶堆
 pq.add(new int[]{0, 0}); // 起始点入堆
 while(!pq.isEmpty()) { 
 int[] u_dist = pq.remove();
 int u = u_dist[0];
 if(visited[u]) continue;
 visited[u] = true; // 立即置u的距离为已确定
 for (int[] v_weight : graph.get(u)) {
 int v = v_weight[0], weight = v_weight[1];
 if(!visited[v]) { // 对于u的距离未确定的邻接顶点v，更新v的距离
 if(weight < dists[v]) { // 更新条件
 dists[v] = weight; // 更新dv
 pq.add(new int[]{v, weight}); // v入堆
 }
 }
 }
 }
 for(int dist : dists){ // 计算 MST 边权和
 if(dist == INF) return -1; // 若有不连通的城市，返回 -1
 sum += dist;
 }
 return sum;
 }
}
```

### Kruskal

前述 Prim 算法从一个顶点出发，逐渐「长出」一棵 MST，而本节的 Kruskal 算法在「生成」MST 的过程上与 Prim 颇有相对之感，该方法令 MST 的各部分各自生长，最终合并成一棵完整的 MST。Kruskal 算法是并查集的典型应用，需要读者先了解并查集。在之前的「初探图搜索 (遍历)」 - 「无向图连通性」 - 「并查集」中我已提过，我在另一篇文章中对并查集做过较为全面的介绍，如果读者还不熟悉并查集，那么在开始本节之前，可以先阅读我写的 [并查集从入门到出门](https://leetcode.cn/circle/discuss/qmjuMW/) （全文1w+ 字，尝试透彻分析并查集的基本内容，2022 年 5 月中旬在力扣讨论区发布后两周内收获 5k 阅读量，500+ 收藏，100+ 点赞及大量好评）。

后续内容在假设你已了解了「并查集」基本内容的基础上，均只做非常简要的说明 (因为详细内容都已在「并查集从入门到出门」中呈现)。

> Joseph B. Kruskal 于 1956 年发表的 [论文](https://doi.org/10.1090%2FS0002-9939-1956-0078686-7) 中描述了该算法。

#### 算法描述

[Kruskal (克鲁斯卡尔算法)](https://en.wikipedia.ahmu.cf/wiki/Kruskal%27s_algorithm): 一种基于贪心思想的求解无向图上 MST 的算法。该算法首先将所有边按边权排序，接着应用「并查集」的「查询-合并」过程来决定将哪些边加入到 MST 中。算法内容的简要描述为: 对排序后的边权，依序 (按边权从小到大) 取边 $(u,v)$ ，若顶点 $u, v$ 还未连通，则将 $(u,v)$ 加入 MST ，直到加入的边数等于 $|V| - 1$   。

#### 算法过程

1. 构建双向带权图。
2. 按边权从小到大排序所有边。
3. 实现以顶点的并查集。
4. 从排序后的边中依序 (按边权从小到大) 选取边 $(u, v)$ ，查询该边的两个顶点是否已在 MST 中 (即是否已连通) ，是则跳过，否则合并，也即将此边加入 MST 中。
5. 当加入的边数等于 $|V| - 1$   时，表明所有在一个连通分量中的顶点构成了 MST，算法结束。
6. 若依序取完所有的边后，加入 MST 的边数仍达不到 $|V| - 1$，说明此图不存在 MST，也即图中存在不连通的顶点。

#### 时空复杂度

时间复杂度:  边权排序 $O(|E|log|E|)$ ，单次查询或合并均为 $O(\alpha(n))$，近似 $O(1)$  ，至多 $|V| - 1$ 次查询与合并。综合为 $O(|V|+|E|log|E|)$，化简为 $O(|E|log|V|)$ 。

空间复杂度:  建图 $O(|V|+|E|)$ (若输入已有图信息，也可以不用建图)，$parents / rank$ 空间 $O(|V|)$。综合为 $O(|V|+|E|)$ 。

#### 代码

现在，我们给出如下利用 Kruskal 算法代码来解决 [1135. 最低成本联通所有城市](https://leetcode.cn/problems/connecting-cities-with-minimum-cost/) 。并查集采用「带路径压缩的查找 + 按秩合并」的组合。熟悉「并查集」之后我们能够非常轻松地写出该代码。

```java
class Solution {
 public int minimumCost(int n, int[][] connections) {
 Arrays.sort(connections, (a, b) -> a[2] - b[2]); // 先对边权排序
 int sum = 0, count = 0;
 int[] parents = new int[n];
 for(int i = 0; i < n; i++) parents[i] = i;
 UnionFind uf = new UnionFind(parents);
 for(int[] edge : connections){
 int u = edge[0] - 1, v = edge[1] - 1, weight = edge[2];
 if(uf.find(u) != uf.find(v)){
 uf.union(u, v); // 合并
 sum += weight; // 实时地累计 MST 边权和
 count++;
 if(count == n - 1) return sum; // 若存在 MST，必能由此句返回
 }
 }
 return -1; // 否则无MST
 }
}
class UnionFind{
 int[] parents, rank;
 public UnionFind(int[] parents){
 this.parents = parents;
 this.rank = new int[parents.length];
 Arrays.fill(rank, 1);
 }
 public int find(int x){ // 带路径压缩的查找
 if(parents[x] == x) return x;
 return parents[x] = find(parents[x]);
 }
 public void union(int x, int y){ // 按秩求并
 int xRoot = find(x), yRoot = find(y);
 if(xRoot != yRoot){
 if(rank[yRoot] <= rank[xRoot]){
 parents[yRoot] = xRoot;
 }
 else parents[xRoot] = yRoot;
 if(rank[xRoot] == rank[yRoot]) rank[xRoot]++;
 }
 }
}
```

### 小结

本节介绍了两种常见的求解「最小生成树」的算法，在掌握 Dijkstra 算法的基础上，Prim 只需简单对照学习即可完全掌握。对于 Kruskal，仅仅是并查集的典型应用，因此在掌握了并查集的基础上，学习 Kruskal 也是十分轻松的。

「最短路径」算法中，由于最短路是边权的累计，在无法穷尽松弛的算法中，例如 Dijkstra，我们特别强调了其无法处理负边图的特点，且所有的最短路径算法都不能求解负圈图 (有的可以检测出负圈) 。但「最小生成树」比较边权的大小而无「累计」效应，因此 **负边和负圈都不影响算法的正确性** ，也就是在讨论「最小生成树」时，我们 **无需考虑图是否有圈以及是否有负边** 。

## 网络流

图论中，除了关心顶点到顶点的「最短距离」和整张图的「最小生成树」之外，人们还关心 **顶点间的「流量」**。将图想象成一张信息网络，信息在顶点之间流动，每条边的权值限制了同一时间承载流量的上限，我们想知道，从一个顶点到另一个顶点，一次最多能够发送多少流量，这就是同样著名的「最大流」问题。在本节中我们将从著名的 **「最大流最小割定理」** 的证明开始，深入讨论该问题，并给出几种求最大流的算法。

### 最大流最小割定理

[最大流最小割定理(Max-flow min-cut theorem)](https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem)：对于一张网络图 $G$，从源点 $s$ 到汇点 $t$ 的 **最大流量等于最小割所有割边容量之和**。

以下将从 **路径存在问题** 引入 **割和割的大小** 的概念，再由割的大小与 $s-t$ 不相交路径数量的关系，证明该定理。证明过程中先假设有向图 (网络) 边无权 (或者说均为单位边权，即边权为1)，随后再推广至有权图。

> 定理证明过程整理自B站南大老师蒋炎岩的授课视频: [[算法竞赛入门] 网络流基础: 理解最大流/最小割定理](https://www.bilibili.com/video/BV1Q7411R7ie?spm_id_from=333.999.0.0) ，同时也增加了作者的理解。

在这里我们提前指出 **Ford-Fulkerson 方法的正确性证明与最大流最小割定理的证明等价** ，这意味着它们会被 **同时证明** 。如下，也就是 $k = m$ 与 $k = l$ 同时成立，后续我们将理解这一点。

- Ford-Fulkerson方法的正确性证明：图 $G$ 中 $s-t$ 的最大流为 $k$ ，FF 方法找到的流量为 $m$ ，证明 $k=m$。
- 最大流最小割定理证明：图 $G$ 中 $s-t$ 的最大流为 $k$ ，$s-t$ 最小割大小为 $l$ ，证明 $k=l$。

> [L. R. Ford Jr.](https://en.wikipedia.org/wiki/L._R._Ford_Jr.) & [D. R. Fulkerson](https://en.wikipedia.org/wiki/D._R._Fulkerson) (1962) *Flows in Networks*, 这一 [论文](https://www.rand.org/content/dam/rand/pubs/reports/2007/R375.pdf) 第23页，作者给出的最大流最小割定理描述如下。
>
> Theorem 5.1 Max flow min cut theorem.
>
> For any network the maximal flow value from $s$ to $t$ is equal to the minimal cut capacity  over cuts separating $s$ and $t$.

#### 从路径存在问题到割

$s-t$ 流 (flow) 存在的前提是 $s-t$ **路径** 存在。对于路径存在问题，通常以 $DFS/BFS$ 算法判定，算法从 $s$ 出发找到 $t$ 则说明 $s-t$ 路径存在，否则不存在。为了引入割的概念，现在尝试以更本质的方式考察该问题。首先以排列组合的方式简单罗列所有可能的 $s-t$ 路径。例如一张包含顶点 $s, a, b ,c, d, t$ 的图，可以罗列出如下路径，暂不考虑边是否存在。

```
s > t
s > a > t
s > b > t
...
s > a > b > t
s > a > c > t
...
```

对于上述列表中的一条路径，若该路径中的每对相邻顶点构成的边均存在，则该路径为一条 $s-t$ 路径。若对于列表中的所有路径都能找到不存在的边，则证明该图不存在 $s-t$ 的路径。

对于路径存在问题，罗列所有可能路径并逐一判断的方法虽最严格，但显然不是证明的好办法。再次考虑 $DFS/BFS$，算法从 $s$ 出发，会找到所有能到达的顶点，将这些顶点作为集合 $S$，剩下 $s$ 无法到达的顶点作为集合 $T$ 。$s-t$ 路径不存在， **等价于 $S$ 中任意顶点到 $T$ 中任意顶点的连边都不存在** ，由此引入如下 **割** 的概念。

**割的定义**：割 (cut) 是图 $G$ 的 **顶点集 $V$ 的划分** 。有向图 $G(V, E)$ 的 $s-t$ 割 $C = (S, T)$ 指 $V$ 被划分为顶点集 $S$ 和 $T$ ，且 $s ∈ S$，$t ∈ T$。

**割的大小**：对于上述割，其大小指从 $S$ 到 $T$ 的边的数量，即边 $(u, v) ∈ E | u ∈ S, v ∈ T$ 的数量，称这些边为 **割边**。

根据割及其大小的定义，只要存在 $s-t$ 路径，无论如何划分 $V$ 得到 $s-t$ 割，总能在图中找到从 $S$ 到 $T$ 的边，即该割的大小一定大于0。例如下面的 $s-t$ 路径，$s, a, d, e, h ∈ S， b, c, f, g, i, t ∈ T$，红箭头表示 $s-t$ 割的边。只要满足 $s ∈ S$  ($s$ 在绿色阴影里)，$t ∈ T$ ($t$ 不在绿色阴影里)，在有路径的情况下，红箭头一定存在，而与绿色阴影的形状 (具体的 $s-t$ 割) 无关。反过来说就是 **若 $s-t$ 路径存在，则所有 $s-t$ 割的大小都大于0** 。

因此，要想证明 $s-t$ 路径不存在，**只需要找到一个大小为 0 的 $s-t$ 割即可** 。 注意，当 $s-t$ 路径不存在时，也可能存在大小不为 0 的 $s-t$ 割，很容易找到相关例子，因此重申，证明 $s-t$ 路径不存在是要找到一个大小为 0 的 $s-t$ 割。

![image.png](https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/posts_img/algorithms/graph/max-flow-proof1.png)

#### 不相交路径数量与割的大小

现在，我们初步建立了「流」与「割」在特定情形下的联系，即上述分析给出的「$s-t$ 路径数量为 0 时 (流为0)，必存在大小为 0 的 $s-t$ 割」。这是 「$s-t$ 路径数量」 与 「$s-t$ 割大小」 的特定关系。再次回到定理内容，定理描述了「最大流」和「最小割边容量」(对无权图来说即割边数量) 的关系，不难理解，最大流就是 **不相交的 $s-t$ 的路径** 数量 (再次注意，我们当前讨论的是无权图，「数量」即「流量」)。$s-t$ 的 **不相交** 路径指对于多条 $s-t$ 路径，它们之间 **没有公共边** 。后续我们通过如下三个量的关系来证明定理，即证明 $k = l$。

-   $k$ 为图中 **实际存在的** $s-t$ 不相交路径数量。

-   $m$ 为 **算法找到的**  $s-t$ 不相交路径数量。

-   $l$ 为图中 **最小**  $s-t$ 割边数量。

##### 不相交路径数上界

假设图有 $k$ 条 $s-t$ 的不相交路径，想要知道 $k$ 的大小，可以逐步假设 $k (k = 0, k = 1, k = 2,...)$，再验证是否确实有那么多条。例如假设 $k=0$ 时，实际上就是前述 $s-t$ 路径存在性问题，已经指出，若存在大小为 0 的 $s-t$ 割，则 $k=0$。当 $k > 0$ 时，考虑是否还能用 $s-t$ 割的大小表达不相交路径数量。

下图 $k=1$，以图中的阴影表示 $s-t$ 割，可以看出该割的大小为 1。容易看出 **不相交路径数量受到割边 $(b, c)$ 数量的限制** ，如果所有 $s-t$ 割大小最小为1，那么任意 $s-t$ 路径一定都经过该唯一割边，即 $s-t$  **不相交** 路径至多为 1。若最小割大小为 2，则存在 2 条经过 2 条不同割边的 $s-t$ 路径。总之，**$s-t$ 割的大小 $c$ 决定了 $s-t$ 不相交路径数量 $k$ 的上界**，即 $k ≤ c$。如果 $c = l$ ，自然就有 $k≤l$ ，任意 $s-t$ 割的大小 $c$ 是 $k$ 的一个 **上界** ，$l$ 是 $k$ 的 **最紧上界** 。现在我们离目标近了一步，即「割边数」$c$ 和「最大流」($s-t$ 不相交路径数量) $k$ 的关系满足: $k ≤ c$ ，最紧地有 $k≤l$ 。

![image.png](https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/posts_img/algorithms/graph/max-flow-proof2.png)

##### 不相交路径数下界

上述以割边数给出了不相交路径数量 $k$ 的上界，而如果能直接找到 $m$ 条不相交路径，此 $m$ 可立即作为 $k$ 的一个下界，且若 $m = l$，便可得到 $k = l$。 直接地，我们用 $DFS/BFS$ 求 $m$，在 $G$ 中寻找一条 $s-t$ 路径 $p$，找不到时 $k=0$，若能找到，为了保证找到的路径总是 **不相交** 的，需要从 $G$ 中删去 $p$，然后 $k = k + 1$。看起来有效，但实际操作后我们会发现一个问题，如下图，当第一次选择的路径为 $s > d > a > t$ 后，由于该路径被删除，将无法再找到下一条路径，而该图显然有 $k=2$ ($s > a > t, s > d > t$)，因此单纯使用 $DFS/BFS$ 算法得到的 $m$ 并不一定是 $k$ 。而 Ford-Fulkerson 方法可以解决这一问题，即 FF 方法保证 $m = k$ 。

![image.png](https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/posts_img/algorithms/graph/max-flow-proof3.png)

##### 反向边 (路径)

L. R. Ford, JR & D. R. Fulkerson 在1956年的[论文](http://www.cs.yale.edu/homes/lans/readings/routing/ford-max_flow-1956.pdf)中修正了单纯以 $DFS/BFS$ 找最大流的缺陷缺陷，并证明了改进后算法的正确性，这就是著名的 Ford-Fulkerson 方法。修正办法十分简单，即在每一次找到一条路径并删除该路径后，在 $t-s$ 的方向上 ($s-t$ 的反方向)  **添加原路径的反向路径**，仅此而已。如前图，找到 $s > d > a > t$ 的路径后将其删除，立即添加 $t > a > d > s$ 路径。该操作使得后续仍能找到一条 $s-t$ 路径，即 $s > a > d > t$，继续删除并添加相应的反向路径，最终无法再找到 $s-t$ 路径，$m=2$ 被正确求出。

![image.png](https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/posts_img/algorithms/graph/max-flow-proof4.png)

$s-t$ 路径称为 **增广路径(Augmenting Path)**，可以将反向路径称作 **反向增广路径**。添加这一反向路径的操作是整个算法最为核心的部分，以下证明这一操作的正确性，即以「寻找增广路-删除该路径-添加反向路径」这一FF方法得到 $m$ 条 $s-t$ 路径，且 $m = k$。稍等，我们不是要证明「最大流最小割定理」，也就是证明 $k = l$ 吗？为何突然转为证明 $m=k$ ？很快你会看到，这两点是等价的，且是同时证明的。

#### 证明k=m

蒋岩炎老师的视频中不以严谨的数学证明，而是以图形化的直观方式证明了最大流最小割定理 (也即证明了 FF 方法的正确性)。

##### 添加反向边的有效性

如下左图 (图中的 $s$ 和 $t$ 虽画出了多个点，但表示一个点)，$p1, p2, p3$ 是 $DFS/BFS$ 找到的头 3 条 $s-t$ 不相交路径 (每次都会添加反向路径，但这三条恰好都还未经过反向边)，$p4$ 是第 4 条 (经过反向边)。$p4$ 由两种边组成，如下中图，一种是不与 $p1, p2, p3$ 交叠的边，即此前尚未出现在不相交路径上的 **原边**，另一种是与 $p2$ 和 $p3$ (反向) 交叠的边，这些边是找到 $p2$，$p3$ 后添加的 **反向边**，它们使得 $p4$ 可以沿着这样的反向边到达 $t$。假设此时 FF 方法已找不到 $s-t$ 路径，那么 FF 方法找到了 4 条不相交路径，即 $m = 4$ 。

$p4$ 是通过添加反向边来间接得到的 (此路径并不存在于原图中)，现在的问题，由于 4 条路径是通过添加反向边找到的，它们并不都是原图中存在的路径。我们首先明确 **原图** 中确实有 4 条不相交路径。为了看出这一点，找到 $p4$ 后，在反向 $p4$ 之前，去掉 $p4$ 走过的反向边，然后将还原 $p1, p2, p3$ 反向过后的边 (再反回去) ，得到下右图。可以看到，$p1$不变，而 $p'2, p'3, p'4$ 就是 **原图** 中的 $s-t$  路径，它们显然不相交 。注意下右图本身就是原图的一部分，只不过一开始没找到 $p'2, p'3, p'4$ ，而是找到了 $p2, p3$，然后通过反向边找到了 $p4$。

尽管算法找到的路径与下右图显示的原图上的路径不同，**但数量是正确的**。如果还有 $p5$，仍然可以通过相同的方法证明原图中有 5 条不相交路径。**在示意图中那些通过反向边得到的 (在原图中不存在的) 路径看起来就像是切开了起初得到的路径 ($p2, p3$)，并通过部分原边连接这些路径的断点，使得 $s$ 到 $t$ 可达** 。

![image.png](https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/posts_img/algorithms/graph/max-flow-proof5.png)

##### k的确定与最小割的大小

上述内容说明了添加反向边能够找到新的 (在不添加反向边时可能找不到的) 不相交路径，并且我们看到算法找到的路径与原图实际的路径 **一一对应 (数量相等)** 。有了这些准备工作，我们开始证明 $k = m$ 。证明基于以下思路。

1. 已经知道 $m = 4$，因此 $k ≥ m = 4$ 。
2. 如果找到原图 $G$ 的 $s-t$ 割 $C$，证明它是「最小割」且 $l = 4$ ，那么证明就完成了。
3. 对于 2，指出一个割，直接证明它是 **「最小的」** 是困难的，因此我们不必考虑它是不是最小，转而考虑在原图中寻找一个大小 $c=4$ 的割 $C$ 。因为 $m≤k≤c$ ，那么 $m=k=c=4$，确定了 $k=4$ ，就不可能存在大小小于 4 的割，于是 $m=k=l=c=4$ 。
4. 上述 3 就意味着 FF 方法 ($m=k$) 和最大流最小割定理 ($k=l$) 同时得证。

根据这个思路，我们接着前图继续分析。再次强调，现在的目标是 **在原图中寻找一个大小为 $c=4$ 的割 $C$** 。

以上中图为例，将 $p4$ 反向得到如下残留图 $G_{f'}$ 。

![image.png](https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/posts_img/algorithms/graph/max-flow-proof6.png)

**残留图 $G_{f'}$ 有两种边** ，一种是 $s-t$ 不相交路径的反向边（注意，这里说的 $s-t$ 不相交路径不是通过算法找到的路径，而是前述说明中 $p1, p'2, p'3, p'4$ 那样的原图中存在的 $s-t$ 路径），一种是其他不在不相交路径上的原边。显然，此时 $t-s$ 不相交路径就是原图上的 4 条 $s-t$ 不相交路径的反向路径。由于 $s-t$ 已不连通，可知此时在残留图中存在大小为 0 的 $s-t$ 割 $C$ 。我们指出如下具体的割 $C$ 。

> 割 $C$ : 将 $G_{f'}$ 中 $s$ 能够到达的顶点划归 $S$，将剩下的顶点划归 $T$ 。

**该割大小为 0** ，反证法简单可证明。若有割边，也就是还能从 $S$ 找到一个顶点 $v$ 连到 $T$ 中的某个顶点 $u$，那么 $s$ 就能通过 $v$ 连通 $u$ ，这与我们的划分要求相矛盾 ，因为在 $G_{f'}$ 中已经将 $s$ 能到达的所有顶点都划入 $S$ 了。$u$ 也不可能是 $t$，因为  $G_{f'}$ 中 $s-t$ 不连通，因此假设不成立，此割无割边。  由此得到如下重要推论。

> 推论: 割 $C$ 在原图 $G$ 中大小为 4。

证明如下:

1. 割 $C$ 在残留图 $G_{f'}$ 中大小为 0 ，也就是 $S$ 中无顶点可到 $T$ 。 
2. 残留图与原图的区别仅仅是 **不相交路径的方向相反** 。
3. 在原图 $G$ 中，$S$ 中的顶点可分为不在 $s-t$ 路径上和在 $s-t$ 路径上的顶点。对于前者，根据 1，无顶点可到 $T$ ，对于后者，它们 **贡献且仅贡献了 4 条割边** 。
   1. 也就是说每条 $s-t$ 路径只贡献一条割边，这要求每条 $s-t$ 路径都只穿过一次 $S-T$。
   2. 因为原图 $G$ 的 $s-t$ 路径是残留图 $G_{f'}$ 的 $t-s$ 路径的反向路径。因此证明原图中 $s-t$ 路径只穿过一次 $S-T$ 等价于证明残留图中 $t-s$ 路径只穿过一次 $T-S$。(记住，割 $C$ 在原图和残留图中是一样的)
   3. 假设在残留图 $G_{f'}$ 中 $t-s$ 路径穿过了两次 $T-S$，因为 **路径是连续的** ，穿越过程必然是 $T→S→T→S$，也就是会有边穿越 $S-T$ 。**这与残留图 $G_{f'}$ 存在大小为 0 的 $s-t$ 割相矛盾** ( $G_{f'}$ 上的割 $C$)。 
   4. 因此原图 $G$ 中的 $s-t$ 路径均只穿过一次 $S-T$，每条路径只贡献一条割边，也即割 $C$ 在原图 $G$ 中大小为 4 。

推论得证。

至此，通过找到残留图 $G_{f'}$ 上大小为 0 的割 $C$ ，我们证明了割 $C$ 在原图中大小为 4 ，实现了证明目标。最后总结如下。

1. 我们在指出原图 $G_f$ 上的割 $C$ 时，并不知道它是不是最小割，但证明了 $m = c = 4$，而我们知道 $m≤k≤c$  ，因此直接得到了 $k = m = 4$ 。因为 $k=4$ ，所以原图上的任何 $s-t$ 割不可能比割 $C$ 更小，于是 **割 $C$ 是一个最小割** ，综上，有 $m=k=l=c=4$ 。
2.  $m=k$ 证明了 Ford-Fulkerson 方法的正确性， $k = l$ 证明了最大流最小割定理，这就是我们在开始证明时提到「FF 方法正确性和最大流最小割定理的证明等价，它们会被同时证明」的原因。

#### 推广至有权图

只需将边权为 $n$ 的边看作 $n$ 条单位边，转换成无权图即可适用前述证明。例如 $s > a > t$ 路径，$(s, a)$ 边权为 2，$(a, t)$ 边权为3，将边拆成单位边后，原容量为 2 的一条路径被分成两条单位容量的路径。

### Ford-Fulkerson

在「最大流最小割定理及其证明」中我们已经介绍了 Ford-Fulkerson 方法并证明了该方法的正确性。本节我们继续讲解该方法更详细的内容。

#### 算法描述

[Ford-Fulkerson方法(福特-富尔克森方法)](https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm): 1956 年 L. R. Ford Jr 和 D. R. Fulkerson 在其发表的 [论文](http://www.cs.yale.edu/homes/lans/readings/routing/ford-max_flow-1956.pdf) 中描述的基于 **贪心思想** 的求 **有向图最大流** 的算法。因为该算法未指定求增广路径的具体算法，所以通常将其称作 Ford-Fulkerson **方法** (Method) 而非 Ford-Fulkerson **算法** (Algorithm) 。若增广路径 **以 $bfs$ 方式求出** ，则为 **Edmonds-Karp 算法** 。此外也可以以 $dfs$ 方式求最短路径，我们之后会介绍 **结合 $bfs$ 和 $dfs$ 求增广路的 Dinic 算法** 。FF 首先设置要求解的目标，即源点 $s$ 到目标点 $t$ 的最大流，设为 $f$，初始值为 0，然后寻找 $s-t$ 路径 $p1$，$p1$ 上最小权边的边权即 $s$ 能沿 $p1$ 发往 $t$ 的最大流量 $c(p1)$。如我们在「最大流最小割定理及其证明」中所述，由于不适当的增广路选择会使得最大流量 $f$ 在求出前 $s$ 到 $t$ 就没有了增广路，因此 Ford-Fulkerson 方法要求每次求出一条增广路后，要在相反方向路径上添加 $c(p1)$，其作用是 $t$ 到 $s$ 在必要时能够发回原先 $s$ 发送到 $t$ 的流量。我们已经证明了该做法的正确性。当无法再在残留图中找到 $s-t$ 的增广路时所得到的 $f$ 即为原图 $s-t$ 最大流。

#### 算法过程

给定一张图 $G(V, E)$ ，源点为 $s$ ，汇点为 $t$ 。求 $G$ 中从 $s$ 到 $t$ 的最大流 $f$ 。

1. 设置一张残留网络 (残留图/残差图/残余图，*residual graph* ) $Gf$，$Gf$ 初始为 $G$。

2. 考察 $Gf$ 中是否有从 $s$ 到 $t$ 的路径 $p$ ，使得 $p$ 上的每一条边 $(u,v) ∈ p$ ，都有 $c(u, v) > 0$ 。$p$ 称作 **增广路径 (Augmenting Path)** 。若存在 $p$ ，则：
   2.1 将 $p$ 中 **最小边的权**  $c$ 加入 $f$。
   2.2  $p$ 的每条边减去该最小边的权 $c$。
   2.3  $p$ 的反向路径上的每条边加上该最小边权 $c$。

3. 在 $Gf$ 中反复寻找增广路径 $p$ 并执行 2 中的操作直到 $Gf$ 中找不到 $p$，算法停止。此时得到的 $f$ 即为 $s$ 到 $t$ 的最大流。

※ 虽然根据 wiki 的说法 Ford-Fulkerson 未指定求增广路的具体方式，但若以 $dfs$ 方式求增广路，通常也称作 Ford-Fulkerson 。

#### 算法正确性证明

请参考「最大流最小割定理」。

#### 两种坏情形

**小边权增广路径情形**

如下图，寻找从 $A$ 到 $B$ 的增广路径时，若选取 $A>B>C>D$ 后，再选取 $A>C>B>D$ ( $C>B$ 由反向边操作得到)，如此反复选取。由于 $B,C$ 之间的小权边限制了流的大小，需经历 2000 次增广才能结束算法，而选取 $A>B>D$，然后选取 $A>C>D$ 则只需要两次。针对如何避免选取含有小边权的增广路，有以下两种做法。

- 做法1:  **总是选取流最大的增广路径** 。显然能够避免小权边引起的多次增广路选取。

- 做法2:  **总是选取最短的增广路径** 。较短的增广路降低了路径上出现小权边的概率。

![image.png](https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/posts_img/algorithms/graph/ff-bad-situation.png)

以 $bfs$ 方式应用无权单源最短路径方法实现做法 2 即为 Edmonds-Karp 算法。

**算法无法终止的情形**

算法能够结束的隐含前提是 **每次找到的增广路至少使 $s$ 到 $t$ 的发送流增加 1 个单位 (例如整数 1)** ，只要最大流是固定的，经过有限次操作后总能发送到最大流。如果边权存在 **无理数** ，则算法可能无法结束。以下举例说明 (该例来自 [Wiki](https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm) )。

如下图的流量网络，$e1 = (b, a), e2 = (d, c), e3 = (b, c)$ ， $|e1| = |e3| = 1$，$|e2| = r = (√5 - 1) / 2$ 。其他边的容量为 $M (M >= 2)$ ，且 $r^2 = 1 - r$ ， $r^3 = r - r^2$ ,  $r^4 = r^2 - r^3$ ...。有路径 $p0 = s > b > c > t$ ，$p1 = s > d > c > b > a > t$ ， $p2 = s > b > c > d > t$ ，$p3 = s > a > b > c > t$ 。若按路径 $p0, p1, p2, p1, p3, p1, p2, p1, p3, p1, p2, p1, p3...$ 的顺序增广，则算法无法结束。

观察下表经过上述顺序一次循环后的结果，步骤 1 和步骤 5 时 $e1, e2, e3$ 剩余容量为 $r^n, r^{n+1}, 0$ 的形式。发送流为 $1+2(r^1+r^2)$ 。经过无限次完整的循环，$e1, e2, e3$ 剩余容量都会是 $r^n, r^{n+1}, 0$ 的形式，而发送流为 $1+2∑r^i$   ( $r$ 是从 1 到正无穷的整数)。根据等比数列求和公式有：

$$1+2∑r^i   = 1 + 2*r/(1-r)$$

将 $r = 1 - r^2 = (1+r)*(1-r)$ 代入上式分子中的 $r$ ，得到 $3+2r$ ，即发送流会向 $2+√5$ 趋近，但从原图可以看出最大流为 $2M + 1 > 5 > 2+√5$ 。

| 步骤 | 增广路 | 发送流 | e1剩余    | e2剩余 | e3剩余 |
| ---- | ------ | ------ | --------- | ------ | ------ |
| 0    |        |        | $r^0 = 1$ | $r^1$  | 1      |
| 1    | $p0$   | 1      | $r^0$     | $r^1$  | 0      |
| 2    | $p1$   | $r$    | $r^2$     | 0      | $r^1$  |
| 3    | $p2$   | $r$    | $r^2$     | $r^1$  | 0      |
| 4    | $p1$   | $r^2$  | 0         | $r^3$  | $r^2$  |
| 5    | $p3$   | $r^2$  | $r^2$     | $r^3$  | 0      |

![image.png](https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/posts_img/algorithms/graph/ff-bad-situation2.png)

#### 时空复杂度

时间复杂度：$O(|E|*f)$ 。

设最大流为 $f$ ，算法过程为穷尽增广路径的过程，对于任意一条增广路，都可以保证在 $O(|E|)$ 时间内找到 (例如以 $bfs/dfs$ 方式寻找，为 $O(|V|+|E|)$，简略为 $O(|E|)$  )，而每找到一条增广路径，至少增加 1  个单位的流量 (不考虑边权为无理数的情况，前面已说过，该情况可能会导致算法无法终止)，故总的时间复杂度为 $O(|E|*f)$ 。此时间复杂度与最大流的大小正相关，当 $f$ 较大时会导致较高的时间复杂度。若以 $bfs$ 算法寻找增广路，即 Edmonds-Karp 算法，时间复杂度为 $O(|V||E|^2)$ 。若以 $bfs$ 和 $dfs$ 相结合的 Dinic  算法寻找增广路，则时间复杂度进一步降为 $O(|V|^2|E|)$ 。

空间复杂度：依赖于存图及求最短路径的具体方法，采用邻接表存图，则存图空间为 $O(|V|+|E|)$ ，采用邻接矩阵为 $O(|V|^2)$ 。若以 $bfs$ 求最短路径，即 Edmonds-Karp 算法，队列的长度导致的空间复杂度为 $O(|V|)$ 。若以 $dfs$ 求最短路径，递归栈导致的空间复杂度为 $O(|V|)$ 。总体来说取决于存图方式。

#### 代码

我们采用 $dfs$ 方式找增广路，并将其看作 Ford-Fulkerson 「算法」。现给出 FF 「算法」解决 P3376 【模板】网络最大流 (请自行搜索) 一题的代码（#9, #10 测试例超时，其他通过）。

```java
// Ford-Fulkerson
package com.yukiyama.demo;

import java.util.*;
import java.io.*;

public class FF {
 boolean[] visited;
 int[] ends, heads, nexts, weights, preEdges, pre, saturatedWeights;
 int edgeNum;
 public static void main(String[] args) {
 Scanner cin = new Scanner(System.in);
 int n = cin.nextInt(), m = cin.nextInt(), s = cin.nextInt() - 1, t = cin.nextInt() - 1;
 FF demo = new FF();
 demo.visited = new boolean[n];
 demo.ends = new int[2 * m + 2];
 demo.nexts = new int[2 * m + 2];
 demo.weights = new int[2 * m + 2];
 demo.preEdges = new int[n];
 demo.heads = new int[n];
 demo.pre = new int[n];
 demo.saturatedWeights = new int[n];
 demo.edgeNum = 1; // 初始为1，使得第一条边的编号为2，二进制为 10，第二条边(第一条边的反向边)编号为3，二进制为11，方便取异或
 demo.init(m, cin); // 建图
 cin.close();
 System.out.println(demo.ek(s, t)); // 求最大流
 }
 // 求 s-t 最大流
 public long ek(int s, int t) {
 if (s == t) return 0; // 特判
 long max = 0, incFlow = 0;
 while((incFlow = dfs(s, t, Integer.MAX_VALUE)) > 0) { // 不断增广
 max += incFlow; // 将每次增广路带来的流量增加到maxFlow上
 Arrays.fill(visited, false); // 重置 visited
 }
 return max;
 }
 // 链式向前星建图
 private void init(int m, Scanner cin) {
 for(int i = 0; i < m; i++) {
 int u = cin.nextInt() - 1, v = cin.nextInt() - 1, weight = cin.nextInt();
 ++edgeNum;
 ends[edgeNum] = v;
 weights[edgeNum] = weight;
 nexts[edgeNum] = heads[u]; 
 heads[u] = edgeNum;
 ++edgeNum;
 ends[edgeNum] = u;
 weights[edgeNum] = 0;
 nexts[edgeNum] = heads[v]; 
 heads[v] = edgeNum;
 }
 }
 // dfs 增广并实时地发送 & 发回流
 private long dfs(int u, int t, long incFlow){
 if(u == t) return incFlow;
 visited[u] = true; // 立即置为已访问
 for(int edgeNo = heads[u]; edgeNo != 0; edgeNo = nexts[edgeNo]) {
 int v = ends[edgeNo], weight = weights[edgeNo];
 if(visited[v] || weight == 0) continue; // 跳过已访问或边权为0的情况
 long saturatedWeight = 0;
 if((saturatedWeight = dfs(v, t, Math.min(incFlow, weight))) > 0) {
 weights[edgeNo] -= saturatedWeight; // 增广路发送流
 weights[edgeNo ^ 1] += saturatedWeight; // 反向增广路发回流
 return saturatedWeight;
 }
 }
 return 0;
 }

}
```

### Edmonds-Karp

#### 算法描述

[Edmonds-Karp算法 (埃德蒙兹-卡普算法)](https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm): 以 $bfs$ 方式 (无权最短路) 寻找增广路径实现 Ford-Fulkerson 方法即为 Edmonds-Karp 算法。每找到一条增广路并确定该路径上的最小边权 (该路径最大可发送流) 后，将此边权计入最大流中，并在此路径上对 $s-t$ 方向的边减去该权值， $t-s$ 方向上加上该权值。当 BFS 无法再找到增广路时算法结束，得到 $s$ 到 $t$ 的最大流。

#### 算法过程

给定一张图 $G(V, E)$ ，源点为 $s$ ，汇点为 $t$ 。求 $G$ 中从 $s$ 到 $t$ 的最大流 $f$ 。

1. 设置一张残留网络 (残留图/残差图/残余图，*residual graph* ) $Gf$，$Gf$ 初始为 $G$。

2. **以 $bfs$ 方式** 考察 $Gf$ 中是否有从 $s$ 到 $t$ 的路径 $p$ ，使得 $p$ 上的每一条边 $(u,v) ∈ p$ ，都有 $c(u, v) > 0$ 。$p$ 称作 **增广路径 (Augmenting Path)** 。若存在 $p$ ，则：
   2.1 将 $p$ 中 **最小边的权**  $c$ 加入 $f$。
   2.2  $p$ 的每条边减去该最小边的权 $c$。
   2.3  $p$ 的反向路径上的每条边加上该最小边权 $c$。

3. 在 $Gf$ 中反复寻找增广路径 $p$ 并执行 2 中的操作直到 $Gf$ 中找不到 $p$，算法停止。此时得到的 $f$ 即为 $s$ 到 $t$ 的最大流。

#### 时空复杂度

以下证明 EK 算法的时间复杂度为：$O(|V||E|^2)$

> 本证明参考了[证明1](http://pisces.ck.tp.edu.tw/~peng/index.php?action=showfile&file=f6cdf7ef750d7dc79c7d599b942acbaaee86a2e3e)、[证明2](https://brilliant.org/wiki/edmonds-karp-algorithm/)。

##### 1. 一次BFS增广

每次 $bfs$ 增广，在增广路上的未饱和边会多出一条反向边，原图的单向边添加反向边后，就具有双向边 (两条) ，但饱和边仍是一条 (反向) ，因此增广操作导致的边数增长不会使总边数超过原来的 2 倍，即算法的任意时刻总边数 $< 2|E|$。因此一次 $bfs$ 的时间复杂为 $O(2|E|)$，即 $O(|E|)$。

##### 2. BFS增广次数

###### 2.1 增广路长度非递减

即证明算法过程中的 $s$ 到 $t$ 的 BFS 增广操作，即正向边删除和反向边增加的操作，不会导致源点 $s$ 到任意一点 $v$ 的最短路径距离减少。残留图 $G_f$ 经过一次 BFS 增广变为 $G_{f'}$ 后，对任意顶点 $v$ ，源点 $s$ 到 $v$ 的最短路径长度 **非递减**，即有 $d'(s, v) ≥ d(s, v)$。以下利用反证法证明，并在证明中解释为何**只能证明非递减而无法证明严格递增**，即不是 $d'(s, v) > d(s, v)$。

1. 假设某一次 $s - t$ 增广后，使得某些顶点到源点 $s$ 的最短路径距离相比增广前变小了，且这其中距离源点 $s$ 最近者为 $v$。则根据该假设有

(1) $d'(s, v) < d(s, v)$

2. 令 $u$ 为 $G_{f'}$ 中 $v$ 的靠近源点 $s$ 的前一个顶点，则有

(2)    $d'(s, u) + 1= d'(s, v)$

如 2.1.1 所述，$v$ 是我们有意选择的在 $G_{f'}$ 中最短距离相比在 $G_f$ 中变小的且距离 $s$ 最近的顶点，$u$ 比 $v$ 更靠近 $s$，但在 $G_{f'}$ 中相比在 $G_f$ 中距离 $s$ 的最短路径未变小，即有

(3)    $d(s, u) ≤ d'(s, u)$

3. 假设 $(u, v) ∈ E_f$，已知 $s$ 到 $v$ 的最短路径距离为 $d(s, v)$，则有

(4)    $d(s, u) + 1 = d(s, v)$

结合(1)、(2)、(3)有

$d(s, u) ≤ d'(s, u) → d(s, u) + 1 ≤ d'(s, u)+ 1 = d'(s, v) < d(s, v)$，即

(5) $d(s, u) + 1 < d(s, v)$

(4) 是由 2.1.3 的假设得到的，与由 (1), (2), (3) 得到的 (5) 矛盾，故在 2.1.1 假设成立的前提下，2.1.3 的假设 $(u, v) ∈ E_f$ 不成立，即 $(u, v) ∉ E_f$。同时我们还能看到，如果一开始证明的是 $d'(s, v) > d(s, v)$，那么就要反证 $d'(s, v) ≤ d(s, v)$ (对应式(1))，经过同样的过程当前的式 (5) 会变为 $d(s, u) + 1 ≤  d(s, v)$，将推导不出与 (4) 式的矛盾（因为都有一个等号）。

4. 由上述知 $(u, v) ∉ E_f$，但如 2.1.2 所述，$(u, v) ∈ E_{f’}$ ，故在 $G_f$ 上的增广必定经过了 $(v, u)$，且此边饱和，导致在 $G_{f'}$ 中产生了反向边 $(u, v)$。于是可知在 $G_f$ 中有

(6)    $d(s, u) = d(s, v) + 1$

(6) 与 (5) 矛盾，于是最初 2.1.1 的假设不成立，即不存在这样的顶点 $v$，也即增广操作使得源点到任意一点 $v$ 的长度 **非递减**， **故EK算法寻找的增广路长度非递减**。

###### 2.2 增广次数

1. 假设某次 $G_f$ 的增广中 $(u, v)$ 为饱和边，增广后 $(u, v) ∉ E_{f'}$，$(v, u) ∈ E_{f'}$。之后 $(u, v)$ 要再次出现的前提是 $(v, u)$ 在增广路上。在 $G_f$ 中  $(u, v)$ 第一次成为饱和边时有

(7)    $d(s, v) = d(s, u) + 1$

2. 若 $(u, v)$ 第二次成为饱和边，可知在此前的 $G_{f'}$ 中 $(v, u)$ 中在增广路上，在 $G_{f'}$ 的这次增广中有

(8)    $d'(s, u) = d'(s, v) + 1$

3. 由 2.1 的结论，$s$ 到任意顶点的最短路径非递减，即必有 $d'(s, v)  ≥ d(s, v)$ ，结合 (7) 和 (8)，有

$d'(s, u) = d'(s, v) + 1 ≥ d(s, v) + 1 = d(s, u)+ 2$，即

(9)    $d'(s, u)   ≥ d(s, u) + 2$

也就是说，$(u, v)$ 第二次成为饱和边时 $s$ 到 $u$ 的最短距离至少比前一次成为饱和边时大 2。而 $s$ 到任意顶点的距离最多不超过$|V| - 1$，故 $(u, v)$ 可以成为饱和边的次数最多为 $(|V| - 1) / 2$。每次增广至少有一条边成为饱和边，根据 2.1 中的说明，EK算法过程中边数 $< 2|E|$，故考虑 **所有边的总的增广次数必小于** $2|E|*(|V| - 1)/2$，即 **增广次数复杂度为 $O(|V||E|)$**。

**综上，EK 算法复杂度为 $O(|V||E|^2)$。**

证明过程中 **BFS增广使得增广路长度非递减** 的结论是关键，网上有的文章声称 BFS 寻找增广路的操作使得增广路长度递增，但我们已经在 2.1.3 的叙述中指出这是不对的。根据 2.1 的证明，只能得到 **非递减** 的结果，但这一结论在 2.2 中足以证明任意边第二次成为饱和边时其最短路径长至少增加2，由此得到BFS次数的上界。

空间复杂度：存图空间为 $O(|V|+|E|)$ ，队列空间为 $O(|V|)$ 。总体时间复杂度为 $O(|V|+|E|)$ 。

#### 代码

现给出 EK 算法解决 P3376 【模板】网络最大流 一题的代码（通过）。

```java
// edmonds-karp
package com.yukiyama.demo;

import java.util.*;
import java.io.*;

public class EK {
 boolean[] visited;
 int[] ends, heads, nexts, weights, preEdges, pre, saturatedWeights;
 int edgeNum;
 public static void main(String[] args) {
 Scanner cin = new Scanner(System.in);
 int n = cin.nextInt(), m = cin.nextInt(), s = cin.nextInt() - 1, t = cin.nextInt() - 1;
 EK demo = new EK();
 demo.visited = new boolean[n];
 demo.ends = new int[2 * m + 2];
 demo.nexts = new int[2 * m + 2];
 demo.weights = new int[2 * m + 2];
 demo.preEdges = new int[n];
 demo.heads = new int[n];
 demo.pre = new int[n];
 demo.saturatedWeights = new int[n];
 demo.edgeNum = 1; // 初始为1，使得第一条边的编号为2，二进制为 10，第二条边(第一条边的反向边)编号为3，二进制为11，方便取异或
 demo.init(m, cin); // 建图
 cin.close();
 System.out.println(demo.ek(s, t)); // 求最大流
 }
 // 求 s-t 最大流
 public long ek(int s, int t) {
 long max = 0;
 while(bfs(s, t)) { // 不断增广
 max += update(s, t); // 将每次增广路带来的流量增加到maxFlow上
 Arrays.fill(visited, false); // 重置 visited
 }
 return max;
 }
 // 链式向前星建图
 private void init(int m, Scanner cin) {
 for(int i = 0; i < m; i++) {
 int u = cin.nextInt() - 1, v = cin.nextInt() - 1, weight = cin.nextInt();
 ++edgeNum;
 ends[edgeNum] = v;
 weights[edgeNum] = weight;
 nexts[edgeNum] = heads[u]; 
 heads[u] = edgeNum;
 ++edgeNum;
 ends[edgeNum] = u;
 weights[edgeNum] = 0;
 nexts[edgeNum] = heads[v]; 
 heads[v] = edgeNum;
 }
 }
 // bfs 增广
 private boolean bfs(int s, int t){
 if (s == t) return false; // 特判
 Queue<Integer> q = new ArrayDeque<>();
 q.add(s); // 起始顶点入队
 visited[s] = true; // 立即置为已访问
 saturatedWeights[s] = Integer.MAX_VALUE; // 增广路径到达 s 为止的饱和边权置为INF
 while(!q.isEmpty()) {
 int u = q.remove();
 for(int edgeNo = heads[u]; edgeNo != 0; edgeNo = nexts[edgeNo]) {
 int v = ends[edgeNo], weight = weights[edgeNo];
 if(visited[v] || weight == 0) continue; // 跳过已访问或边权为0的情况
 saturatedWeights[v] = Math.min(saturatedWeights[u], weight); // 记录到 v 为止的饱和边权
 q.add(v); // v入队
 visited[v] = true; // 立即置为已访问
 preEdges[v] = edgeNo; // 记录边下标
 pre[v] = u; // 记录前驱
 if(v == t) return true; // 找到增广路
 }
 }
 return false;
 }
 // 发送 & 发回流
 private int update(int s, int t) {
 int cur = t;
 while(cur != s) { 
 int edge = preEdges[cur];
 weights[edge] -= saturatedWeights[t]; // 增广路发送流
 weights[edge ^ 1] += saturatedWeights[t]; // 反向增广路发回流
 cur = pre[cur];
 }
 return saturatedWeights[t];
 }

}
```

### Dinic (Dinitz)

#### 算法描述

[Dinic算法 (迪尼克算法)](https://en.wikipedia.org/wiki/Dinic%27s_algorithm)：EK 算法以 $bfs$ 方式实现 FF 方法中的增广操作，在 Dinic 算法中，采用 $bfs$ 与 $dfs$ 结合的方式增广。首先引进 **高度标号 (层次标号)** 和 **分层图** 的概念。以 $bfs$ 算法从 $s$ 到 $t$ ，标记 $s$ 为第 1 层，$s$ 的邻接顶点为第 2 层，以此类推 $t$ 为最后一层。执行一次 $bfs$，赋予每个顶点高度标号信息，此时的图称作分层图。在此分层图内以 $dfs$ 方式反复寻找增广路并执行增广操作 (找到饱和边，发送和发回流)，累计发送流。完成当前分层图的所有增广操作称作 **一个阶段** ，一个阶段的发送流总和为此分层图的 **阻塞流** 。一个阶段结束后，将此阶段阻塞流累计到最大流中，接着重置高度标号信息，再次执行 $bfs$ 得到新的分层图并重复 $dfs$ 的增广操作，直到无法分层时说明 $s$ 到 $t$ 已无增广路，算法结束，此时得到的阻塞流总和即为 $s$ 到 $t$ 的最大流。

高度标号的作用：在以 $dfs$ 增广时，每次从顶点 $u$ 到其邻接顶点 $v$ 的路径增长，都要考察 $v$ 的的高度是否比 $u$ 的高度大 1，以此来保证路径总是能 **按步增长到最后一层** 的 $t$ (在有增广路的前提下)。

#### 算法过程

给定一张图 $G(V, E)$ ，源点为 $s$ ，汇点为 $t$ 。求 $G$ 中从 $s$ 到 $t$ 的最大流 $f$ 。

1. 设置一张残留网络 (残留图/残差图/残余图) $G_f$ ，$G_f$ 初始为 $G$ 。
2. 调用 $bfs$ 方法，赋予 $G_f$ 中所有顶点以高度标号，建立当前分层图。注意在赋予高度时会先判断是否已赋过值，若有则跳过，因此顶点高度不会因为它处于多个层次而被较高的高度值覆盖，即一个顶点的高度是是它离源点最近的高度。此方法返回布尔值，有分层图 (即有增广路) 时返回 $true$ ，否则返回 $false$ 。
3. 求增广路发送流。以 $dfs$ 方法搜索 $s$ 到 $t$ 的增广路 $p$ ，并实时地发送 / 发回流，返回值为本次增广路发送流 (饱和边权 $c$)。在方法中比较当前边与上一条边的边权，取较小者，并将此取值作为递归 $dfs$ 方法的入参 (具体看代码)。若存在 $p$ ，也即递归调用到基本情形 (遇到 $t$ )，以当前边权减去 $c$ ，当前边的反向边权加上 $c$ ，然后返回 $c$ 。
4. 求阻塞流。反复求上述增广路发送流，并累积到当前分层图阻塞流中。在步骤 3 中，当前分层图完成所有增广由于已无增广路，不会递进到基本情形 (不会遇到 $t$ )，返回 0 且层层返回 0，于是发送流不大于 0，此时即可返回当前分层图的阻塞流。
5. **累计分层图阻塞流，清空所有顶点的高度标号信息** ，再次调用 $bfs$ 方法建立当前分层图，重复 2、3、 4，直到建立分层图的 $bfs$ 方法返回 $false$，表明当前图无法分层，即 $s$ 到 $t$ 无增广路，算法结束。此时 $s$ 到 $t$ 的最大流。

#### 实例分析

以下图为例，增广过程如下：

![image.png](https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/posts_img/algorithms/graph/dinic-example.png)

第一次：$s>a>c>t,$  找到增广路后 $return$，得到饱和边权 ，修改当前边正向和反向边权后 $return$，再次修改当前边的正向和反向边权后 $return$ (层层返回并修改边权)，$t>c>a>s$ 后得到本次增广路发送流为 2 。整体的顶点访问顺序为 $s>a>c>t>c>a>s$ 。

第二次：$s>a>c$ ，发现 $(c, t)$ 边权为 0，不满足邻边边权要大于 0 的条件，找 $a$ 的下一个满足层号关系的邻接顶点 $d$ ，然后 $d>t$ ，同上，找到增广路后在$return$ 过程中修改正反向边权，$t>d>a>s$ 后得到本次增广路发送流为 1 。整体的顶点访问顺序为 $s>a>c>d>t>d>a>s$ 。

第三次：从 $s$ 开始，发现 $(s, a)$ 边权为 0，不满足邻边边权要大于 0 的条件，找 $s$ 的下一个满足层号关系的邻接顶点 $b$ ，然后 $b>d>t$ ，同上，找到增广路后在 $return$ 过程中修改正反向边权，$t>d>b>s$ 后得到本次增广路发送流为 $2$ 。整体的顶点访问顺序为 $s>b>d>t>d>b>s$ 。

第四次：从 $s$ 开始，$for$ 循环遍历所有邻接顶点均不满足邻边边权要大于 0 的条件，返回 0 ，得到最终结果当前分层图阻塞流 5。

#### 时空复杂度

以下证明 Dinic 算法时间复杂度为：$O(|V|^2|E|)$

>  如下证明参考了[COMPSCI 638: Graph Algorithms, Lecture3](https://courses.cs.duke.edu/fall19/compsci638/fall19_notes/lecture3.pdf)。

##### 1. BFS建立分层图

时间复杂度为 $O(|E|)$ ，可参考无权最短路径复杂度分析，略。

##### 2. 一次DFS增广

在分层图中，由于高度标号加一的判断条件限制， $dfs$ 只能沿着高度递增的方向从 $s$ 到 $t$ 推进，因此单次 $dfs$ 推进次数最多不超过 $|V|-1$ 次，时间复杂度为 $O(|V|)$。

##### 3. 一个阶段中DFS增广次数

在分层图中，每次 $dfs$ 增广的结果使得一条高度递增方向上的饱和边 $(u, v)$ 消失，此边的反向边 $(v, u)$ 增加。如前述，**增广路只能沿着高度递增的方向**，而同一阶段内(同一张分层图中)反向边是沿着高度递减方向增加的。$(u, v)$ 消失后再次出现的条件是 $(v, u)$ 为此后某次增广路上的饱和边。**再次强调**，在 **同一阶段内** (同一张分层图中)，$(v, u)$方向是**高度递减**的，不可能出现在增广路上，因此一条高度递增边 $(u, v)$ 被删除后不会再次出现。一次增广至少令一条高度递增边饱和并删除，高度递增边数量不大于$|E|$，于是 **一个阶段内 $dfs$ 的次数最多为 $|E|$，即 $O(|E|)$**。结合 2 可知，**一个阶段的总复杂度为单次 $dfs$ 的复杂度与 $dfs$ 次数的乘积，即 $O(|V||E|)$**。

##### 4. 阶段数 (分层图建立次数)

**此证明是难点。** 如前述，在层高递增条件的限制下，$s - t$ 最短路径长度即 $t$ 的层高，因此最短路径最大不超过 $|V| - 1$。如果能证明每次分层图使得 $s - t$ 最短路径长 **「严格」递增** ，则立即推出阶段数(分层图建立次数)的上限为 $|V|$，复杂度为 $O(|V|)$。最短路径长严格递增的证明如下。

令相邻的两次分层图为 $G_f$  和 $G_{f'}$ ，以 $d(u, v)$ 和 $d'(u, v)$ 分别表示$G_f$  和 $G_{f'}$ 中的 $u$ 到 $v$ 的最短距离。

1. 由 [Edmonds-Karp算法复杂度证明](https://leetcode-cn.com/circle/discuss/tN3sZc/) 已知 (这一点很重要)，删正向边加反向边的操作，使得**源点 $s$ 到任意一点 $u$ 的距离是非递减**的，即 **必有** $d'(s, u) ≥ d(s, u)$。对证明过程稍加改造很容易得到一个对汇点 $t$ 来说类似的结论，即删正向边加反向边的操作，使得任意一点 $u$ 到汇点 $t$ 的距离是非递减的，即 **必有** $d'(u, t) ≥ d(u, t)$。

(1)    $d'(s, u) ≥ d(s, u)$

(2)    $d'(u, t) ≥ d(u, t)$

对于 $s - t$ 来说有 $d'(s, t) ≥ d(s, t)$。接下来的证明目标是**拿掉该不等式中的等号**，证明 $G_{f'}$ 相比 $G_f$，严格地有 $d'(s, t) > d(s, t)$。可用**反证法证明不可能取等号**。

2. **假设 $d'(s, t) ≥ d(s, t)$ 可以取到等号**。 
   若$G_{f'}$ 有一条 $s$ 到 $t$ 的最短路径 $f'$，则一定存在边 $(x, y) ∈ E_{f'}$，是 $G_f$ 某条增广路饱和边的反向边。因为如果 $E_{f'}$ 都是 $G_f$ 中存在的边，由于 $d'(s, t) = d(s, t)$，这样的 $f'$ 路径在 $G_f$ 中就**一定**已经被找到了。因此在 $G_f$ 中有 $(y, x) ∈ E_f$ ，于是有

(3)    $d(s, x) = d(s, y) + 1$

![image.png](https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/posts_img/algorithms/graph/dinic-proof.png)

3. 由 (1) 和 (2) 易知

(4)    $d'(s, x) ≥ d(s, x)$

(5)    $d'(y, t) ≥ d(y, t)$

4. $f'$ 路径长可写成 $d'(s, t) = d'(s, x) + 1 + d'(y, t)$ ，应用 (4) 和 (5) 得到

$d'(s, t) = d'(s, x) + 1 + d'(y, t) ≥ d(s, x) + 1 + d(y, t)$

又由 (3) 得到

$d'(s, t) = d'(s, x) + 1 + d'(y, t) ≥ d(s, x) + 1 + d(y, t) = d(s, y) + d(y, t) + 2$

即

(6)    $d'(s, t) ≥ d(s, t) + 2$

由此，$d'(s, t) = d(s, t)$ 的假设不成立，但我们知道 $d'(s, t) ≥ d(s, t)$ ，因此有 $d'(s, t) > d(s, t)$ ，也即证明了 **Dinic 算法中下一分层图的最短路径长度与前一分层图相比严格递增**。

综上，总时间复杂度为每个阶段建立分层图的复杂度 $O(|E|)$ 与在该分层图内执行的总 $dfs$ 复杂度 $O(|V||E|)$ 之和乘以阶段数 $O(|V|)$，为 $O((|E|+|V||E|)*|V|)$，即 $O(|V|^2|E|)$。

空间复杂度：采用邻接表存图，则存图空间为 $O(|V|+|E|)$ ，采用邻接矩阵为 $O(|V|^2)$ 。 $bfs$ 中的队列为 $O(|V|)$ ， $dfs$ 中的递归栈为 $O(|V|)$ 。总体来说取决于存图方式。

#### 代码

```java
// TODO
```

## 实战应用

给出以下图论相关题目及作者写的题解，供读者在阅读本文后自练自查。

※ 不断更新中。

| 题目                                                         | 难度 | 题解                                                         |
| ------------------------------------------------------------ | ---- | ------------------------------------------------------------ |
| [323. 无向图中连通分量的数目](https://leetcode.cn/problems/number-of-connected-components-in-an-undirected-graph/) | 中等 | [题解](https://leetcode.cn/problems/number-of-connected-components-in-an-undirected-graph/solution/by-yukiyama-y5l4/) |
| [547.省份数量](https://leetcode-cn.com/problems/number-of-provinces/) | 中等 | [题解](https://leetcode.cn/problems/number-of-provinces/solution/by-yukiyama-mh7f/) |
| [200.岛屿数量](https://leetcode-cn.com/problems/number-of-islands/) | 中等 | [题解](https://leetcode.cn/problems/number-of-islands/solution/by-yukiyama-jkd6/) |
| [695. 岛屿的最大面积](https://leetcode.cn/problems/max-area-of-island/) | 中等 | [题解](https://leetcode.cn/problems/max-area-of-island/solution/by-yukiyama-0mrt/) |
| [785. 判断二分图](https://leetcode.cn/problems/is-graph-bipartite/) | 中等 | [题解](https://leetcode.cn/problems/is-graph-bipartite/solution/by-yukiyama-yoc0/) |
| [684. 冗余连接](https://leetcode.cn/problems/redundant-connection/) | 中等 | [题解](https://leetcode.cn/problems/redundant-connection/solution/-by-yukiyama-mlqi/) |
| [1631. 最小体力消耗路径](https://leetcode.cn/problems/path-with-minimum-effort/) | 中等 | [题解](https://leetcode.cn/problems/path-with-minimum-effort/solution/yukiyama-by-yukiyama-qboz/) |
| [329. 矩阵中的最长递增路径](https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/) | 困难 | [题解](https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/solution/by-yukiyama-d7bv/) |
| [207. 课程表](https://leetcode.cn/problems/course-schedule/) | 中等 | [题解](https://leetcode.cn/problems/course-schedule/solution/yukiyama-by-yukiyama-lbz3/) |
| [210. 课程表 II](https://leetcode.cn/problems/course-schedule-ii/) | 中等 | [题解](https://leetcode.cn/problems/course-schedule-ii/solution/-by-yukiyama-9scu/) |
| [269. 火星词典](https://leetcode.cn/problems/alien-dictionary/) | 困难 | [题解](https://leetcode.cn/problems/alien-dictionary/solution/by-yukiyama-2cam/) |
| [444. 序列重建](https://leetcode.cn/problems/sequence-reconstruction/) | 中等 | [题解](https://leetcode.cn/problems/sequence-reconstruction/solution/by-yukiyama-a371/) |
| 814.无向图中的最短路径 (其他平台题目)                        | 中等 |                                                              |
| [743. 网络延迟时间](https://leetcode.cn/problems/network-delay-time/) | 中等 |                                                              |
| [1334. 阈值距离内邻居最少的城市](https://leetcode.cn/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/) | 中等 |                                                              |
| [1135. 最低成本联通所有城市](https://leetcode.cn/problems/connecting-cities-with-minimum-cost/) | 中等 |                                                              |

| 题目                                                         | UF   | BFS/DFS | Topo | SP   | MST  | MF   |
| ------------------------------------------------------------ | ---- | ------- | ---- | ---- | ---- | ---- |
| [323](https://leetcode.cn/problems/number-of-connected-components-in-an-undirected-graph/) | 〇   | 〇      |      |      |      |      |
| [547](https://leetcode-cn.com/problems/number-of-provinces/) | 〇   | 〇      |      |      |      |      |
| [200](https://leetcode.cn/problems/number-of-islands/)       | 〇   | 〇      |      |      |      |      |
| [695](https://leetcode.cn/problems/max-area-of-island/)      | 〇   | 〇      |      |      |      |      |
| [785](https://leetcode.cn/problems/is-graph-bipartite/)      | 〇   | 〇      |      |      |      |      |
| [684](https://leetcode.cn/problems/redundant-connection/)    | 〇   | 〇      |      |      |      |      |
| [1631](https://leetcode.cn/problems/path-with-minimum-effort/) | 〇   | 〇      |      | 〇   |      |      |
| [329](https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/) |      | 〇      | 〇   |      |      |      |
| [207](https://leetcode.cn/problems/course-schedule/)         |      | 〇      | 〇   |      |      |      |
| [210](https://leetcode.cn/problems/course-schedule-ii/)      |      | 〇      | 〇   |      |      |      |
| [269](https://leetcode.cn/problems/alien-dictionary/)        |      | 〇      | 〇   |      |      |      |
| [444](https://leetcode.cn/problems/sequence-reconstruction/) |      | 〇      | 〇   |      |      |      |
| 814                                                          |      |         |      | 〇   |      |      |
| [743](https://leetcode.cn/problems/network-delay-time/)      |      |         |      | 〇   |      |      |
| [1334](https://leetcode.cn/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/) |      |         |      | 〇   |      |      |
| [1135](https://leetcode.cn/problems/connecting-cities-with-minimum-cost/) |      |         |      |      | 〇   |      |

```text
UF: Union-Find 并查集
FS: DFS & BFS 深搜和广搜
Topo: Topological Sort 拓扑排序
SP: Shortest Path 最短路
MST: Minimum Spanning Tree 最小生成树
MF: Maximum Flow 最大流

标记 〇 表示该题与该算法相关。
```

----

【更新日志】

[2022-09-20]

- 修改了 Bellman-Ford 方法求解 [743. 网络延迟时间](https://leetcode.cn/problems/network-delay-time/) 的代码中的一处 bug 。即若本次全量松弛执行了松弛操作，则 `finished = false` ，随后在开始下一次全量松弛前应将 `finished` 置回 `true`。感谢 [@nTouKxAnj3](/u/nTouKxAnj3/) (@河) 、 [@rain-roc](/u/rain-roc/) (@RainRoc) 指出。

[2022-09-08]

- 新增了 Prim 算法正确性证明小节。（小节路径: 最小生成树 > Prim > 朴素版 > 正确性证明）

[2022-07-17]

- 大幅修改了「最大流最小割定理」中的「证明 $k=m$」小节的内容，修正了前一天发现的证明过程中的错误 (结论正确，过程有误)。虽然作者认为修正后的证明是正确的，但如果读者仍觉得有问题，还请评论或私信联系。

[2022-07-16]

- 在「最大流最小割定理」一节的「最小割的大小」小节中，原文称「现在我们来指出一个 $l = 4$ 的割 .... .... 就得到了原图的一个大小为 4 的 $s-t$ 割」。根据原文的描述，似乎无法指出大小为 4 的割。这个部分有待更正，目前还在思考。。。暂时先以删除线划去，并注明证明暂不成立。
- 在「Edmonds-Karp」-「时间复杂度」-「2.2 增广次数」中，原文称「...之后 $(u, v)$ 要再次出现的前提是 $(v, u)$ 为饱和边...」，这是错误的。正确表述是「...之后 $(u, v)$ 要再次出现的前提是 $(v, u)$ 为 **增广路上的边** ...」，后续论证仍然成立。
- 上述两点均由 [@migeater](/u/migeater/) 指出，非常感谢！🙏

[2022-07-01]

- 在「链式向前星」中增加图示及若干补充描述。

[2022-06-20]

- 新增「网络流」一节。

[2022-06-19]

- 在「图的表示」一节中新增「链式向前星」小节，并在后续代码中给出此存图方式的代码实例。