【算法基础实验】图论-最小生成树Prim的延迟实现-易微帮

最小生成树-Prim的延迟实现

理论基础

树的基本性质

用一条边连接树中的任意两个顶点都会产生一个新的环；
从树中删去一条边将会得到两棵独立的树。

切分定理的定义

定义。图的一种切分是将图的所有顶点分为两个非空且不重叠的两个集合。横切边
是一条连接两个属于不同集合的顶点的边。
命题（切分定理）。在一幅加权图中，给定任意的切分，它的横切边中的权重最
小者必然属于图的最小生成树。

切分定理的证明

请添加图片描述

证明。令e为权重最小的横切边,T为图的最小生成树。我们采用反证法：假设T
不包含e。那么如果将e加入T，得到的图必然含有一条经过e的环，且这个环
至少含有另一条横切边——设为f，f的权重必然大于e（因为e的权重是最小的
且图中所有边的权重均不同）。那么我们删掉f而保留e就可以得到一棵权重更
小的生成树。这和我们的假设T矛盾。

实验数据和算法流程

请添加图片描述

代码实现

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.myMinPQ;
import edu.princeton.cs.algs4.StdOut;

public class myLazyPrimMST {

    private boolean[] marked;
    private myLinkedQueue<myEdge> mst;
    private myMinPQ<myEdge> pq;
    private double totalWeight;

    public myLazyPrimMST(myEdgeWeightedGraph G)
    {
        marked = new boolean[G.V()];
        mst = new myLinkedQueue<myEdge>();
        pq = new myMinPQ<myEdge>();

        visit(G,0);

        while(!pq.isEmpty())
        {
            myEdge e = pq.delMin();
            int v=e.either();
            int w=e.other(v);
            if(marked[v]&&marked[w]) continue;
            mst.enqueue(e);
            if(!marked[v]) visit(G,v);
            if(!marked[w]) visit(G,w);
        }
    }

    private void visit(myEdgeWeightedGraph G, int v)
    {
        marked[v] = true;
        for(myEdge e:G.adj(v))
            if(!marked[e.other(v)])
                pq.insert(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);
        myLazyPrimMST mst = new myLazyPrimMST(G);

        for(myEdge e:mst.edges())
            StdOut.println(e);
        StdOut.print(mst.weight());
    }
}

代码详解

这段代码实现了一个名为 myLazyPrimMST 的类，用于计算加权无向图的最小生成树（MST），采用的是 Prim 的延迟算法。下面是代码的主要功能和操作步骤的详细解释：

类变量：
- private boolean[] marked;：标记数组，用于记录图的顶点是否已被访问。
- private myLinkedQueue<myEdge> mst;：用于存储构成最小生成树的边。
- private myMinPQ<myEdge> pq;：优先队列，用于按边的权重顺序访问边。
- private double totalWeight;：记录最小生成树的总权重。
构造函数：
- 在构造最小生成树时，首先初始化标记数组、边队列和优先队列。
- 从顶点0开始访问图，将其相邻的未访问边加入优先队列。
- 循环从优先队列中取出最小边，如果这条边的两个顶点已经被标记，则忽略此边；否则，将其加入到生成树中，并访问相邻的未标记顶点。
访问顶点（visit 方法）：
- 标记顶点为已访问。
- 遍历与顶点相连的所有边，如果边的另一端未被标记，则将该边加入优先队列。
获取生成树的边和权重：
- edges() 方法返回构成最小生成树的边。
- weight() 方法计算最小生成树的总权重，通过遍历所有生成树的边并累加它们的权重。
主函数：
- 从文件读取图的数据构造图对象。
- 创建 myLazyPrimMST 对象来生成最小生成树。
- 输出生成树的所有边和总权重。

通过这种方式，myLazyPrimMST 类使用延迟的 Prim 算法有效地找到了一个给定图的最小生成树，这种算法特别适合处理稀疏图。

实验

代码编译

$ javac myLazyPrimMST.java

代码运行

代码运行输出的是计算得到的最小生成树的所有边，以及最小生成树所有边的总权重

$ java myLazyPrimMST ..\data\tinyEWG.txt
0-7 0.16
1-7 0.19
0-2 0.26
2-3 0.17
5-7 0.28
4-5 0.35
6-2 0.40
1.81

参考资料

算法（第四版）人民邮电出版社

【算法基础实验】图论-最小生成树Prim的延迟实现