什么是最小生成树
为了直观，还是用图片给大家解释一下：
- 对于一个图而言，它可以生成很多树，如右侧图2，图3就是由图1生成的。
- 从上面可以看出生成树是将原图的全部顶点以最少的边连通的子图，对于有n个顶点的连通图，生成树有n-1条边，若边数小于此数就不可能将各顶点连通，如果边的数量多于n-1条边，必定会产生回路。
- 对于一个带权连通图，生成树不同，树中各边上权值总和也不同，权值总和最小的生成树则称为图的最小生成树。
3
关于最小生成树的算法
关于最小生成树有两种算法：Prim算法和Kruskal算法。
Prim算法
基本思想：
假设有一个无向带权图G=(V,E)，他的最小生成树为MinTree=(V,T)，其中V为顶点集合，T为边的集合。
求边的集合T的步骤如下：
①令 U={u0}，T={}。其中U为最小生成树的顶点集合，开始时U中只含有顶点u0（u0可以为集合V中任意一项），在开始构造最小生成树时我们从u0出发。
②对所有u∈U，v∈(V – U)（其中u,v表示顶点）的边(u,v)中，找一条权值最小的边(u’,v’)，将这条边加入到集合T中，将顶点v’加入集合U中。
③直到将V中所有顶点加入U中，则算法结束，否则一直重复以上两步。
④符号说明：我们用大写字母表示集合，用小写字母表示顶点元素，用<>表示两点之间的边。
为了更好的说明问题，我们下面一步一步来为大家展示这个过程。
⑴初始状态：U={a} V={b,c,d,e } T={}
⑵集合U和V相关联的权值最小的边是<a,b>，于是我们将b加入U。U={a,b}，V={d,c,e }，T={<a,b>}
⑶此时集合U和V相关联的权值最小的边是<b,c>，于是我们将c加入U。U={a,b,c} ，V={d,e }，T={<a,b>, <b,c>}
⑷显然此时集合U和V中相关联的权值最小的边是<c,d>，于是我们将d加入U。U={a,b,c,d} ，V={e }，T={<a,b>, <b,c>,<c,d>}
⑸最后集合U和V中相关联的权值最小的边是<d,e>，于是将e加入U。U={a,b,c,d,e} ，V={}，T={<a,b>, <b,c>,<c,d>,<d,e>}。
到此所有点访问完毕。
又到了激动银心的看代码时间了
点击文末的“阅读原文”字样可以直接复制黏贴获取代码哦
代码小说明
将城市X标记为visit=true时，就表示该城市加入到集合U，用sum累加记录边的总费用
