最小生成树
1、基本概念
🐋树的特性
1）连通图的生成树（Spanning Tree）
2）是图的极小连通子树，它包含图中的全部顶点，但只有构成一颗树的边（极小连通子树：边是最少的，不能在少，否则不连通）
3）生成树又是图的极大无回路子图，它的边集是关联图中的所有顶点而又没有形成回路的边。
（极大无回路子图：边不能在多，再多，就回路）
4）一个有n个顶点的连通图的生成树只能有n-1条边。
若有n个顶点而少于n-1条边，则是非连通图。
若多余n-1条边，则一定形成回路。
有n-1条边的生成子图并不一定是生成树。
5）图的生成树不是唯一的。
6）连通图生成树，根据遍历方式分为：
由广度优先遍历得到的生成树，称为广度优先生成树。
由深度优先遍历得到的生成树，称为深度优先生成树。
7）非连通图的生成森林
对于非连通图，每一个连通分量中的顶点集和遍历时经过的边一起构成若干棵生成树，这些生成树组成了该非连通图的生成森林。
8）非连通图生成森林，根据遍历方式分为：
由广度优先遍历得到的生成森林，称为广度优先生成森林。
由深度优先遍历得到的生成森林，称为深度优先生成森林。
🐋最小生成树
问题：
假设要在n个城市之间建立通讯联络网，则连通n个城市只需要修建n-1条线路，如何在最节省经费的前提下建立这个通讯网？
等效问题：
构建网的一颗最小生成树，即：在e条带权的边中选取n-1条边（不构成回路），使权值之和为最小？
最小生成树：
1）在一个网的所有生成树中，权值总和最小的生成树称为最小代价生成树，也称为最小生成树。
2）构建最小生成树的准则：
1. 只能使用该图中的边构造最小生成树
2. 当且仅当使用n-1条边来连接图中的n个顶点
3. 不能使用产生回来的边。
3）求图的最小生成树的典型算法：
克鲁斯卡尔（Kruskal）算法
普里姆（Prim）算法
注：考虑问题的出发点相同：为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能的小。
