最近双11又快到了
有女朋友的忙着帮女朋友清空购物车
有男朋友的忙着叫男朋友帮清购物车
而小编就比较牛逼了
小编沉迷学习，已经无法自拔。
那么今天小编又给大家带来什么好玩的东西呢？
没错
那就是小编通过
夜夜修仙，日日操劳
终于修成的正果
用起来很牛逼，说出去很装逼的
最小生成树
纲要
- 什么是图(network)
- 什么是最小生成树 (minimum spanning tree)
- 最小生成树的算法
1
什么是图
这里的图当然不是我们日常说的图片或者地图。通常情况下，我们把图看成是一种由“顶点(node)”和“边(arc)”组成的抽象网络。各个顶点可以由边连接起来。图的结构可以用来描述多种复杂的数据对象，其应用较为广泛。还是看一个图比较直观：
为了更好地说明问题，下面我们看一个比较老套的通信问题：
在各大城市中建设通信网络，如下图所示，每个圆圈代表一座城市，而边上的数字代表了建立通信连接的价格。那么，请问怎样才能以最小的价格使各大城市能直接或者间接地连接起来呢？
我们需要注意两点：
- 最小的价格
- 各大城市可以是直接或者间接相连的
稍稍留心可以发现，题目的要求是，城市只需要直接或者间接相连，因此，为了节省成本，我们稍稍优化一下上述方案如下：
可以看到，我们砍掉了原先在AD，BE之间的两条道路，建设价格自然就降下来了。当然这个方案也是符合我们题目的要求的。
按照国际惯例，这里要说蛋是了。
上面的实例由于数据很简单，优化的方案很easy就看出来了。但在实际中，数据量往往是非常庞大的。所以，我们更倾向于设计一种方法，然后利用计算机强大的运算能力帮我们处理这些数据得出最优的方案。
那么，针对上述问题，我们一起来看看如何应用图的相关知识来实现吧。
