第十一章：图论part07
今天在学习prim 和 kruskal的同时，也要清楚这两个算法的区别所在。
prim算法精讲
思路
最小生成树模板题
最小生成树是所有节点的最小连通子图， 即：以最小的成本（边的权值）将图中所有节点链接到一起。
图中有n个节点，那么一定可以用 n - 1 条边将所有节点连接到一起。
那么如何选择 这 n-1 条边 就是 最小生成树算法的任务所在。prim算法 是从节点的角度 采用贪心的策略 每次寻找距离 最小生成树最近的节点 并加入到最小生成树中。
prim算法核心就是三步：
第一步，选距离生成树最近节点
第二步，最近节点加入生成树
第三步，更新非生成树节点到生成树的距离（即更新minDist数组）minDist数组：minDist数组 用来记录 每一个节点距离最小生成树的最近距离。 理解这一点非常重要，这也是 prim算法最核心要点所在（示例中节点编号是从1开始，minDist数组下标也从 1 开始计数，下标0 就不使用了，这样 下标和节点标号就可以对应上了)
1. 初始状态
minDist 数组 里的数值初始化为 最大数，因为本题 节点距离不会超过 10000，所以 初始化最大数为 10001就可以。
因为现在 还没有最小生成树，默认每个节点距离最小生成树是最大的，这样后面我们在比较的时候，发现更近的距离，才能更新到 minDist 数组上。
如图：
开始构造最小生成树
2
1、prim三部曲，第一步：选距离生成树最近节点
选择距离最小生成树最近的节点，加入到最小生成树，刚开始还没有最小生成树，所以随便选一个节点加入就好（因为每一个节点一定会在最小生成树里，所以随便选一个就好），那我们选择节点1 （符合遍历数组的习惯，第一个遍历的也是节点1）
2、prim三部曲，第二步：最近节点加入生成树
此时 节点1 已经算最小生成树的节点。
3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）
接下来，我们要更新所有节点距离最小生成树的距离，如图：
注意下标0，我们就不管它了，下标 1 与节点 1 对应，这样可以避免大家把节点搞混。
此时所有非生成树的节点距离 最小生成树（节点1）的距离都已经跟新了 。
- 节点2 与 节点1 的距离为1，比原先的 距离值10001小，所以更新minDist[2]。
- 节点3 和 节点1 的距离为1，比原先的 距离值10001小，所以更新minDist[3]。
- 节点5 和 节点1 的距离为2，比原先的 距离值10001小，所以更新minDist[5]。
注意图中标记了 minDist数组里更新的权值，是哪两个节点之间的权值，例如 minDist[2] =1 ，这个 1 是 节点1 与 节点2 之间的连线，清楚这一点对最后我们记录 最小生成树的权值总和很重要。
3
1、prim三部曲，第一步：选距离生成树最近节点
选取一个距离 最小生成树（节点1） 最近的非生成树里的节点，节点2，3，5 距离 最小生成树（节点1） 最近，选节点 2（其实选 节点3或者节点2都可以，距离一样的）加入最小生成树。
2、prim三部曲，第二步：最近节点加入生成树
此时 节点1 和 节点2，已经算最小生成树的节点。
3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）
接下来，我们要更新节点距离最小生成树的距离，如图：
此时所有非生成树的节点距离 最小生成树（节点1、节点2）的距离都已经更新了 。
- 节点3 和 节点2 的距离为2，和原先的距离值1 小，所以不用更新。
- 节点4 和 节点2 的距离为2，比原先的距离值10001小，所以更新minDist[4]。
- 节点5 和 节点2 的距离为10001（不连接），所以不用更新。
- 节点6 和 节点2 的距离为1，比原先的距离值10001小，所以更新minDist[6]。
4
1、prim三部曲，第一步：选距离生成树最近节点
选择一个距离 最小生成树（节点1、节点2） 最近的非生成树里的节点，节点3，6 距离 最小生成树（节点1、节点2） 最近，选节点3 （选节点6也可以，距离一样）加入最小生成树。
2、prim三部曲，第二步：最近节点加入生成树
此时 节点1 、节点2 、节点3 算是最小生成树的节点。
3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）
接下来更新节点距离最小生成树的距离，如图：
所有非生成树的节点距离 最小生成树（节点1、节点2、节点3 ）的距离都已经更新了 。
- 节点 4 和 节点 3的距离为 1，和原先的距离值 2 小，所以更新minDist[3]为1。
因为节点3加入 最小生成树后，非 生成树节点 只有 节点 4 和 节点3是链接的，所以需要重新更新一下 节点4距离最小生成树的距离，其他节点距离最小生成树的距离 都不变。
然后重复这三步，分别把节点4、5、6加入，具体看文章
注意： minDist数组 是记录了 所有非生成树节点距离生成树的最小距离。
所以最后，minDist数组 也就是记录的是最小生成树所有边的权值。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int v = scanner.nextInt(); // 顶点数量
int e = scanner.nextInt(); // 边数量
int x, y, k;
// 初始化图的邻接矩阵，填一个默认最大值，题目描述val最大为10000
int[][] grid = new int[v + 1][v + 1];
for (int i = 1; i <= v; i++) {
Arrays.fill(grid[i], 10001);
}
// 读取每条边的信息，填充邻接矩阵
while (e-- > 0) {
x = scanner.nextInt();
y = scanner.nextInt();
k = scanner.nextInt();
// 因为是双向图，所以两个方向都要填上
grid[x][y] = k;
grid[y][x] = k;
}
// 所有节点到最小生成树的最小距离
int[] minDist = new int[v + 1];
Arrays.fill(minDist, 10001);
// 这个节点是否在树里
boolean[] isInTree = new boolean[v + 1];
// Prim算法：我们只需要循环 v-1 次，建立 v-1 条边，就可以把 v 个节点的图连在一起
for (int i = 1; i < v; i++) {
// 1、Prim三部曲，第一步：选距离生成树最近的节点
int cur = -1; // 选中哪个节点 加入最小生成树
int minVal = Integer.MAX_VALUE;
for (int j = 1; j <= v; j++) { // 1 - v，顶点编号，这里下标从1开始
// 选取最小生成树节点的条件：
// （1）不在最小生成树里
// （2）距离最小生成树最近的节点
if (!isInTree[j] && minDist[j] < minVal) {
minVal = minDist[j];
cur = j;
}
}
// 2、Prim三部曲，第二步：最近节点（cur）加入生成树
isInTree[cur] = true;
// 3、Prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）
for (int j = 1; j <= v; j++) {
// 更新的条件：
// （1）节点是非生成树里的节点
// （2）与cur相连的某节点的权值 比该某节点距离最小生成树的距离小
if (!isInTree[j] && grid[cur][j] < minDist[j]) {
minDist[j] = grid[cur][j];
}
}
}
// 统计结果
int result = 0;
for (int i = 2; i <= v; i++) { // 不计第一个顶点，因为统计的是边的权值，v个节点有 v-1 条边
result += minDist[i];
}
System.out.println(result);
}
}
拓展
上面讲解的是记录了最小生成树 所有边的权值，如果让打印出来 最小生成树的每条边呢？ 或者说 要把这个最小生成树画出来呢？
此时我们就需要把 最小生成树里每一条边记录下来。
此时有两个问题：
1、用什么结构来记录
2、如何记录
如果记录边，其实就是记录两个节点就可以，两个节点连成一条边。
如何记录两个节点呢？
我们使用一维数组就可以记录。 parent[节点编号] = 节点编号， 这样就把一条边记录下来了。（当然如果节点编号非常大，可以考虑使用map）
使用一维数组记录是有向边，不过我们这里不需要记录方向，所以只关注两条边是连接的就行。
根据 minDist数组：选择距离 生成树 最近的节点 加入生成树，那么 minDist数组里记录的其实也是 最小生成树的边的权值。
既然 minDist数组 记录了 最小生成树的边，所以就是在更新 minDist数组 的时候，去更新parent数组来记录一下对应的边即可。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int v = scanner.nextInt(); // 顶点数量
int e = scanner.nextInt(); // 边数量
int x, y, k;
// 初始化图的邻接矩阵，填一个默认最大值，题目描述val最大为10000
int[][] grid = new int[v + 1][v + 1];
for (int i = 1; i <= v; i++) {
Arrays.fill(grid[i], 10001);
}
// 读取每条边的信息，填充邻接矩阵
while (e-- > 0) {
x = scanner.nextInt();
y = scanner.nextInt();
k = scanner.nextInt();
// 因为是双向图，所以两个方向都要填上
grid[x][y] = k;
grid[y][x] = k;
}
int[] minDist = new int[v + 1]; // 所有节点到最小生成树的最小距离
Arrays.fill(minDist, 10001);
boolean[] isInTree = new boolean[v + 1]; // 这个节点是否在树里
int[] parent = new int[v + 1]; // 记录最小生成树的边
Arrays.fill(parent, -1); // 初始化 parent 数组
// Prim算法：我们只需要循环 v-1 次，建立 v-1 条边，就可以把 v 个节点的图连在一起
for (int i = 1; i < v; i++) {
int cur = -1; // 选中哪个节点加入最小生成树
int minVal = Integer.MAX_VALUE;
// 选距离生成树最近的节点
for (int j = 1; j <= v; j++) {
if (!isInTree[j] && minDist[j] < minVal) {
minVal = minDist[j];
cur = j;
}
}
isInTree[cur] = true; // 最近节点（cur）加入生成树
// 更新非生成树节点到生成树的距离（即更新minDist数组）
for (int j = 1; j <= v; j++) {
if (!isInTree[j] && grid[cur][j] < minDist[j]) {
minDist[j] = grid[cur][j];
parent[j] = cur; // 记录最小生成树的边
}
}
}
// 输出最小生成树边的链接情况
for (int i = 1; i <= v; i++) {
if (parent[i] != -1) { // 跳过根节点
System.out.println(i + " -> " + parent[i]);
}
}
}
}
数组指向的顺序很重要。 因为不少录友在这里会写成这样： parent[cur] = j 。
这里估计大家会疑惑了，parent[节点编号A] = 节点编号B， 就表示A 和 B 相连，我们这里就不用在意方向，代码中 为什么 只能 parent[j] = cur 而不能 parent[cur] = j 这么写呢？
如果写成 parent[cur] = j，在 for 循环中，有多个 j 满足要求， 那么 parent[cur] 就会被反复覆盖，因为 cur 是一个固定值。
举个例子，cur = 1， 在 for循环中，可能 就 j = 2， j = 3，j =4 都符合条件，那么本来应该记录 节点1 与 节点 2、节点3、节点4相连的。
如果 parent[cur] = j 这么写，最后更新的逻辑是 parent[1] = 2, parent[1] = 3， parent[1] = 4， 最后只能记录 节点1 与节点 4 相连，其他相连情况都被覆盖了。
如果这么写 parent[j] = cur， 那就是 parent[2] = 1, parent[3] = 1， parent[4] = 1 ，这样 才能完整表示出 节点1 与 其他节点都是链接的，才没有被覆盖。
主要问题也是我们使用了一维数组来记录。
如果是二维数组，来记录两个点链接，例如 parent[节点编号A][节点编号B] = 1 ，parent[节点编号B][节点编号A] = 1，来表示 节点A 与 节点B 相连，那就没有上面说的这个注意事项了，当然这么做的话，就是多开辟的内存空间。
kruskal算法精讲
思路
Kruskal，同样可以求最小生成树。
prim 算法是维护节点的集合，而 Kruskal 是维护边的集合。
kruscal的思路：
- 边的权值排序，因为要优先选最小的边加入到生成树里
- 遍历排序后的边
- 如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
- 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合
具体画图，看代码随想录。
如果将两个节点加入同一个集合，又如何判断两个节点是否在同一个集合呢？
这里就涉及到并查集
并查集主要就两个功能：
- 将两个元素添加到一个集合中
- 判断两个元素在不在同一个集合
import java.util.*;
class Edge {
int l, r, val;
Edge(int l, int r, int val) {
this.l = l;
this.r = r;
this.val = val;
}
}
public class Main {
// 节点数量
static int n = 10001;
// 并查集标记节点关系的数组
static int[] father = new int[n]; // 节点编号是从1开始的，n要大一些
// 并查集初始化
static void init() {
for (int i = 0; i < n; i++) {
father[i] = i;
}
}
// 并查集的查找操作
static int find(int u) {
if (u == father[u]) {
return u;
} else {
father[u] = find(father[u]); // 路径压缩
return father[u];
}
}
// 并查集的加入集合
static void join(int u, int v) {
int rootU = find(u); // 寻找u的根
int rootV = find(v); // 寻找v的根
if (rootU != rootV) { // 如果根不同，则将v的根连接到u的根上
father[rootV] = rootU;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int v = sc.nextInt(); // 顶点数量
int e = sc.nextInt(); // 边数量
List<Edge> edges = new ArrayList<>();
int result_val = 0;
for (int i = 0; i < e; i++) {
int v1 = sc.nextInt();
int v2 = sc.nextInt();
int val = sc.nextInt();
edges.add(new Edge(v1, v2, val));
}
// 执行Kruskal算法
// 按边的权值对边进行从小到大排序
edges.sort(Comparator.comparingInt(edge -> edge.val));
// 并查集初始化
init();
// 从头开始遍历边
for (Edge edge : edges) {
// 并查集，搜出两个节点的祖先
int x = find(edge.l);
int y = find(edge.r);
// 如果祖先不同，则不在同一个集合
if (x != y) {
result_val += edge.val; // 这条边可以作为生成树的边
join(x, y); // 两个节点加入到同一个集合
}
}
System.out.println(result_val);
}
}
拓展一
如果题目要求将最小生成树的边输出的话，应该怎么办呢？
import java.util.*;
class Edge {
int l, r, val;
Edge(int l, int r, int val) {
this.l = l;
this.r = r;
this.val = val;
}
}
public class Main {
static int n = 10001;
static int[] father = new int[n];
// 并查集初始化
static void init() {
for (int i = 0; i < n; i++) {
father[i] = i;
}
}
// 并查集的查找操作
static int find(int u) {
if (u == father[u]) {
return u;
} else {
father[u] = find(father[u]); // 路径压缩
return father[u];
}
}
// 并查集的加入集合
static void join(int u, int v) {
int rootU = find(u); // 寻找u的根
int rootV = find(v); // 寻找v的根
if (rootU != rootV) { // 如果根不同，则将v的根连接到u的根上
father[rootV] = rootU;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int v = sc.nextInt(); // 顶点数量
int e = sc.nextInt(); // 边数量
List<Edge> edges = new ArrayList<>();
int result_val = 0;
// 读取所有的边信息
for (int i = 0; i < e; i++) {
int v1 = sc.nextInt();
int v2 = sc.nextInt();
int val = sc.nextInt();
edges.add(new Edge(v1, v2, val));
}
// 按照边的权值升序排序
edges.sort(Comparator.comparingInt(edge -> edge.val));
List<Edge> result = new ArrayList<>(); // 存储最小生成树的边
// 并查集初始化
init();
// 遍历排序后的边
for (Edge edge : edges) {
int x = find(edge.l);
int y = find(edge.r);
// 如果祖先不同，则不在同一个集合
if (x != y) {
result.add(edge); // 保存最小生成树的边
result_val += edge.val; // 这条边可以作为生成树的边
join(x, y); // 两个节点加入到同一个集合
}
}
// 打印最小生成树的边
for (Edge edge : result) {
System.out.println(edge.l + " - " + edge.r + " : " + edge.val);
}
sc.close();
}
}
代码解析
-
Edge类：- 用于存储每条边的两个节点（
l和r）以及权值（val）。
- 用于存储每条边的两个节点（
-
并查集的操作：
-
init()方法：初始化father数组，每个节点的父节点初始为自身。 -
find(int u)方法：查找节点u的根，并使用路径压缩优化查询。 -
join(int u, int v)方法：将节点u和v合并到同一个集合中。
-
-
Kruskal算法：
- 读取输入的边信息，并将它们存储在
edges列表中。 - 对
edges列表按照边的权值进行排序。 - 遍历排序后的边，并使用并查集检查每条边是否可以加入最小生成树。
- 读取输入的边信息，并将它们存储在
-
记录最小生成树的边：
- 使用
result列表来存储最小生成树中的边。 - 在每次成功加入一条边到生成树时，将该边添加到
result列表中。
- 使用
-
输出最小生成树的边：
- 遍历
result列表，输出每条边的两个节点及其权值，格式为l - r : val。
- 遍历
示例输出
根据题目要求，代码会输出最小生成树中的每条边及其权值。例如：
1 - 2 : 1
1 - 3 : 1
2 - 6 : 1
3 - 4 : 1
4 - 5 : 1
5 - 7 : 1
该 Java 代码实现了 Kruskal 算法，并能够输出最小生成树的所有边和它们的权值。
拓展二
此时我们已经讲完了 Kruskal 和 prim 两个解法来求最小生成树。
什么情况用哪个算法更合适呢。
Kruskal 与 prim 的关键区别在于，prim维护的是节点的集合，而 Kruskal 维护的是边的集合。 如果 一个图中，节点多，但边相对较少，那么使用Kruskal 更优。
所以在 稀疏图中，用Kruskal更优。 在稠密图中，用prim算法更优。
边数量较少为稀疏图，接近或等于完全图（所有节点皆相连）为稠密图
Prim 算法 时间复杂度为 O(n^2)，其中 n 为节点数量，它的运行效率和图中边树无关，适用稠密图。
Kruskal算法 时间复杂度 为 nlogn，其中n 为边的数量，适用稀疏图。
