imsz5460
通信网络规划的最短路径（最小生成树的2种算法介绍）
《大话数据结构》中在“图”的那一章节有这样一个实例：假设你是电信实施工程师，需要为一个镇的九个村庄架设通信网络做设计。村庄位置大致如下图，之间连线的数字表示村与村间的可通达直线距离（个别如v0与v6，v6与v8，v5与v7未测算距离是因为有高山或湖泊，不予考虑）。你们领导要求你必须用最小的成本完成这次任务。你说怎么办？
我之前在某家设计院也是做网络规划设计的，而且觉得很有实际意义，所以拿出来给大家分享一下。其实这个案例就是查找连通网的最小生成树。这术语不懂也没关系，我们不管它叫什么。
有人说，这还不简单嘛，我凭着直觉就能做出来。不排除你有这种能力，有时候人类的“直觉”真的是强大，也不知道人类是如何进化到这么聪慧的。
有人说，把所有可能的方案罗列出来，再一一比对，找到最短路径的那个方案，就行了。这确实是个好办法，实际上我们也是这样做的。那么怎么去罗列所有的方案呢？。
为了便于描述上面的图，我们构造图的邻接矩阵。如下图所示：
在单纯的计算或者有规律的运算方面，我们很容易想到借助计算机来帮忙解决。 刚刚我提到人类的直觉是很强大的，比如有的人答题的时候直接省略了步骤得出了结果，而要他写详细的步骤可能他也说不太清。计算机是没有直觉的，某些我们认为很简单的东西她可能要运算很多次，而且你还得教她怎样按照她自己“有限的能力”去执行，可是往往我们不知道怎么去教计算机，也就是具体的怎样写代码。
这里介绍两种思路，也就是两个算法：
一、一种思路是这样的：
从v0（可以任意选定一点，这里选v0）开始，找到与其相连的最短的路径，定义两个一维数组a，b。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，当（v1，vi）的权值小于此时a[i]的值，将前者替换掉后者，更新a数组的值。
求a数组中的最小值，为11，对应的i为5，标记边（v0，v5）并让a5置为0，代表v5已经纳入生成路径了。
然后从v5开始，排除a[i]=0对应的顶点vi，当（v5，vi）的权值小于此时a[i]的值，将前者替换掉后者，更新a数组的值。
延伸阅读
- ssh框架 2016-09-30
- 阿里移动安全 [无线安全]玩转无线电——不安全的蓝牙锁 2017-07-26
- 消息队列NetMQ 原理分析4-Socket、Session、Option和Pipe 2024-03-26
- Selective Search for Object Recognition 论文笔记【图片目标分割】 2017-07-26
- 词向量-LRWE模型-更好地识别反义词同义词 2017-07-26
- 从栈不平衡问题 理解 calling convention 2017-07-26
- php imagemagick 处理 图片剪切、压缩、合并、插入文本、背景色透明 2017-07-26
- Swift实现JSON转Model - HandyJSON使用讲解 2017-07-26
- 阿里移动安全 Android端恶意锁屏勒索应用分析 2017-07-26
- 集合结合数据结构来看看(二) 2017-07-26
学习是年轻人改变自己的最好方式