的应用—最小生成树

连通图的生成树定义：

连通图的生成树是一个极小的连通子图，它含有图中全部的 n个顶点 ，但只足已构成一棵树的 n-1条边 。

把构成联通网的最小代价的生成树成为最小生成树。

图中粗线部分，便是联通了全部顶点代价最小的生成树。

那如何构建一个最小生成树？

从一个顶点V0开始，不断选取未遍历的边中权值最小的边。

注意:

更新lowcost 数组与adjvex 数组的条件:

创建一个图：

最小生成树：

测试：

全局贪婪最小权值的边(通过排序)，同时防止形成环。

如何防止形成环：

1: 通过一个数组，记录边的开头和结尾沿着路径到达尾部的时候的顶点。

2: 遍历边，判断边的开头和结尾沿着路径到达尾部的时候，是否会来到同一个顶点。

3: 如果来到同一个顶点，说明形成环。

4: 如果来到了不同的顶点，说明没有形成环。

遍历越靠后，n = m 的几率越来越大，后入树的顶点很容易与之前的顶点形成闭环。

边表数组结构，使用上边创建的邻接矩阵的图。

kruskal算法实现：

测试：

get：parent数组+Find函数，防止了图中新加入的顶点与已加入的顶点形成闭环。

普里姆算法构造最小生成树算法的思想是：选择一个结点，然后从这个结点开始，选择权值最小的边，用一条边连接，然后再以前面的那个结点开始，和你连接的那个结点作为根节点，再选择权值最小的边进行连接。

对权值给出解释：以上图为例，权值就是你第一个图那几条边（弧）上，所标的数字。

对楼主所提出的问题：并不是连接那圆圈中最小的圆圈，如果没错的话，那圆圈中的数字表示的是V1---V6六个顶点，并不是代表数字，以3和6为顶点，找权值最小边，显然6——4为最小，即权值为2，顶点364相连接的时候各以364为顶点寻找最小边，应该先从6连接到2，那么现在加入顶点的为3642顶点，现在以3642为顶点寻找最小边，应该从2连接到1，现在被连接的有63421，在以63421为顶点寻找最小边

出现了问题：如果以5为权值的话，无论从2连接到4还是从3连接到4都出现了环，当然我们知道数中是不能出现环的，所以寻找次小的，剩余5与13之间权值最小为13.所以将1连接5，即得到最小生成树。

楼主可以按照我说的在纸上画一下试试

从6连接到3因为有前提条件：从顶点V3开始用普里姆方法求其最小生成数，可见是从顶点3连接到6，而不是从6连接到3

希望可以解决楼主的疑惑，谢谢！

本文来自作者[第五俊俊]投稿，不代表巨商报立场，如若转载，请注明出处：https://91zxpc.com/zx/2064.html