什么是生成树生成树生成森林解说

发布时间：2022-07-07 10:24 所属栏目：51 来源：互联网

导读：在学习连通图的基础上，本节学习什么是生成树，以及什么是生成森林。对连通图进行遍历，过程中所经过的边和顶点的组合可看做是一棵普通树，通常称为生成树。连通图中，由于任意两顶点之间可能含有多条通路，遍历连通图的方式有多种，往往一张连通图可能有

　　在学习连通图的基础上，本节学习什么是生成树，以及什么是生成森林。

　　对连通图进行遍历，过程中所经过的边和顶点的组合可看做是一棵普通树，通常称为生成树。

　　连通图中，由于任意两顶点之间可能含有多条通路，遍历连通图的方式有多种，往往一张连通图可能有多种不同的生成树与之对应。

　　我们知道，非连通图可分解为多个连通分量，而每个连通分量又各自对应多个生成树（至少是 1 棵），因此与整个非连通图相对应的，是由多棵生成树组成的生成森林。

　　因此，多个连通分量对应的多棵生成树就构成了整个非连通图的生成森林。