Kruskal 算法

Kruskal 是用来求解最大/小生成树的算法。

一棵树可以被理解为 $n$ 个结点，$n-1$ 条边的连通图。

断开 $k$ 条边，树会被分为 $k+1$ 个连通块。

• 生成树：从一张 $n$ 个点 $m$ 条边的图中选出 $n-1$ 条边，构成一棵树。
• 最小生成树：边权和最小的生成树。
• 最大生成树：边权和最大的生成树。

反向考虑一棵树的构建过程。

一开始是 $n$ 个独立的联通块，每增加一条边，减少一个联通块。

直到选出 $n-1$ 条边，构造完成。

使用并查集维护联通块。

考虑最小生成树的构造过程，即选出 $n-1$ 条边的顺序。

有一个贪心策略，按照边权升序排序，依次考虑是否选取。

如果两个端点 $u,v$ 在一个联通块里，不选。否则选。

1. 建立并查集。
2. 按照边权排序，依次扫描每条边。
3. 如果 $u,v$ 属于同一连通块，则忽略，扫描下一条。否则选择这条边，合并两个并查集。

时间复杂度为 $\Theta(m \log m)$。

例题：【模板】最小生成树

给出一个 $n$ 个点，$m$ 条边的无向图，判断其是否为联通图，并求出其最小生成树。

Dijkstra 算法

Dijkstra 算法是一种用于求解单源最短路问题的算法。

设 $S$ 为起点，$dis_x$ 为 $x$ 到 $S$ 的最短距离。

流程如下：

1. 初始化 $dis_S$ 为 $0$，$dis$ 的其他位置为 $+\infty$。
2. 在未被标记点中找到的 $dis_x$ 最小的 $x$，并标记结点 $x$。
3. 扫描 $x$ 的所有出边 $(x,y,z)$ $^{[1]}$，如果 $dis_y>dis_x+z$，则更新 $dis_y$。
4. 重复步骤 $2 \sim 3$，直至所有结点被标记。

Dijkstra 只能处理非负边权的图。

其思想基于贪心：当边长为非负数，全局最小值必然不可能再被更新。

即，每次在第二步中取出的 $x$，$dis_x$ 已经是起点到 $x$ 的最短路径。

Dijkstra 的时间复杂度是 $\Theta(n^2)$。

其时间复杂度瓶颈为寻找结点 $x$，这个过程可以用优先队列 priority_queue 优化。

优化后均摊时间复杂度为 $\Theta(n \log n)$。

• pair <type,type>
• 优先以第一关键字比大小，第一关键字相同按第二关键字比。
• make_pair(a,b)，得到一个以 $a$ 为第一关键字，$b$ 为第二关键字的 pair。

例题：【模板】单源最短路径（标准版）

给出一个 $n$ 个点 $m$ 条边的有向图，求从 $s$ 出发到每个点的最短距离。

$n \le 10^5,m \le 2 \times 10^5,w_i \le 10^9,\sum w_i \le 10^9$

$^{[1]}$ $x$ 为该边起点，$y$ 为该边终点，$z$ 为该边长度。

Floyd 算法

Floyd 算法是用来求解全源最短路的算法，其基于动态规划思想。

使用邻接矩阵存储图。

设 $D_{k,i,j}$ 为经过若干个编号不超过 $k$ 的结点从 $i$ 到 $j$ 的最短路长度。

有两种转移来源：

• 经过若干个编号不超过 $k-1$ 的结点从 $i$ 到 $j$。
• 从 $i$ 到 $k$ 再到 $j$。

即有 $D_{k,i,j}=\min\{D_{k-1,i,j},D_{k-1,i,k}+D_{k-1,k,j}\}$。

类似于背包问题，第一维 $k$ 可以省略。

即有 $D_{i,j}=\min\{D_{i,j},D_{i,k}+D_{k,j}\}$。

由于动态规划的有序性，需要先枚举阶段转移点 $k$，再枚举 $i$ 和 $j$。

最终 $D_{i,j}$ 即为 $i$ 到 $j$ 的最短距离。

Floyd 算法的时间复杂度为 $\Theta(n^3)$。

全源最短路问题也可以通过做 $n$ 次 Dijkstra 在 $\Theta(n^2 \log n)$ 的时间复杂度内完成。

例题：【模板】Floyd 算法

给出一个 $n$ 个点 $m$ 条边的无向图，求任意两点间最短路径。

$n \le 100,m \le 4500,w_i \le 1000$