【算法基础实验】图论-最小生成树Kruskal实现

预备知识

【算法基础实验】图论-UnionFind连通性检测之quick-union_union find 判断是否成环-CSDN博客

【算法基础实验】排序-最小优先队列MinPQ_最小优先队列实现-CSDN博客

理论知识

Kruskal算法是一种用于查找加权无向图的最小生成树的贪心算法。最小生成树是一个连通的子图，它包含所有顶点，并使得所有边的权重之和最小。Kruskal算法的核心思想是：

边排序：首先将图中的所有边按权重从小到大排序。
边选择：从权重最小的边开始，依次选择边加入到生成树中，但要确保不会形成环。
循环停止：直到树中包含 V-1 条边（其中 V 是图中的顶点数）时，算法停止。

Kruskal算法的主要步骤涉及使用并查集（Union-Find）来检测是否形成环。并查集有效地管理和合并不同的连通分量，并检查两个顶点是否已经在同一个连通分量中。

Kruskal 算法的时间复杂度

Kruskal算法的时间复杂度主要取决于边的排序和并查集操作：

排序：O(E log E)，其中 E 是边的数量。
Union-Find 操作：每次操作的时间复杂度接近 O(1)，总体复杂度为 O(E log V)。

Prim 算法是一条边一条边地来构造最小生成树，每一步都为一棵树添加一条边。Kruskal 算法构造最小生成树的时候也是一条边一条边地构造，但不同的是它寻找的边会连接一片森林中的两棵树。我们从一片由棵单顶点的树构成的森林开始并不断将两棵树合并（用可以找到的最短边）直到只剩下一棵树，它就是最小生成树。

实验数据

算法流程

在这里插入图片描述

代码实现

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;public class myKruskalMST {private myLinkedQueue<myEdge> mst;private double totalWeight;public myKruskalMST(myEdgeWeightedGraph G){mst = new myLinkedQueue<myEdge>();myMinPQ<myEdge> pq = new myMinPQ<myEdge>();for(myEdge e:G.edges()) pq.insert(e);myQuickUnion uf = new myQuickUnion(G.V());while(!pq.isEmpty() && mst.size()<G.V()-1){myEdge e = pq.delMin();int v=e.either(),w=e.other(v);if(uf.connected(v,w)) continue;uf.union(v,w);mst.enqueue(e);}}public Iterable<myEdge> edges(){ return mst; }public double weight(){totalWeight = 0.0;for(myEdge e:edges())totalWeight += e.weight();return totalWeight;}public static void main(String[] args){In in = new In(args[0]);myEdgeWeightedGraph G = new myEdgeWeightedGraph(in);myKruskalMST mst = new myKruskalMST(G);for(myEdge e:mst.edges())StdOut.println(e);StdOut.printf("%.5f\n", mst.weight());}
}

代码详解

这段代码实现了 Kruskal 算法来求解最小生成树。以下是对代码各部分的详细解释：

类变量和构造函数

java复制代码
private myLinkedQueue<myEdge> mst; // 用于存储最小生成树的边
private double totalWeight; // 最小生成树的总权重public myKruskalMST(myEdgeWeightedGraph G) {mst = new myLinkedQueue<myEdge>();myMinPQ<myEdge> pq = new myMinPQ<myEdge>();for (myEdge e : G.edges()) pq.insert(e);myQuickUnion uf = new myQuickUnion(G.V());while (!pq.isEmpty() && mst.size() < G.V() - 1) {myEdge e = pq.delMin();int v = e.either(), w = e.other(v);if (uf.connected(v, w)) continue;uf.union(v, w);mst.enqueue(e);}
}

mst：使用 myLinkedQueue 存储 Kruskal 算法中选择的边，即最小生成树的边。
totalWeight：记录最小生成树的总权重。
构造函数：
- 初始化 mst 队列，用于保存最终的最小生成树的边。
- 使用 myMinPQ（最小优先队列）来存储和排序图中的边。
- 将图 G 中的所有边插入优先队列 pq 中。
- 使用 myQuickUnion 实现并查集，以检测并合并连通分量。
- 通过一个 while 循环，不断从 pq 中取出权重最小的边，并检查是否形成环。如果不会形成环，则将边加入 mst 队列。

辅助方法：edges() 和 weight()

java复制代码
public Iterable<myEdge> edges() {return mst;
}public double weight() {totalWeight = 0.0;for (myEdge e : edges())totalWeight += e.weight();return totalWeight;
}

edges()：返回最小生成树中的所有边。
weight()：计算并返回最小生成树的总权重。

main方法

java复制代码
public static void main(String[] args) {In in = new In(args[0]);myEdgeWeightedGraph G = new myEdgeWeightedGraph(in);myKruskalMST mst = new myKruskalMST(G);for (myEdge e : mst.edges())StdOut.println(e);StdOut.printf("%.5f\n", mst.weight());
}

main()：从输入文件读取加权无向图数据，构造 myEdgeWeightedGraph 对象 G。
- 调用 myKruskalMST 类生成最小生成树。
- 打印最小生成树的边和总权重。

总结

Kruskal 算法通过从权重最小的边开始逐步构建最小生成树。使用并查集来管理连通分量，有效避免形成环。在这段代码中，Kruskal 算法以 myKruskalMST 类实现，使用优先队列 myMinPQ 来处理边的排序，并使用 myQuickUnion 来实现并查集操作。最终，代码输出了最小生成树中的边及其总权重。

实验步骤

C:\Users\xyz\IdeaProjects\algrithoms\src>javac myKruskalMST.java             C:\Users\xyz\IdeaProjects\algrithoms\src>java myKruskalMST data\tinyEWG.txt  
0-7 0.16
2-3 0.17
1-7 0.19
0-2 0.26
5-7 0.28
4-5 0.35
6-2 0.40
1.81000