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