生成树和生成森林

时间:2021-11-15 12:35:42

1、无向图的生成树和生成森林

对于无向连通图,在图的深度优先遍历广度优先搜索遍历过程中经历的边的集合和 图中的所有顶点一起构成图的极小连通子图,就是一颗生成树(深度优先生成树、广度优先生成树)。

对非连通无向图,深度优先搜索遍历或广度优先搜索遍历,每个连通分量中的顶点集合遍历时走过的边一起构成若干颗生成树,这些连通分量的生成树组成非连通图的生成森林(深度优先生成森林、广度优先生成森林)。

深度优先搜索中的图7-25和图7-26的DFS生成树、BFS生成树、生成森林如下:

DFS生成树:

生成树和生成森林

BFS生成树、BFS生成森林:

生成树和生成森林

2、有向图的生成树和生成森林

对强连通有向图,用DFS和BFS算法可分别求得DFS和BFS生成树。对非强连通图,则一般只能得到生成森林。

无向图或有向图的生成树或生成森林不唯一(选出发点不唯一)。

生成树和生成森林