大家平常都会收发快递，那么某快递公司的一辆货车需要在全国范围内收发快递，为了节省开支，公司需要提前规划货车的行车路线，如何在多条行车路线中找到最划算的呢?我们可以用Graph Algorithm。那么，今天就让我们一起来看一下在这个过程中会被用到的一些常用名词。
首先，来看一个图
这个图是Manchester以及周边五座城镇之间的距离及行车路线。单位为mile。
现在，一家快递公司需要将快递发送到这6个城镇，请问怎样的行车路线最节省开支呢?
在考虑之前，我们需要知道一些基础概念。
上述图为network(网图)，通常我们可以用network来模拟实际情况。
在图中，每个城镇都是vertices【单数为vertex】(或者叫nodes)。连接城镇的线叫做edges(或者arcs)。
那么问题就是怎样连接R O M T S B,使得它们之间的距离最短。
通过观察，我们会发现最短的距离是25英里。如下图：
这是这个网图的minimum spanning tree 最小生成树。
最终答案包含了5个edges。minimum spanning tree 中edges的数量永远会比vertices少一个。MS这条ege的长度并不会被纳入答案，因为那样就形成了一个圈，即MSTM，不符合tree的定义。
那么tree，spanning tree 和minimum spanning tree又分别是什么呢?
Tree
A tree is a connected undirected graph with no simple circuits.
因为没有一个环路，所以一个tree不能有loops。
因此，任何一个tree一定会是一个simple graph。
Theorem： An undirected graph is a tree if and only if there is a unique simple path between any of its vertices.
那么请问以下图中，哪些是tree?
答案下翻
只有左下及右上两幅是trees。
左上：形成了环路
右下：没有连通
Spanning Trees
一个图的spanning tree就是包含了所有vetices的子图。且它是一个tree。
一个graph可能有很多Spanning Trees。
假设你有一个无向连通图
连通：每一个vertex/node都可以通过其他任意一个vertex/ node到达
无向：edges不会有相关方向
那么一个图的spanning tree就是一个没有环路的连通子图。
下图一共有16个不同的 spanning trees，大家有时间的话，可以尝试画一画。
Minimum Spanning Tree
一个图的 minimum spanning tree即花费最小 的spanning tree。
请求出下图中的minimum spanning tree
答案下翻
在最开始Manchester及周边城镇送快递的题中，我们发现只有一条spanning tree能给出最小值25，但并不是永远都是这样的，有可能对于某个graph，会有同样的最小值但是不同的行车路线。
这题之所以可以用观察法是因为只有6个城镇。它的spanning tree较少。但要是有20个城镇，那么可能有的spanning trees会达到2.6*10^23个，通过观察法是不太可能有效率的找到minimum spanning tree的。
那么，我们就需要应用algorithm来帮助我们提高效率。
一般我们使用的是kruscal's algorithm和prim's algorithm。
具体如何实施，请大家关注微信号，之后会分享哟～
好啦，那让我们回顾下，你现在知道vertex/nodes，edges/arcs，tree，spanning tree，minimum spanning tree了么?大家要时常温故而知新哦!
锦秋A-Level为学生提供考培+雅思+留学申请一站式解决方案，针对不同学员的不同层次的学习需求，一对一规划学习方案。全海归教师授课，注重的不只是成绩，更是能力；专业助教团队全天候服务，让学员在课后能够更有效的吸收课上所学习的内容，全方位地提高语言成绩；家校间微信时时互通，只为成就每一位学员的之路。
| 大学名称 | QS排名 |
|---|
