<p>前面已经给大家介绍了有关生成树和生成森林的有关知识，本节来解决对于给定的无向图，如何构建它们相对应的生成树或者生成森林。</p> 讯享网
其实在对无向图进行遍历的时候，遍历过程中所经历过的图中的顶点和边的组合，就是图的生成树或者生成森林。
图 1 无向图
例如，图 1 中的无向图是由 V1～V7 的顶点和编号分别为 a～i 的边组成。当使用深度优先搜索算法时，假设 V1 作为遍历的起始点，涉及到的顶点和边的遍历顺序为（不唯一）：
此种遍历顺序构建的生成树为：
图 2 深度优先生成树
由深度优先搜索得到的树为深度优先生成树。同理，广度优先搜索生成的树为广度优先生成树，图 1 无向图以顶点 V1 为起始点进行广度优先搜索遍历得到的树，如图 3 所示：
图 3 广度优先生成树
非连通图在进行遍历时，实则是对非连通图中每个连通分量分别进行遍历，在遍历过程经过的每个顶点和边，就构成了每个连通分量的生成树。
非连通图中，多个连通分量构成的多个生成树为非连通图的生成森林。
图 4 深度优先生成森林
例如，对图 4 中的非连通图 （a） 采用深度优先搜索算法遍历时，得到的深度优先生成森林（由 3 个深度优先生成树构成）如 （b） 所示（不唯一）。
非连通图在遍历生成森林时，可以采用孩子兄弟表示法将森林转化为一整棵二叉树进行存储。
具体实现的代码：
讯享网
运行程序，拿图 4（a）中的非连通图为例，构建的深度优先生成森林，使用孩子兄弟表示法表示为：
图5 孩子兄弟表示法表示深度优先生成森林
图中，3 种颜色的树各代表一棵深度优先生成树，使用孩子兄弟表示法表示，也就是将三棵树的树根相连，第一棵树的树根作为整棵树的树根。
运行结果
13,13
1
2
3
4
5
6
7
8
9
10
11
12
13
1,2
1,3
1,6
1,12
2,13
4,5
7,8
7,10
7,9
8,10
11,12
11,13
12,13
1 2 13 11 12 3 6 4 5 7 8 10 9
非连通图采用广度优先搜索算法进行遍历时，经过的顶点以及边的集合为该图的广度优先生成森林。
拿图 4（a）中的非连通图为例，通过广度优先搜索得到的广度优先生成森林用孩子兄弟表示法为：
图6 广度优先生成森林（孩子兄弟表示法）
实现代码为：
运行结果为：
13,13
1
2
3
4
5
6
7
8
9
10
11
12
13
1,2
1,3
1,6
1,12
2,13
4,5
7,8
7,10
7,9
8,10
11,12
11,13
12,13
1 2 13 3 6 12 11 4 5 7 8 9 10
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/207604.html