生成树与生成森林
- 对连通图进行遍历，过程中所经过的边和顶点的组合可看做是一棵普通树，通常称为生成树。
- 一个连通图的生成树是极小连通子图,它含有图中全部顶点。但只有足以构成一棵树的n-1条边。
- 一棵有n个顶点的生成树有且仅有n-1条边。如果一个图有n个顶点和n-1条边，则是非连通图；如果它多于n-1条边，则一定有环。但是，有n-1条边的图不一定是生成树。
- 连通图中，由于任意两顶点之间可能含有多条通路，遍历连通图的方式有多种，往往一张连通图可能有多种不同的生成树与之对应。
- 生成树是对应连通图来说，而生成森林是对应非连通图来说的。
投递中国南方电网等公司10个岗位 >