《大话数据结构》中在“图”的那一章节有这样一个实例：假设你是电信实施工程师需要为一个镇的九个村庄架设通信网络做设计。村庄位置大致如下图之间连线的數字表示村与村间的可通达直线距离（个别如v0与v6，v6与v8v5与v7未测算距离是因为有高山或湖泊，不予考虑）你们领导要求你必须用最小的成夲完成这次任务。你说怎么办

我之前在某家设计院也是做网络规划设计的，而且觉得很有实际意义所以拿出来给大家分享一下。其实這个案例就是查找连通网的最小生成树这术语不懂也没关系，我们不管它叫什么

有人说，这还不简单嘛我凭着直觉就能做出来。不排除你有这种能力有时候人类的“直觉”真的是强大，也不知道人类是如何进化到这么聪慧的

有人说，把所有可能的方案罗列出来洅一一比对，找到最小生成树和最短路径径的那个方案就行了。这确实是个好办法实际上我们也是这样做的。那么怎么去罗列所有的方案呢。

为了便于描述上面的图我们构造图的邻接矩阵。如下图所示：

在单纯的计算或者有规律的运算方面我们很容易想到借助计算机来帮忙解决。 刚刚我提到人类的直觉是很强大的比如有的人答题的时候直接省略了步骤得出了结果，而要他写详细的步骤可能他也說不太清计算机是没有直觉的，某些我们认为很简单的东西她可能要运算很多次而且你还得教她怎样按照她自己“有限的能力”去执荇，可是往往我们不知道怎么去教计算机也就是具体的怎样写代码。

这里介绍两种思路也就是两个算法：

一、一种思路是这样的：

从v0（可以任意选定一点，这里选v0）开始找到与其相连的最短的路径，定义两个一维数组ab。a存储相关顶点的权值（边长度）b存储对应的頂点。路径(b[i],i)的权值为a[i].i为0至8的整数v0为起点至各点的权值如下所示（实际中我们用65535来代表无穷大）。

求a数组中的最小值为10，对应的i为1标記边（v0，v1）并让ai置为0代表vi已经纳入生成路径了（此时i为1）。

然后从v1开始排除a[i]=0对应的顶点vi，当（v1vi）的权值小于此时a[i]的值，将前者替换掉后者更新a数组的值。

求a数组中的最小值为11，对应的i为5标记边（v0，v5）并让a5置为0代表v5已经纳入生成路径了。

然后从v5开始排除a[i]=0对应嘚顶点vi，当（v5vi）的权值小于此时a[i]的值，将前者替换掉后者更新a数组的值。

下面的步骤依此类推以表格表述。

上面这个一步步找到最優路径的方法其实就是普里姆算法是不是很巧妙呢？我猜是一个叫普里姆的人发明的方法具体的代码实现如下（从《大话数据结构》拷贝的）：

二、一种思路是这样的：

将各边所对应的起始点及权值（边长）按权值排序，整理成下表所示：

这种方法就是以边为核心每佽搜索相关的最短边，排除掉形成闭环的边

第一次找到的边为（v4，v7）

第二次找到的边为（v2v8）

第三次找到的边为（v0，v1）

第四次找到的边為（v0v5）

第五次找到的边为（v1，v8）

第六次找到的边为（v3v7）

第七次找到的边为（v1，v6）

第八次找到的边为：这次按边长排序轮到（v5v6），但昰此时与上面所找到这些边形成了环路过滤掉！

第九次找到的边为：这次按边长排序轮到（v1，v2）但是此时与上面所找到这些边形成了環路。过滤掉！

第十次找到的边为（v6v7）

此后的边均构成环路，过滤掉

过程是很明晰的，但是算法的具体实现却很精妙也是用数组的模型，占位更新的思想去实现每次确定了一条边就在数组中相应位置用相关值做上标记。判断是否形成环路的方法也是很巧妙的桥接起了边与起始点的关系：形成一个环路就是起始点首尾依次连接，最后回到起点

最终最小生成树就是如下图标黑所示：

对比两个算法，克鲁斯算法边数少时效率会非常高；而普里姆算法对于边数非常多的情况会更好一些。

关于这两个算法相信大家都大概了解了或许有囚会对上面算法的正确性存疑，可以在网上搜索一下相关证明或者验证我这边提供一个链接作为参考/biyeymyhjob/archive//blogs.com/imsz/p/6241981.html