其实在对无向图进行遍历的时候，遍历过程中所经历过的图中的顶点和边的组合，就是图的生成树或者生成森林。
图 1 无向图
例如，图 1 中的无向图是由 V1～V7 的顶点和编号分别为 a～i 的边组成。当使用深度优先搜索算法时，假设 V1 作为遍历的起始点，涉及到的顶点和边的遍历顺序为（不唯一）：
此种遍历顺序构建的生成树为：
图 2 深度优先生成树
由深度优先搜索得到的树为深度优先生成树。同理，广度优先搜索生成的树为广度优先生成树，图 1 无向图以顶点 V1 为起始点进行广度优先搜索遍历得到的树，如图 3 所示：
图 3 广度优先生成树
非连通图的生成森林
非连通图在进行遍历时，实则是对非连通图中每个连通分量分别进行遍历，在遍历过程经过的每个顶点和边，就构成了每个连通分量的生成树。非连通图中，多个连通分量构成的多个生成树为非连通图的生成森林。
深度优先生成森林
图 4 深度优先生成森林 例如，对图 4 中的非连通图 （a） 采用深度优先搜索算法遍历时，得到的深度优先生成森林（由 3 个深度优先生成树构成）如 （b） 所示（不唯一）。 标签：优先,遍历,连通,生成,详解,深度,广度 From： https://www.cnblogs.com/yitongtianxia666/p/16913489.html