最小生成树

假设你是电信的实施工程师，你需要为一个镇的九个村设计一个通信网络。村落的位置大致如图，其中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算法的核心思想。既然已经知道了这个想法，那我们就通过对比算法来解释一下。

Prim算法

在讨论之前，我们先选择一个图的存储结构。这里，我们用图的邻接矩阵存储结构来解释。

第39-47行是上面提到的用于寻找我们当前顶点邻接的最小权重边，(使用前面的例子:第一个循环是顶点V0的所有边，第二个循环在边(V0，V1，等等)之后去除顶点V0和V1的所有边)，而第51-58行是用于更新当前所有可能的边的最小权重。晦涩的算法是对adjvex[MAXVEX]和lowcost[MAXVEX]的理解。一旦你理解了这两个数组的含义，这个算法就没有难度了。

从代码中的循环嵌套可知，该算法的时间复杂度为O (n 2)。

本文来自怪你过分美丽投稿，不代表舒华文档立场，如若转载，请注明出处：https://www.chinashuhua.cn/24/614201.html