【prim算法生成最小生成树 最小生成树prim算法流程图】
最小生成树 假设你是电信的实施工程师，需要为一个镇的九个村庄架设通信网络做设计，村庄位置大致如图，其中V0~V8是村庄，之间连线代表可达距离，数字代表里程数 。领导要求你用最小成本完成这次任务，如何做？
显然这是一个带权值的图，即是网结构 。所谓最小成本，就是n个顶点，用n-1条边把一个连通图连接起来，并使得权值和最小 。
定义 一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一个树的n-1条边——我们把构造连通网的最小代价生成树称为最小生成树（Minimum Cost Spanning Tree）
我想在讲算法之前我们先做一下思考，我们如何找到该条路径？
我们是否可以从某一点开始寻找呢？我们从哪一个地点作为起始点呢？我们找到第一个点以后如何找最小权值的边呢？第一步
我想先从概念下手：
首先，因为一个连通图含有图中全部顶点，所以我们可以从任意顶点出发（开始寻找），最终结果应该是一致的 。但是为了方便讲述我还是想从V0开始出发（此时我们站在V0） 。
起始点找到了，那么如何找起始点到第一个顶点的边呢？
逆着想一下，与V0邻接有且仅有两条边（V0,V1）,（V0,V5），我们必须要选一条（因为我们必须要到达V0），所以我们干脆在V0的两条边上选一条到达V0 。
我们站在V0巡视了一下两条边，然后选择了（V0,V1）（此处有判断） 。
然后我们记录一下V0我们已经走过，走过的路标记为红色 。
第二步
但是接下来我们该如何走呢？
其实我也很迷茫，既然不知道，那就选当前能走的路的最近的一条吧 。
现在我们有两种选择，第一种从V0出发，第二种从V1出发，分别产生的可能性如下（绿色）：
选一条最短的
接下来看V5和V1能到达哪里？然后继续寻找…直到最后一个顶点被连通（从0-n的循环）
其实这就是普里姆算法的核心思路，既然思路知道了，我们对比算法来讲解吧 。
普里姆（Prim）算法 在讲之前我们先选一种图的存储结构吧，这里我们用图的邻接矩阵存储结构来讲解 。
39-47行就是上面讲述的寻找我们当前顶点邻接的最小权值边，(用之前的例子讲：第一次循环是顶点V0所有的边，第二次循环除去边(V0,V1)以后顶点V0和V1所有的边，以此类推）而51-58行则是更新当前所有可能的边的最小权值 。算法比较晦涩的是adjvex[MAXVEX]和lowcost[MAXVEX]的理解，一旦理解这两个数组的含义，这个算法也就没难点了 。由代码中的循环嵌套可得知此算法的时间复杂度为O(N^2) 。
推荐阅读
- 矮个子女生成熟穿搭 小个子女生的3个穿衣搭配技巧
- 经济补偿金的具体算法怎么算呢
- 算法的时间复杂度定义
- 递归算法流程图 递归详解
- 商标设计在线生成，手把手教你怎样免费设计logo
- 教你免费设计自己的logo 免费在线生成图标
- 亚马逊Prime会员无广告音乐及播客服务政策
- 手机视频生成gif动图软件推荐 gif动图在线制作工具
- 2进制怎么算 二进制运算法则
- 模拟退火算法介绍 模拟退火算法简介