最小生成树
假设你是电信的实施工程师,需要为一个镇的九个村庄架设通信网络做设计,村庄位置大致如图,其中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)。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。