（原创）最小生成树之Prim（普里姆）算法+代码详解，最懂你的讲解

冷不防 2022-01-07 10:53 150阅读 0赞

# Prim算法 #

（哈欠）在创建最小生成树之前，让我们回忆一下什么是最小生成树。最小生成树即在一个待权值的图（即网结构）中用一个七拐八绕的折线串连起所有的点，最小嘛，顾名思义，要权值相加起来最小，你当然可以拿起笔来就算你脑中的每一种可能，但是如果你了解了这种算法，你就能跟我一样，一次画出完美答案。

## 上个栗子： ##

![1598426-20190209151948466-1317742710.png][]

我先说一哈这个算法的方法论，然后我们来代码实现一下，在讲解开始之前，敲黑板，记得我们要生成一个权值最小的树，所以每一步都要考虑到树的每一个结点，不要孤立地用一个结点来对比从而走上死路，我们任选一个点开始生成，教材里选的 v0，那我们就选 v8，战斗开始

v8 有三条路，分别通往v1 v2 v3，v2那条路权值最小，ok， v2→v8，然后我们该看什么，如果你说找和 v2 相邻的 v8 以外的边，那我刚才的强调就gg了，我们找v2 和 v8除相连的线之外的所有分支，易得 v8→v1的权值最小，ok，下一步找哪几个点？v2 v1 v8这三个点除两条连接线以外的所有分支，挑最小的那一条，后面重复前面的操作，每次都把新加入的伙伴算在找线之内才对，自己画一下给答案：

![1598426-20190209152755118-1545954670.png][]

操作一遍是不是发现还真的跟哪个点开始没鸡儿关系，因为每个点都要连到，关键就在于沿最小分支找点的时候一定要把它看成一个树结构来找，才算是**最小**生成树。

还是给一下标准定义：

## 我们把构造连通网的最小代价（权值）生成树 称为最小生成树 （Minimum Cost Spanning Tree）。 ##

方法论就到这里，相信下一次看到同样的现实问题，你也应该能在第一时间用正确的思路找到合适的路。

在代码实现之前，我们先请来连通图的好基友——邻接矩阵

![1598426-20190209154000243-1162682346.png][]

我们发现一行一行的矩阵很容易显示权值，这样就可以快速对比权值的大小，只要在循环的每一步留存下权值较小的边权值和顶点下标，就可以实现。

和以前一样，我们还是用 INFINITY 来表示无限大，即不存在该边

代码如下：

1 void MiniSpanTree_Prim(MGragh G)
     2 {
     3     int mini,i,j,k;
     4     int adjvex[MAXVEX]; //保存相关顶点下标
     5     int lowcost[MAXVEX]; //保存相关顶点间边的权值
     6     lowcost[0] = 0;//这里把第0位的权值置0表示v0已加入生成树
     7     //ps：lowcost[i] = 0 表示i那个下标的顶点加入生成树
     8     adjvex[0] = 0; //初始化第一个顶点的下标为0
     9     for(i = 0; i < G.numVertexes; i++)
    10     {
    11         lowcost[i] = G.arc[0][i];//将vo相关顶点的权值存入lowcost数组
    12         adjvex[i] = 0;//置所有下标为v0
    13     }
    14     for(i = 1; i < G.numVertexes; i++) //最小生成树开始辽
    15     {
    16         mini = INFITINY; //先把权值的最小值置为无限大
    17         j = 1;
    18         k = 0;
    19         while(j < G.numVertexes)
    20         {
    21             if(lowcost[j] != 0 && lowcost[j] < mini)//判断并向lowcost中添加权值
    22             {
    23                 mini = lowcost[j];
    24                 k = j;
    25             }
    26             j++;
    27         }
    28         printf("(%d %d)",lowcost[k],k);
    29         lowcost[k] = 0;//置0表示这个定点已经完成任务，找到最小权值分支
    30         for(j = 1; j < G.numVertexes; j++)
    31         {
    32             if(lowcost[j] != 0 && G.arc[k][j] < lowcost[j])
    33             {
    34                 lowcost[j] = G.arc[k][j];
    35                 adjvex[j] = k;
    36             }
    37         }
    38     }
    39 }

**简单讲解一哈：**

*  4~5行，先说 adjvex\[\] ，这个数组要解决的问题就是存入已经安排好的那些顶点的下标，什么叫安排好了呢，比如我已经找到了 v0→v1 ，v1 就可以算是安排好了，而v0点置0则算做初始化的操作；再说 lowcost\[\] 这个数组，听名字就是最小权值的意思，下面讲循环的时候详解这个东西到底储存了些什么，然后每次更新之后能做什么
 *  6~13行完全是初始化，要注意的是就是 lowcost\[\] 储存了邻接矩阵 v0 这一行的权值
 *  14~38行是最小生成树的整体代码
 *  16行就是每次都把最小值重置
 *  19~27行，从 1 开始遍历完全，找到现在这个状态下的最小权值数，并且把这个下标用 k 存住，28行就是把权值和下标打印出来，当然也可以换成别的操作，这里不再赘述
 *   然后29行，看看他都干了些什么，它把  adjvex\[ k \] 置0，看一下第一点，这里表示 v1 完成任务，没有利用价值了
 *  然后30~37这个循环，看看循环的条件，条件一：  ** lowcost\[ j \] != 0**  ，这是啥意思，表示在没有完成任务的顶点中选择，条件二： ** G.arc\[k\]\[j\] < lowcost\[j\]   **这表示在刚才找到的新顶点的矩阵那一行去对应，如果有更小的权值就把 lowcost\[\] 更新掉，这样就保证了这个数组中同时存在好几个顶点的权值信息，还是择优录用的，然后返回循环头，再找这次的最小权值点，周而复始。

## 时间复杂度 O（n²） ，没啥问题辽 ##

最后附上过程图：

![1598426-20190209162520461-1583048902.png][]

## 谢谢大嘎 ##

转载于:https://www.cnblogs.com/yx1999/p/10357626.html

[1598426-20190209151948466-1317742710.png]: /images/20211223/86cdaf98e05d4ed5a1ae4188bdea996c.png
[1598426-20190209152755118-1545954670.png]: /images/20211223/106b377b5f514d699ff5279f7236b76d.png
[1598426-20190209154000243-1162682346.png]: /images/20211223/50ef5f90430e43c098c17a0ee575de8b.png
[1598426-20190209162520461-1583048902.png]: /images/20211223/5d173e85292e41afbd8dd6705a8958c8.png