【数据结构】最小生成树之普利姆算法

亦凉 2022-10-02 12:51 183阅读 0赞

## 基本概念 ##

假设要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，自然会考虑如何在最省经费的前提下完成任务。

在一个**连通网**的所有生成树中，各边的代价之和最小的那棵生成树称为该连通网的**最小生成树**。

**MST性质**：最小生成树中必定存在一条具有最小权值的边。**普利姆(Prim)算法**和**克鲁斯卡尔(Kruskal)算法**是两个利用MST性质构成最小生成树的算法。

普利姆算法的核心思想是归并点，时间复杂度为O(n²)，适用于稠密网；

克鲁斯卡尔算法的核心思想是归并边，时间复杂度为O(elog2e)，使用与稀疏网。

## 普利姆算法（加点法） ##

**<逻辑思路>**

（1）设所有顶点保存在**集合V**中，已**被归并的点**保存在**集合U**中，则未被归并的点保存在**集合V-U**中；

（2）在图中任意找一个**起始顶点v1**，v1归入U，离开V-U；

（3）顶点v1存在v2，v3，v4三个邻接顶点，找出权值最小的边(v1,v3)；

（4）顶点v3归入U，离开V-U；

（5）顶点v1剩余邻接顶点v2，v4，顶点v3有邻接顶点v2，v4，v5，v6；

（6）比较(v1,v2)和(v3,v2)，得出权值更小边(v3,v2)；比较(v1,v4)和(v3,v4)，两边权值相同；

\*在逻辑思路中，其实第(6)步可以省略，直接比较所有边的权值，再从中选择权值最小的边。但代码实现中，应该避免数据冗余，先筛选部分意义重合的数据。

（7）比较(v3,v2)，(v1,v4)或(v3,v4)，(v3,v5)，(v3,v6)，找出权值最小的边(v3,v6)；

（8）顶点v6归入U，离开V-U；

（9）顶点v1剩余邻接顶点v4（因为(v3,v2)的权值更小，所以不再需要考虑v1到v2的情况），顶点v3剩余邻接顶点v2，v4，v5，顶点v6有邻接顶点v4，v5；

（10）到这里思路应该清晰了。

**<实现思路>——以邻接矩阵为存储结构的无向网**

（1）顶点集合为**V**等价于**邻接矩阵图**中用于存储顶点信息的**一维数组vexs\[vexnum\]**；

（2）算法**最巧妙**的地方——**结构体数组closedge\[vexnum\]**，包含信息：**最小边在集合U中的那个顶点**（adjvex）和**最小边的权值**（lowcost）。

结构体数组closedge\[\]的使用正是<逻辑思路>中步骤(6)的体现。

closedge\[vi-1\]表示顶点vi，当lowcast不为0时，vi在集合V-U中；**当lowcast记为0时，vi归并到集合U中**；

（3）**循环执行某一段代码，直至closedge\[\]中所有元素的lowcast属性都归0，即所有顶点都并入到集合U中。**

（看代码前可以先回顾下[“邻接矩阵”][Link 1]的知识）

typedef struct                        /*定义结构体数组closedge[vexnum]*/
    {
        Vextype adjvex;
        Arctype lowcast;
    } closedge[vexnum];
        
    
    void MiniSpanTree_Prim(AMGraph G, Vextype vi)
    {
        int i = LocateVex(G, vi);         /*确定起始顶点vi的编号*/
    
        closedge[i] = {NULL, 0};          /*将vi归并到集合U中*/
        
        for(int vj = 1; vj <= G.vexnum; vj++)    /*对于V-U中的每个顶点vj，初始化closedge[vj-1]*/
        {
            int j = LocateVex(G, vj);
    
            if(j != i) closedge[j] = {vi, G.arcs[i][j]};
        }
    
        for(int k = 1; k < G.vexnum; k ++)       /*直到所有顶点归并到集合U前，循环执行某一段代码*/
        {
            i = Min(closedge);            /*函数Min()找出closedge[]中lowcast最小的元素，并返回下标i*/
                                          /*即找出权值最小的边，并找出位于V-U中的顶点vj*/
        closedge[i].lowcast = 0;          /*将顶点vj归并到集合U中*/
    
        u0 = closedge[i].adjvex           /*u0为最小边在U中的点*/
        v0 = G.vexs[i];                   /*v0为最小边在V-U中的点*/
        cout<<u0<<v0;                     /*输出u0,v0以记录路线*/
    
        for(int j = 0; j < G.vexnum; j++)
        {
            /*之前对closedge[]的元素进行过初始化，并入新的点后要重新选出权值更小的边，对应<逻辑思路>的步骤(6)*/
            if(G.arcs[i][j] < closedge[j].lowcast)    
                closedge[j] = {G.vexs[i], G.arcs[i][j]};  
        }
    }

[Link 1]: https://blog.csdn.net/Ha1f_Awake/article/details/84383923#t3