我们已经介绍了生成树和森林生成的相关知识,本节将解决如何针对给定的无向图构建相应的生成树和生成森林。
实际上,在遍历有向图时,遍历过程中所经历的图中顶点和边的组合是图的生成树和森林的生成。
图1有向图
例如,图1的有向图由v1 ̄v7的顶点和编号分别为a ̄I的边构成。 使用深度优先搜索算法时,如果V1是遍历的起点,则相关顶点和边缘的遍历顺序如下:
以此遍历顺序构建的生成树如下:
图2深度优先生成树
通过深度优先搜索得到的树是深度优先生成树。 同样,由宽度优先搜索生成的树是宽度优先搜索的树,图1的无向图如图3所示,是以顶点V1为起点进行宽度优先搜索的扫描而得到的树:
图3大小首选生成树
非连通图的生成森林
在非连通图进行遍历时,实际上对非连通图中的每个连通分量进行遍历,对遍历中通过的每个顶点和每个边构成每个连通分量的生成树。
在非连通图中,由多个连通成分构成的多个生成树是非连通图的生成森林。
以深度优先生成森林
图4深度优先生成森林
例如,在对图4的非连通图表(a )使用深度优先搜索算法进行扫描的情况下