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

预备知识

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

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

理论知识

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

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

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

Kruskal 算法的时间复杂度

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

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

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

实验数据

816450.35470.37570.28070.16150.32040.38230.17170.19020.26120.36130.29270.34620.40360.52600.58640.93

算法流程

代码实现

importedu.princeton.cs.algs4.In;importedu.princeton.cs.algs4.StdOut;publicclass myKruskalMST {private myLinkedQueue<myEdge> mst;privatedouble totalWeight;publicmyKruskalMST(myEdgeWeightedGraph G){
        mst =new myLinkedQueue<myEdge>();
        myMinPQ<myEdge> pq =new myMinPQ<myEdge>();for(myEdge e:G.edges()) pq.insert(e);
        myQuickUnion uf =newmyQuickUnion(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);}}publicIterable<myEdge>edges(){return mst;}publicdoubleweight(){
        totalWeight =0.0;for(myEdge e:edges())
            totalWeight += e.weight();return totalWeight;}publicstaticvoidmain(String[] args){In in =newIn(args[0]);
        myEdgeWeightedGraph G=newmyEdgeWeightedGraph(in);
        myKruskalMST mst =newmyKruskalMST(G);for(myEdge e:mst.edges())StdOut.println(e);StdOut.printf("%.5f\n", mst.weight());}}

代码详解

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

类变量和构造函数

java复制代码
private myLinkedQueue<myEdge> mst;// 用于存储最小生成树的边privatedouble totalWeight;// 最小生成树的总权重publicmyKruskalMST(myEdgeWeightedGraph G){
    mst =new myLinkedQueue<myEdge>();
    myMinPQ<myEdge> pq =new myMinPQ<myEdge>();for(myEdge e :G.edges()) pq.insert(e);
    myQuickUnion uf =newmyQuickUnion(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复制代码
publicIterable<myEdge>edges(){return mst;}publicdoubleweight(){
    totalWeight =0.0;for(myEdge e :edges())
        totalWeight += e.weight();return totalWeight;}

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

main方法

java复制代码
publicstaticvoidmain(String[] args){In in =newIn(args[0]);
    myEdgeWeightedGraph G=newmyEdgeWeightedGraph(in);
    myKruskalMST mst =newmyKruskalMST(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-70.162-30.171-70.190-20.265-70.284-50.356-20.401.81000