1、无向图的生成树和生成森林
对于无向连通图，在图的深度优先遍历或广度优先搜索遍历过程中经历的边的集合和 图中的所有顶点一起构成图的极小连通子图，就是一颗生成树（深度优先生成树、广度优先生成树）。
对非连通无向图，深度优先搜索遍历或广度优先搜索遍历，每个连通分量中的顶点集合遍历时走过的边一起构成若干颗生成树，这些连通分量的生成树组成非连通图的生成森林（深度优先生成森林、广度优先生成森林）。
深度优先搜索中的图7-25和图7-26的DFS生成树、BFS生成树、生成森林如下：
DFS生成树：
BFS生成树、BFS生成森林：
2、有向图的生成树和生成森林
对强连通有向图，用DFS和BFS算法可分别求得DFS和BFS生成树。对非强连通图，则一般只能得到生成森林。
无向图或有向图的生成树或生成森林不唯一（选出发点不唯一）。
