%%
# 纲要
> 主干纲要、Hint/线索/路标
# Q&A
#### 已明确
#### 待明确
> 当下仍存有的疑惑
**❓<font color="#c0504d"> 有什么问题？</font>**
# Buffer
## 闪念
> sudden idea
## 候选资料
> Read it later
# 图的表示实现细节说明
❓ <font color="#c00000">如何建图？</font>
- 给定**边集或邻接矩阵**，根据边建图（**邻接表保存图**）
- 无向图 => **建两条有向边**；
❓ <font color="#c00000"> DFS/BFS 搜索，什么时候需要 visited 数组？什么时候不需要？</font>
1. 在图上时：
1. **一般图**：需要；
2. **DAG (有向无环图)**： 不需要；
- 从任意节点出发进行 DFS/BFS 搜索，"**同一路径**" 上一定不会回到 "**当前已遍历过**" 的节点/边，因此当前路径上的节点/边都不会被重复访问。
2. 在树上：
- **树上 DFS/BFS 搜索不需要**，只需用一个变量**记录前一个父节点 parent**即可，跳过父节点，就**不会重复访问同一个节点或边**。
- 因为树是无环无向图，只要**保证不回头**，则**任意两节点间的边只会经过一次**。
- ![[Excalidraw-Solution/树.excalidraw.svg|525]]
3. 在网格图上：
- **需要**，但可以采用**其他方式**实现，例如在原网格值 `grid[i][j]` 上直接进行标记。
❓ <font color="#c00000">如何表示 "已访问过的位置" ？</font>
- 对于一般图：
- **标记访问过的顶点**——用 `vector<int> visited`；
- **标记访问过的边**——用 `set<pair<int,int>>`；
- 不能使用 `unordered_set<pair<int,int>>`，因为**没有为 `pair` 类型定义哈希函数**。
- 对于网格图：
1. 开一个**与原矩阵相同尺寸的 `vector<vector<bool>> visited(m, vector<bool>(n))` 矩阵**进行标识。
2. 使用**有序集合** **`set<pair<int, int>>` 存储坐标点**进行标识
- 不能使用 `unordered_set<pair<int,int>>`，因为**没有为 `pair` 类型定义哈希函数**。
3. 矩阵元素值非负时，**==取负==进行标识**，**需要用元素值时，取绝对值**即可：
- `grid[i][j] < 0` 表示已访问过；
- `abs(grid[i][j])` 表示原始值；
4. 矩阵元素值范围为 `[min, max]` 时，令**每个值 `gird[i][j] += (max-min+1)`**：
- `grid[i][j] > max` 表示已访问过；
- `(grid[i][j] > max) ? grid[i][j] - (max-min+1) : grid[i][j]` 表示原始值。
> [!NOTE] ❓ <font color="#c00000">如何标记 "已访问过的位置" ？</font>
>
> - 方法一：使用一个**额外的 `m*n` 的`visited` 数组来标记已访问**。
> - 方法二：直接**修改原矩阵中的值标记 "已访问**"，最后**再额外扫描一次恢复原矩阵的值**，则空间开销降为 $O(1)$；
## 网格图方向的表示
上下左右四个方向：
```cpp
constepxr int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (const auto& [dx, dy] : dirs) {
int nx = x + dx, ny = y + dy;
}
```
相邻一圈 8 个方向：
```cpp
// 方式一:
constexpr int dir_x[8] {0, 0, 1, 1, 1, -1, -1, -1};
constexpr int dir_y[8] {-1, 1, -1, 0, 1, -1, 0, 1};
for (int i = 0; i < 8; ++i) {
int nx = x + dir_x[i], ny = y + dir_y[i];
...
}
// 方式二:
constexpr int dir_x[3] {0, -1, 1};
constexpr int dir_y[3] {0, -1, 1};
for (int dx : dir_x) {
for (int dy : dir_y) { // 会有一个偏移量(0,0).
int nx = x + dx, ny = y + dy;
if (dx == 0 && dy == 0) continue;
...
}
}
```
%%
# 图相关算法总览
- 图的遍历算法
- ![[00-数据结构与算法笔记/数据结构/图相关算法#^ub7lm8]]
- ![[00-数据结构与算法笔记/数据结构/图相关算法#^1j9yqm]]
- Tarjan 算法：
- 强连通分量问题（查找有向图中的强连通分量，或强连通分量分解）
- 双连通分量问题（求出无向图的"割点"与"桥"，双连通分量分解, 求出**无向图中的所有双连通分量**）
- 最近公共祖先问题（LCA）
![[00-数据结构与算法笔记/数据结构/图相关算法#^ut8xuj]]
- 最小生成树问题
- Kruskal 算法
- Prim 算法
- 拓扑排序
<br><br>
# 图搜索
> [!NOTE] 标注 🏳️🌈 的代表 DFS/BFS 两种方法均可
- DFS 应用 ^ub7lm8
- **回溯**：暴力搜索，枚举所有可能情况
- 搜索/枚举**两顶点间所有路径**
- **有向图的环路检测**（三色标识法）
- **搜索连通分量** 🏳️🌈
- 找出图中的所有连通分量 （统计数量）
- 搜索**一个极大连通分量**，包括
- 得到连通分量的**支撑树**（为顶点染色标识）
- 获取连通分量中的**顶点集**、**顶点总数**；
- 获取连通分量中的**边集**、**边总数**
- **判断两顶点间连通性**（判断是否可达）
- **求两顶点间路径数量**（DFS 分治 & 记忆化优化）
- BFS 应用 ^1j9yqm
- **顶点 u 出发==可行走的最大步数==** （顶点 u 的最大邻居阶数） 🏳️🌈
- **顶点 u 出发行走==指定步数==可抵达的位置** （顶点 u 指定阶数的邻居）🏳️🌈
- **无权图的单源最短路径**
- 顶点 u 到**单个顶点 v** 的最短距离
- 顶点 u 到**最近的某一类顶点 vs** 的最短距离（多源 BFS，**以 vs 类顶点为起点**，反过来求）
- "**某一类顶点 us**" 到 **==离各自最近==的 "另一类顶点 vs"** 的最短距离（多源 BFS，同上）
- **拓扑排序**
> [!NOTE]
>
> 无向图中进行 DFS/BFS 搜索时，通常 **==不能重复访问节点==**，仅在需要 "**==松弛操作==**" 时（从不同路径**到达节点时方案更优**，或者**到达节点时状态不同**）**才允许重复访问**。
>
> - [[99-题解/leetcode/lc-505 迷宫 II|lc-505 迷宫 II]]
> - [[99-题解/leetcode/lc-1129 颜色交替的最短路径|lc-1129 颜色交替的最短路径]]
> - [[99-题解/leetcode/lc-1293 网格中的最短路径|lc-1293 网格中的最短路径]]
>
## 连通分量
> [!NOTE] 有向图中没有 "**连通分量**" 的概念。
>
> 找 "**==极大有根树==**" 时需要**从 "==入度为 0==" 的顶点**进行 DFS/BFS，并且**允许访问重复节点**（一个子图可能**被多个有根树共享**）。
## 连通图的生成树
> **生成树**也即**支撑树**，即覆盖连通图中 "**所有顶点**" 的树。
- 对于 "**连通图**"，从**任一顶点**出发进行 DFS/BFS（不访问重复顶点），可得到图中的 "**==支撑树==**"。
- 对于 "**非连通图**"，分别以所有顶点为起点进行 DFS/BFS（不访问重复顶点），可得到 "**==支撑森林==**"
- 即为 "图中**每个独立连通分量**分别得到各自的支撑树"。
![[Excalidraw-Solution/图相关算法_2.excalidraw|775]]
## 环路检测
> 判断**是否存在环**，求出**环路上的边 or 顶点**。
- **无向图环路检测**：三种方法
- （1）**==DFS & 跳过父节点==**
- DFS 过程中，若每个节点的邻居在 **==排除父节点==** 后**还存在已访问过的顶点**，则说明有环
- （2）**==并查集==**
- 遍历 **边集**，对于一条边 `u-v`，若两端顶点**此前已连通，说明有环**；若尚未连通，则连通两顶点，标记边加入图中
- （3）**==拓扑排序==**
- 每次移除所有**度减为 1** 的顶点，若无环，则 n 个顶点将全被移除；若有环，则**环上顶点度大于 1**
- **有向图环路检测**：两种方式
- （1）**==三色标记法 & DFS==**；
- 0/1/2，分别表示 **"未访问过"**，**"在当前 DFS 路径上 or 已访问过从该顶点出发有环"**，**"已访问过但未在当前 DFS 路径上，且从该顶点出发无环"**；
- （2）**==拓扑排序==**
- 每次移除所有**入度减为 0** 的顶点，若无环，则 n 个顶点将全被移除；若有环，则**环上顶点入度大于 0**；
例题参见[[01-题单分类/图题单#环路检测|图题单]]
<br><br>
# 最短路径问题
> 参见[^1]
> [!NOTE] 最短路径
>
> - **单源**最短路径：求解图中**某个起始顶点**到**其它所有顶点**之间的最短路径
> - **多源**最短路径：求解出图中**每个顶点到其它所有顶点**之间的最短路径。
>
- 最短路径问题 ^ut8xuj
- **无权图**中的**单源**最短路径问题（边没有权值，或者所有边权值相等）
- BFS 逐层遍历求解
- **带权图**中的**单源**最短路径问题
- **边的权值非负**：Dijkstra 算法
- **边的权值可为负**：
- Bellman-ford 算法
- SPFA 算法 (Bellman-Ford 算法的改进版本)
- **带权图**中的**多源**最短路径问题
- Floyd 算法
| 算法名称 | 适用问题 | 时间复杂度 | 空间复杂度 | 处理负权边 | 处理负权回路 |
| ------------ | ------- | ----------------------- | ------ | ----- | ------ |
| BFS | 无权图; 单源 | $O(V+E)$ | $O(V)$ | | |
| Dijkstra | 带权图; 单源 | $O(E+V^2)=O(V^2)$ | $O(E)$ | ❌ | ❌ |
| | | $O(E*logE)$ 小顶堆优化 | $O(E)$ | ❌ | ❌ |
| Bellman-Ford | 带权图; 单源 | $O(V*E)$ | $O(V)$ | ✔ | ✔ |
| SPFA | 带权图; 单源 | 趋近 $O(E)$，最坏 $O (V*E)$ | $O(V)$ | ✔ | ✔ |
| Floyd | 带权图; 多源 | $O(V^3)$ | | ✔ | ❌ |
> [!NOTE] 对无向图、有向图均可求解最短路径。
> [!info] 负权回路：环上 "边权总和"为负，故可无限循环
<br><br>
## BFS 求无权图的单源最短路径
以给定顶点为起点， **==BFS 逐层遍历==**，**可求得起点到各顶点的单源最短路径**。
BFS 时记录**层数**，每一层即代表一个步长，**首次访问**到一个顶点时：
1. BFS 的步数即为 **起点到该顶点的最短路径**。该顶点的 "前驱顶点"
2. 该顶点的 "**前驱顶点**"，即为该最短路径上抵达该顶点的 "**前驱顶点**"。
###### 一般图示例
```cpp
/* 利用BFS求解无权图中的单源最短路径*/
class BFS_ShortestPath {
private:
vector<vector<int>> graph;
vector<int> dist;
vector<vector<int>> prevs;
public:
void build_graph(int n, vector<vector<int>>& edges) {
graph = vector<vector<int>>(n);
dist = vector<int>(n, INT_MAX); // dist[i]记录起点到顶点i的最短路径
prevs = vector<vector<int>>(n); // prevs[i]记录顶点i的最短路径上的前驱顶点.
}
// 获取起点到指定终点`dest`的最短路径上的边.(最短路径可能不唯一, 故输出所有最短路径上存在的边.)
// `prevs`是给定起点到各顶点的最短路径上的前驱顶点.
vector<pair<int,int>> get_edges_in_shortest_path(int dest) {
int n = graph.size();
vector<pair<int, int>> edges;
vector<bool> visited(n, false);
queue<int> que {{dest}};
visited[dest] = true;
while (!que.empty()) { // 从dest起, 反向遍历prevs给出的有向图.
int u = que.front(); que.pop();
for (const int v : prevs[u]) {
if (visited[v]) continue;
visited[v] = true;
edges.emplace_back(v, u);
que.emplace(v);
}
}
return edges;
}
// 求起点start到其余各顶点的最短距离.
vector<int> ShortestPathByBFS(vector<vector<int>>& graph, int start) { // graph是邻接表.
int n = graph.size();
queue<int> que{{start}};
dist[start] = 0;
int step = -1;
while (!que.empty()) {
++step;
int size = que.size();
while (size--) {
int u = que.front(); que.pop();
for (const int v : graph[u]) {
if (dist[v] != INT_MAX) continue; // 已访问过, 已求得最短路径
dist[v] = step + 1; // 下一步将访问v, 得到起点到v的最短距离.
que.emplace(v);
prevs[v].emplace_back(u); // 记录到v的最短路径上的前驱顶点
}
}
}
return dist;
}
};
```
###### 网格图示例
示例参见 [[99-题解/leetcode/lc-1091 二进制矩阵中的最短路径|lc-1091 二进制矩阵中的最短路径]]，求**起点到终点**的 **最短路径长度**
```cpp
class Solution {
public:
static constexpr int dirs[8][2] {
{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}
};
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
int n = grid.size();
if (grid[0][0] == 1) return -1; // 特判: 起点不可达.
if (n == 1 && grid[0][0] == 0) return 1; // 特判: 起点即终点的情况
vector<vector<bool>> visited(n, vector<bool>(n, false));
queue<pair<int, int>> que {{ {0, 0} }};
visited[0][0] = true;
int path_len = 0; // 路径长度: 途径的单元格数量.
while (!que.empty()) {
++path_len;
int size = que.size();
while (size--) {
auto [x, y] = que.front(); que.pop();
if (x == n - 1 && y == n - 1) { // 涵盖起点即终点的情况.
return path_len;
}
for (const auto& [dx, dy] : dirs) {
int nx = x + dx, ny = y + dy;
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (grid[nx][ny] == 1) continue;
if (visited[nx][ny]) continue;
visited[nx][ny] = true;
que.emplace(nx, ny);
}
}
}
return -1;
}
};
```
<br><br>
## Dijsktra 算法
> 算法功能：**带权图的单源最短路径**
> [!caution] Dijsktra 不能用于存在 "**==负权边==**" 的图。
>
> Dijsktra 每次 "**==贪心==**" 地选择当前**距离源点最短的顶点**，
> 如果存在**负权边**，贪心策略可能会 **==提前确定一个错误的最短路径==**。
>
> 例如**在确定到某顶点的最短距离**后，若**后续路径若有负权边**，则将能够缩短该顶点到起点的最短距离。
> 然而此时**算法已经结束了对该顶点的计算**，**无法再利用负权边对已处理过的顶点进行更新**，从而导致错误。
>
>
> ![[Excalidraw-Solution/图相关算法.excalidraw|461]]
>
>
### 算法步骤
1. 开一个数组，`dist[v]` 记录**起点 s 到图中其余顶点`v`** 的**带权最短路径**，初始化 `dist[s] = 0`，其余 `dist[v] = INF`；
2. 从起点 s 出发，初始时得到**起点 s 到其直接邻居 v 的距离**。
3. 此后每一步，重复两个步骤，直至为 "**所有可达顶点**" 求得最短路径。
1. 从 "**所有剩余待确认顶点**" 中找出 "**==距离起点 s 最近的顶点`u`==**"，则 **u 到起点 s 的最短距离**即为 "**==当前求得的距离== `dist[u]`**"；
2. **==松弛 u 的所有邻接点==**：以 `u` 作为中转点，求得 "**起点s -> ==途经u== -> u 的直接邻居顶点 v**" 的最小距离，**若该距离小于当前 `dist[v]`，则更新 `dist[v]`**。
### 算法实现说明
两种实现版本：
- （1）**朴素实现**：
- 需要一个 `visited[v]` 数组标记 "**是否已为顶点 u 求得最短距离**"；
- 每一步需要 **==遍历所有顶点==**，从中找出 "**当前剩余顶点中，==距离起点 s 最近的顶点 u==**"；
- 复杂度分析：
- 时间复杂度：$O(|V|^2)$；**每一步需要遍历所有顶点**，从而找出剩余顶点中距离起点最近的顶点。
- 空间复杂度：$O(|V|)$
- `dist[]` 数组记录各顶点距离起点的距离
- `visited[]` 数组记录 "是否已求得该顶点到起点的最短距离"
- （2）**小顶堆优化实现**
- 使用一个 "**==小顶堆==**" 维护 "**当前剩余顶点到起点 s 的距离**"：`{顶点v到起点s的距离, 顶点v}`，每次可直接取**堆顶元素**。
- 若 "**堆顶元素**" 记录的距离大于 `dist[v]`，表明**堆顶元素过期**，持续弹出，直至获取**有效堆顶元素**。
- 复杂度分析：
- 时间复杂度：$O(|E|\log |E|)$ 或 $O(|E|\log|V|)$ ，取决于 "优先队列" 的具体实现。
- 使用 C++ 中的 `priority_queue` 时，由于图上每条边都可能被 "**==松弛一次==**"，故**每个顶点可能出入堆多次**，但**出入堆次数**以及**堆中元素总数**均不超过边数 $|E|$，故时间复杂度为 $O(|E|\log |E|)$ 。
- 空间复杂度：$O(|N|+|E|)$
- `dist[]` 数组记录距离；
- `min_pq` 小顶堆，元素数量最多为 $|E|$
> [!NOTE] 关于 Dijsktra 算法优化的时间复杂度说明
>
> ![[_attachment/00-数据结构与算法笔记/数据结构/图相关算法.assets/IMG-图相关算法-64DC6B5A58290AF63348383B731E927C.png|738]]
>
> 在 C++中：
>
> - 若使用 `priority_queue`，其实现是 "**二叉堆**"，不直接支持 `decrease-key` （减小一个元素值）操作。
> 因此只能通过 "**==惰性删除==**" 来间接模拟 `decrease-key`，这一情况下堆中可能包含重复元素，最多 $O(|E|)$ 个，故时间复杂度为 $O(|E|\log |E|)$
>
>>
>
> - 若使用 `set`，其实现是 "**红黑树**"，获取最小元素的开销是 $O(1)$ （`set.begin()`），每次松弛时，**可先删除旧值**，**再插入新距离值**，保证堆中元素总数不超过 $|V||$，故时间开销为 $O(|E|\log|V|)$。
### 小顶堆实现
下面给出 Dijsktra 算法获取 "**无向带权图**" 中 "**==指定起点的单源最短路径距离==**" 以及 "**==到指定终点的最短路径上所有边==**" 的实现。
> [!NOTE] **获取最短路径上所有边**
>
> 1. 首先，需应用 Dijsktra 算法获取指定起点**到各顶点的最短距离数组 `dist[v]`**；
> 2. 从 "**==指定终点==**" 起始，依据 `dist[v] + w == dist[u]` 这一关系进行**反向 DFS 或 BFS**，为每个 "**==更远顶点==**" 找到**关联的 "==更近顶点=="**，即为其 "**==前驱顶点==**"。
>
>
> > [!NOTE] 另一种实现方式： 直接使用 `vector<vector<int>> prevs(n)` 数组在 Dijsktra 过程中**记录每个顶点到起点的==最短路径上的前驱顶点==**。
> >
> > - 相当于用**最短路径边**构建了一个 **==各顶点->起点==**的 "**==反向有向图==**"。
> > - 最后，从**指定终点**起，**反向应用 DFS 或 BFS 遍历，即可得到给定起点->终点间最短路径上所有边**。
> >
>
> 例题： [[99-题解/leetcode/lc-3123 最短路径中的边|lc-3123 最短路径中的边]]
```cpp
class Dijsktra {
private:
using PII = pair<int,int>;
vector<vector<PII>> graph;
public:
void build_graph(int n, vector<vector<int>>& edges) {
graph.clear();
graph.resize(n);
for (const auto& e : edges) {
graph[e[0]].emplace_back(e[1], e[2]);
graph[e[1]].emplace_back(e[0], e[2]);
}
}
// 获取指定起点的单源最短距离.
vector<int> get_shortest_dist(int start) {
int n = graph.size();
vector<int> dist(n, INT_MAX);
priority_queue<PII, vector<PII>, greater<>> min_pq; // `{起点到顶点的距离, 顶点}`
min_pq.emplace(0, start);
dist[start] = 0;
while (!min_pq.empty()) {
auto [d, u] = min_pq.top(); min_pq.pop();
if (d > dist[u]) continue;
for (const auto& [v, w] : graph[u]) {
int new_d = d + w;
if (new_d < dist[v]) {
dist[v] = new_d;
min_pq.emplace(new_d, v);
}
}
}
return dist;
}
// 获取所有最短路径上的边.(最短路径可能不唯一, 打印出所有最短路径构成的连通分量上的各条边)
vector<pair<int,int>> get_edges_in_shortest_path(vector<int>& dist, int dest){
int n = dist.size(); // n个顶点
vector<bool> visited(n, false);
vector<pair<int,int>> edges;
auto dfs = [&](auto& self, int u) -> void {
visited[u] = true;
for (const auto [v, w] : graph[u]) {
if (dist[v] + w == dist[u]) {
edges.emplace_back(v, u); // 不会重复. 保证只会从"更远顶点"指向"更近顶点".
if (!visited[v]) {
self(self, v);
}
}
}
};
dfs(dfs, dest);
return edges;
}
};
```
<br><br>
## Bellman-Ford 算法
> 算法功能：**带权图的单源最短路径**，可确**处理负权边** & **检测负权环**（即图中存在**无法终止的负权循环**）
### 算法步骤
1. 数组 **`dist[v]`记录起点 s 到各顶点 v 的最短距离**，初始化为 `dist[s] = 0`，其余为 INT_MAX。
2. **松弛操作**：
- 进行 **`N-1` 轮迭代**，`N` 为图中顶点数量。
- 每轮迭代，**==遍历图上所有边==**，对于边 `(u,v,w)` ：
- 若 `dist[v] + w < dist[u]` 成立，则更新 `dist[u]`；
- 对于 "**无向图**"，同时**检查 `dist[u] + w < dist[u]` 是否成立，若成立则更新 `dist[v]`**。
- 若一整轮中，**没有任何 `dist[v]` 被松弛更新**，代表 "**==已求得到各顶点的最短路径距离==**"，则跳出循环。
3. **负权回路检测**：
- 完成 `N-1` 轮迭代后，再进行一次检查，若还有边可以 "**==被松弛==**"，说明图中**存在负权回路**。
> [!NOTE] 算法正确性理解
> 对于存在 **N 个顶点的连通图**，图上**任意两点间路径最多经过 ==N-1 条边==**。
>
> - 在第 1 轮松弛操作中，得到所有**离起点==经过 1 条边==的路径** => `dist` 中求得 "**经过 ==1 条边==到各顶点**" 的最短路径的距离；
> - 在第 2 轮松弛操作中，得到所有**离起点==经过 2 条边==的路径** => `dist` 中求得 "**经过 ==最多 2 条边==到各顶点**" 的最短路径的距离；
> - ......
> - 在第 N-1 轮松弛操作中，得到所有**离起点==经过 2 条边==的路径** => `dist` 中求得 "**经过 ==最多N-1 条边==到各顶点**" 的最短路径距离；
>
> ![[Excalidraw-Solution/图相关算法_3.excalidraw|1000]]
>
> [!NOTE] 证明： "若一整轮中没有任何 `dist[v]` 被更新则可提前结束"
>
> 假设**第 k 轮没有任何 `dist[v]` 被更新**，说明**对所有边 `(u, v, w)` 均有 `dist[u] + w >= dist[v]`**。
>
> 由于：（1）**==第 k + 1 轮遍历的"边"== 与第 k 轮==完全相同==**；（2）**第 k 轮中，与 v 相邻的所有顶点 `u` 的 ==`dist[u]` 均未被更新==**。
>
> 因此**第 k+1 轮中 `dist[v]` 也不会被更新**。
### 实现
- 时间复杂度：$O(|V|*|E|)$；
- 空间复杂度：$O(|V|)$
```cpp
void BellMan_Ford(int n, vector<vector<int>>& edges, int start) {
vector<int> dist(n, INT_MAX);
dist[start] = 0;
// 遍历所有边, 进行松弛操作, 最多迭代n-1轮.
for (int i = 0; i < n - 1; ++i) {
bool update = false; // 标记此轮中是否有dist[]被更新.
for (const auto& e : edges) {
int u = e[0], v = e[1], w = e[2];
if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
update = true;
}
// 对于无向图, 需要同时考虑`v->u`.
if (dist[v] != INT_MAX && dist[v] + w < dist[u]) {
dist[u] = dist[v] + w;
update = true;
}
}
if (!update) break; // 此轮中没有任何dist被更新, 说明已求得起点到各顶点的最短路径距离.
}
// 第n轮检查是否存在 "负权回路"
for (const auto& e : edges) {
int u = e[0], v = e[1], w = e[2];
if (dist[u] != INT_MAX && dist[u] + w < dist[v] ||
dist[v] != INT_MAX && dist[v] + w < dist[u]) {
cout << "图中存在负权回路!" << endl;
return;
}
}
cout << "得到有效的单源最短距离dist" << endl;
}
```
<br><br>
## SPFA 算法
> SPFA（Shortest Path Faster Algorithm），是 **基于 Bellman-Ford 算法的优化算法**。
思路： 用 **队列** 来维护 **==被更新/松弛过==的节点**，基于**顶点 u 的 `dist[u]`** 去**尝试松弛其邻居`v`**，仅当 v 的 `dist[v]` 被更新时，才将`v` 加入队列。
> [!NOTE] SPFA 算法也即 "**==BFS + 松弛操作==**"。当顶点 v 的 `dist[v]` 被更新时，重新队列进行搜索。
>
> 若按 "**层**" 记录队列操作，则 **"每一层"** 即等价于 Bellman-Ford 算法中的 "**==一轮迭代==**"：
>
> - 第 1 层时，队列中存储的都是**从起点 1 步可达的邻居**；
> - 第 2 层时，队列中存储的都是**从起点 2 步以内可达的邻居**；
> - 第 k 层时，队列中存储的都是**从起点 k 步以内可达的邻居**。
>
> 同 Bellman-Ford 算法，$N$ 个顶点的图上，**任意两顶点间最短路径==最多包含 $N-1$ 条边==**。
> 因此在没有 "**==负权回路==**" 的情况下，**每个顶点最多出入队列 $N-1$ 次必然可求得最短路径**。
> 由于每次顶点入队都可能导致**其所有邻边被松弛**，因此**所有边**共计最多被松弛 $N*E$ 次，故时间复杂度**最坏上限为 $O(N*E)$**。
### 算法步骤
1. 维护三个数组：
- `dist[v]` 记录起点到各顶点 v 的最短距离，初始化起点 `dist[s] = 0`，其余为 INT_MAX；
- `inQueue[v]` 记录**顶点 ==v 是否已在队列中==**。当 `dist[v]` 被更新时，若**队列中已存在 `v`**，则**不必重复入队**。=> 队列弹出 v 时，将基于最新的 `dist[v]` 进行松弛。
- `count[v]` 记录**顶点 v的 `dist[v]` 被==松弛过的次==数**，当松弛次数**超过 v-1 次**说明存在 **==负权回路==**。
2. 初始时，将**起点入队**。
3. 每次从队列中**取出一个顶点 u**，根据 `u->v`，若 `dist[u]+w < dist[v]` 则更新`dist[v]`。**若 `dist[v]` 被更新，则将 `v` 加入队列进一步搜索**。
4. 重复步骤 3，直至**队列为空**，或者**某顶点松弛次数超过 v-1 次**。
##### 复杂度分析
| | 最优 | 最坏 | 说明 |
| ----- | ------ | -------- | -------------------------------------------------------------------- |
| 时间复杂度 | $O(E)$ | $O(V*E)$ | 最坏情况下，**每个顶点可能被入队 V-1 次**，导致所有边共计最多被松弛 $V*E$ 次松弛操作，退化为 Bellman-Ford。 |
| 空间复杂度 | $O(V)$ | $O(V)$ | 由于有 `inQueue` 标记，队列中无重复顶点，故不超过 $V$ |
### 实现
```cpp
void SPFA(int n, vector<vector<int>>& edges, int start) {
vector<vector<pair<int, int>>> graph(n);
for (const auto& e : edges) {
graph[e[0]].emplace_back(e[1], e[2]);
graph[e[1]].emplace_back(e[0], e[2]);
}
vector<int> dist(n, INT_MAX);
vector<bool> inQueue(n, false);
vector<int> count(n, 0);
queue<int> que {{start}};
dist[start] = 0;
while (!que.empty()) {
int u = que.front(); que.pop();
inQueue[u] = false;
for (const auto& [v, w] : graph[u]) {
if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
++count[v];
if (count[v] > n - 1) {
cout << "存在负权回路!" << endl;
return;
}
if (!inQueue[v]) { // 若v已在队列中, 只需更新dist[v]即可, 无需重复入队.
que.emplace(v);
inQueue[v] = true;
}
}
}
}
cout << "成功得到从起点到各顶点的最短距离dist" << endl;
}
```
%%
## Floyd 算法
> 算法功能：**带权图的多源最短路径**
Floyd 算法的核心是 "**动态规划**"。
#TODO
二维矩阵 `dist[i][j][k]` 记录表示从**顶点 i 到顶点 j** ，**以 ==前 k 个顶点 `[0,k-1]` 中某顶点为中转点==时的最短距离**
```cpp
dist[i][j][k] = dist[i][j][k-1], dist[i][n]
```
### Floyd 算法复杂度分析
- 时间复杂度：$O(|N|^3)$，**只取决于顶点 $N$ 的数量**。
- 空间复杂度：$O(|N|^3)$，三维 dp 数组的开销；
> [!NOTE] 如果是**稀疏图**，**顶点多而边少**，可考虑**依次==以各个顶点为起点多次应用 dijsktra==**，时间复杂度为 $|N|*|E|\log |E|$。
%%
<br><br><br>
# 最小生成树
给定**无向加权连通图**，找到**一棵包含图上所有顶点、且==树上所有边的权重之和最小==的生成树**。
> [!NOTE] 当图上**存在权重相同的边**时，最小生成树可能不唯一。
> [!NOTE] 图中边的权值可以为 0 或者为负, 不影响求解;
#### 最小生成树的求解算法
有两种算法：**Kruskal 算法**、**Prim 算法**
| | 时间复杂度 | 空间复杂度 |
| ---------- | ---------------------------------------------- | -------------------- |
| Prim 算法 | $O(E\log E)$ （延迟删除堆中无效边） | $O(E)$ （堆中最多 $E$ 条边） |
| Kruskal 算法 | $O(E\log E+E\cdot\alpha(V))$（需要对所有边排序 & 并查集开销） | $O(V)$ （并查集所需空间） |
> [!danger] Kruskal 算法、Prim 算法不能处理 "**==有向图==**"
>
> - 对于 Prim 算法：**边的有向性会导致无法遍历整个图**，例如图 `1->2->3`，**如果以 `2` 为起点，将无法得到边 `1->2`**。
> - 对于 Kruskal 算法：有向图没有 "**连通分量**" 的概念，`A->B` 不等于 `B->A`，故**并查集的 "连通/合并" 判断是否成环的逻辑不适用**。
> - ![[Excalidraw-Solution/图相关算法_1.excalidraw|500]]
>
> [!note] 当图 "不连通" 时的处理结果（即图中存在多个孤立的连通分量）
>
> - 对于 Prim 算法：其是从某一顶点起始进行扩展，故将得到 **起始顶点所在连通分量的最小生成树**。
> - 对于 Kruskal 算法：将为 **图上所有连通分量** 分别得到 "**==各自的最小生成树==**"。
<br><br>
## Prim 算法
核心思想：每一步**找出 "==连接到当前生成树中顶点==" 的最小权重边**，逐步生成 "**生成树**"。
过程：
1. 从**任一顶点**开始，初始时**生成树中只有该顶点**。
2. 每一步中，找出连接 "**==生成树中顶点==**" 与 "**==树外顶点==**" 的 **==最小权重的边==**，将该**边**以及**边所连的树外顶点**，**加入生成树中**。
3. 重复第二步，直至：
- **所有顶点都已加入到生成树**。 => 得到有效的 MST
- 或者没有与生成树相连的**横切边**。 => 图不连通，图上存在多个孤立的连通分量
> [!info] 横切边：连接 "**生成树上顶点**" 与 "**树外顶点**" 的边[^3]
### 实现
求给定无环连通图中**最小生成树的权重**：
```cpp
// Prime算法
int MST_Weight_By_Prime(int n, vector<vector<int>>& edges) {
using PII = pair<int, int>;
vector<vector<PII>> graph(n + 1);
for (const auto& e : edges) {
graph[e[0]].emplace_back(e[1], e[2]);
graph[e[1]].emplace_back(e[0], e[2]);
}
unordered_set<int> MST; // 记录已添加到生成树中的顶点.
priority_queue<PII, vector<PII>, greater<>> min_pq; // 小顶堆中存储连接到当前生成树的横切边: `{边权, 边另一端连接的树外顶点}`.
vector<int> min_weight(n + 1, INT_MAX); // 记录与树外顶点关联的、已出现的最小权重边`(parent[i], i, w)`
// 注: min_weight[i]记录的是算法过程中, 将顶点i作为"树外顶点"连接的边中, 权值最小的. 用于优化算法效率, 过滤非最小权值的边.
min_pq.push({0, 1});
min_weight[0] = 0;
int weight = 0;
// 每次取出连接"树中顶点"与"树外顶点", 且权重最小的一条边, 加入树中.
while (MST.size() < n && !min_pq.empty()) {
auto [w, u] = min_pq.top(); min_pq.pop();
if (MST.count(u)) continue;
MST.insert(u);
weight += w;
for (const auto& [v, ew] : graph[u]) {
if (MST.count(v) || ew > min_weight[v]) continue; // 顶点v已在树中, 或者该边不是连接树外顶点v的最小权重边.
min_weight[v] = ew; // 只将与关联树外顶点v的关联, 且权值最小的边入堆, 作为候选.
min_pq.emplace(ew, v);
}
}
return MST.size() == n ? weight : -1;
}
```
求给定无环连通图中**最小生成树的边集**：
```cpp
// Prim算法
int MST_Egdes_By_Prim(int n, vector<vector<int>>& edges) {
using PII = pair<int, int>;
vector<vector<PII>> graph(n + 1);
for (const auto& e : edges) {
graph[e[0]].emplace_back(e[1], e[2]);
graph[e[1]].emplace_back(e[0], e[2]);
}
unordered_set<int> MST; // 记录已添加到最小生成树中的顶点.
vector<vector<int>> MST_edges; // 记录最小生成树中的边. `{u, v, w}`
using T = tuple<int, int, int>;
priority_queue<T, vector<T>, greater<>> min_pq; // 小顶堆中存储连接到当前生成树的横切边: `{边权, 树外顶点, 生成树内的顶点}`,
vector<int> min_weight(n + 1, INT_MAX); // 记录与树外顶点关联的最小权重边.
min_pq.push({0, 1, 1}); // 初始顶点1 即树外顶点.
int weight = 0;
// 每次取出连接"树中顶点"与"树外顶点", 且权重最小的一条边, 加入树中.
while (MST.size() < n && !min_pq.empty()) {
auto [w, u, s] = min_pq.top(); min_pq.pop(); // s是树中顶点, u应是树外顶点
if (MST.count(u)) continue; // 失效边
if (u != s) {
MST_edges.push_back({s, u, w}); // 加入MST边集中.
}
MST.insert(u);
weight += w;
// 只更新min_weight，如果找到更小的权重边
for (const auto& [v, ew] : graph[u]) {
if (MST.count(v) || ew >= min_weight[v]) continue; // 顶点已在树中, 或者该边不是连接树外顶点v的最小权重边.
min_weight[v] = ew;
min_pq.emplace(ew, v, u);
}
}
return MST_edges;
}
```
<br><br>
## Kruskal 算法
核心思想：**对边集==按权重升序排序==**，每次取出一条 **==权重最小==**、且不**会与生成树中已有边构成 "环"** 的边，加入生成树中。
算法过程：
1. **对边集==按权重升序排序==**；
2. 初始化一个 "**并查集**" 结构，用于**判断两顶点是否连通**。
3. **逐条处理按权重升序排列的边**：
- 若边的 **==两顶点尚未连通==**，则**将边加入生成树中**，标记两顶点已连通。
- 否则，意味着加入后将形成环，跳过。
4. 重复步骤三，直至：
- **生成树中已有 n-1 条边** => 得到**有效的最小生成树**，n 是顶点数
- 或者，边集已被遍历完 => 说明**图不连通，存在多个独立的连通分量**
> [!NOTE] 利用 "并查集" 高效判断 "**两个顶点是否已连通**"。
>
> ![[Excalidraw-Solution/图相关算法_0.excalidraw|750]]
### 实现
求给定无环连通图中**最小生成树的权重 & 边集**
```cpp
class MinimumSpanningTree {
public:
// 并查集
class UnionFind {
private:
vector<size_t> parent;
vector<size_t> rank;
public:
UnionFind(size_t n) : parent(n), rank(n, 1) {
iota(parent.begin(), parent.end(), 0);
};
size_t find(size_t x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩
}
return parent[x];
}
void unite(size_t x, size_t y) {
x = find(x), y = find(y);
if (x == y) return;
if (rank[x] < rank[y]) swap(x, y);
parent[y] = x;
++rank[y];
}
bool connected(size_t x, size_t y) {
return find(x) == find(y);
}
};
// Kruskal会为图中每个"独立"的连通分量, 分别求得"最小生成树".
void get_MST(int n, vector<vector<int>>& edges) {
// 1.对边集按权重升序排列
sort(edges.begin(), edges.end(), [](const auto& vec1, const auto& vec2) -> bool {
return vec1[2] < vec2[2];
});
// 2.初始化并查集, 用于判断两顶点是否连通.
UnionFind uf(n);
vector<vector<int>> MST_edges; // 记录最小生成树中的边.
int weight = 0;
int components = n; // 记录连通分量数量. 初始时每个顶点独立
// 3. 每次取出权重最小, 且加入后不会令生成树成环的边加入生成树中.
for (const auto& e : edges) {
int u = e[0], v = e[1], w = e[2];
if (!uf.connected(u, v)) { // 顶点u,v尚未连通, 可加入边u-v.
uf.unite(u, v);
weight += w;
MST_edges.emplace_back(e);
--components;
if (MST_edges.size() == n -1) break; // 边数足够, 统计完成
// 或者if (components == 1) break;
}
}
if (MST_edges.size() == n - 1) { // 边数为n-1, 得到有效的最小生成树.
cout << "最小生成树权重: " << weight << endl;
} else {
cout << "图中存在多个孤立的连通分量, 共 " << components << " 个" << endl;
}
}
};
```
<br><br>
# 拓扑排序
> 下图参见 [^2]
![[_attachment/00-数据结构与算法笔记/数据结构/图相关算法.assets/IMG-图相关算法-F9F4D205FBF4B478722B94C7AB354498.png|656]]
> [!info] **拓扑排序的结果不唯一**，**只要排序结果保证==对于任意一条有向边 `u->v`==，==顶点 u 都排在顶点 v 之前==即是正确的**。
> [!NOTE] 拓扑排序
>
> 步骤如下：
>
> 1. 将所有 "**入度为 0 的顶点**" 加入队列；
> 2. 每**出队一个顶点**，将该顶点所**指向的邻居节点 "==入度减 1=="**，**若邻居节点==入度减为了 0==，则将邻居节点入队**。
> 3. 重复上述过程，直至队列为空。
>
> 若最后 **==所有顶点的入度均为 0==**，则**存在有效的拓扑排序**，**"==各顶点入度变为 0 的顺序==" 即为拓扑排序顺序**。
> 否则意味着 **==有向图中有环==**。 ^a1kq8q
> [!info] 拓扑排序的开销
>
> - 时间复杂度：$O(|V|+|E|)$。从图中入度为 0 的顶点起，图中**每个顶点都会入队/出队一次**，然后 **==列举各顶点的每条边==**，故**每条边也被访问一次**。
> - 空间复杂度：$O(|V|)$，队列本身最多存 $|V|$ 个顶点，但构图（如邻接表） 需要 $O(|V|+|E|)$。
算法实现示例：
```cpp
// 拓扑排序(有向图), 返回拓扑排序的结果.
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
int& n = numCourses;
vector<vector<int>> graph(n);
vector<int> degree(n);
for (const auto& e : prerequisites) {
graph[e[1]].push_back(e[0]);
++degree[e[0]];
}
vector<int> ans;
queue<int> que;
for (int i = 0; i < n; ++i) {
if (degree[i] == 0) {
que.push(i);
ans.push_back(i);
}
}
while (!que.empty()) {
int u = que.front(); que.pop();
for (int v : graph[u]) {
--degree[v];
if (!degree[v]) {
que.push(v);
ans.push_back(v);
}
}
}
if (ans.size() != n) return {};
return ans;
}
```
<br><br><br>
# 参考资料
# Footnotes
[^1]: [最短路径四种算法——总结篇](https://blog.csdn.net/qq_44691917/article/details/104616471)
[^2]: [leetcode.cn/circle/discuss/01LUak/](https://leetcode.cn/circle/discuss/01LUak/)
[^3]: 《算法（第四版）》P391