图
1. 最小生成树概念
生成树概念：
无向图中，一个连通图的最小连通子图称作该图的生成树（不能带环，保持连通，但边要尽可能的少）。
有n个顶点的连通图的生成树有n个顶点和n-1条边。
比如：
这里的最小其实是指的边的权值之和最小，当然是要在保证它是生成树的前提下权值之和最小。
所以，对于一个连通图来说，在它的所有的生成树里面，边的权值之和最小的生成树就是该连通图的最小生成树，当然最小生成树也可以有多个，因为边的权值是可以相等的。
连通图中的每一棵生成树，都是原图的一个极大无环子图，即：从其中删去任何一条边，生成树就不再连通；反之，在其中引入任何一条新边，都会形成一条回路。
若连通图由n个顶点组成，==则其生成树必含n个顶点和n-1条边==。因此构造最小生成树的准则有三条：
- 只能使用图中权值最小的边来构造最小生成树
- 只能使用恰好n-1条边来连接图中的n个顶点
- 选用的n-1条边不能构成回路
构造最小生成树的方法：
Kruskal算法和Prim算法。
这两个算法都采用了逐步求解的贪心策略。
贪心算法：
是指在问题求解时，总是做出当前看起来最好的选择。
也就是说贪心算法做出的不是整体最优的的选择，而是某种意义上的局部最优解。
贪心算法不是对所有的问题都能得到整体最优解。
==Prim算法（普里姆）==
思想：首先，选一个顶点作为起点，选哪个都可以；然后呢，它在选边的时候把图里面的顶点分成了两个集合，一个集合是已经被选到的结点组成的集合，另一个集合是剩下的结点组成的集合。
每次选边的时候是从两个集合中的顶点直接相连的边中选取权值最小的那一条。
==Kruskal算法（克鲁斯卡尔）==
算法思想：
任给一个有n个顶点的连通图N={V,E}，
首先构造一个由这n个顶点组成、不含任何边的图G={V,NULL}，其中每个顶点自成一个连通分量（集合），其次不断从E中取出权值最小的一条边(若有多条权值相等任取其一)，若该边的两个顶点来自不同的连通分量，则将此边加入到G中。如此重复，直到所有顶点在同一个连通分量上为止。
核心：每次迭代时，选出一条具有最小权值的边，且边的两端点不在同一连通分量（集合）上，则加入生成树。
==其实就是每次从图中还未被选到的所有的边里面选出权值最小且不会构成环的边，选够n-1条就完成了，这n-1条边构成的生成树就是该图对应的最小生成树。==