生成树
概念
- 给定一个无向图，如果它任意两个顶点都联通并且是一棵树，那么我们就称之为生成树。
- 也就是说，深度优先遍历或者广度优先遍历搜索无向联通图的过程中，经过的所有顶点与边的集合一起构成的图的极小联通子图，就是生成树。
- 生成树也叫深度优先生成树或广度优先生成树。
生成森林
概念
- 非连通无向图深度优先搜索遍历或广度优先搜索遍历，每个连通分量中的顶点集合遍历时走过的边一起构成若干颗生成树，这些连通分量的生成树组成非连通图的生成森林
注意：生成树是对应连通图来说，而生成森林是对应非连通图来说的
最小生成树
概念
- 给定一个带权值的无向图，权值之和最小的生成树，我们就称之为最小生成树。
- 最小生成树又称MST或最小代价生成树
- 按照我的理解：从图中找到一个权值最小的边的集合，使得所有点相互联通
性质
- 图中权值最小的边（如果唯一的话）一定在最小生成树上
- 对于一个图G，如果图中的边权值都不相同，则图的最小生成树唯一，反之不然。
求解最小生成树算法
- Kruskal算法
- Prim算法
