Question

试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

这2个生成树是怎么画出来的 求详细的过程
求配上文字讲解.

Answer 1

从1开始，1连接7,7连接3，3连接4,4连接5,5连接6,6连接2（1已经连过了）（2连接了3,7，但是3和7都已经连过，所以回到上一级6,6的连接是1,2都已经连过，所以再回到上一级5）5连接10 。

（10连接1,6都已经连过了，所以回到上一级5，但是5的所有连接点都连过了，所以回到上一级4）4连接9,（9连接5,10都已经连过了，所以回到上一级4,4也已经练完了，所以再回到上一级3）3连接8，至此连完。

广度遍历：从1开始，连接7和9，下一个是7，连接3和10 ，下一个是9，连接5，下一个是3，连接4和8，下一个是10 连接6，下一个是5，没有什么连接的，下一个是4，没有什么连接的，下一个是8，没有什么连接的，下一个是6，连接2，至此连完。

扩展资料：

通用定义：

若从图的某顶点出发，可以系统地访问到图中所有顶点，则遍历时经过的边和图的所有顶点所构成的子图，称作该图的生成树。

（1）若G是强连通的有向图，则从其中任一顶点v出发，都可以访问遍G中的所有顶点，从而得到以v为根的生成树。

（2）若G是有根的有向图，设根为v，则从根v出发可以完成对G的遍历，得到G的以v为根的生成树。

（3）若G是非连通的无向图，则要若干次从外部调用DFS(或BFS)算法，才能完成对G的遍历。每一次外部调用，只能访问到G的一个连通分量的顶点集，这些顶点和遍历时所经过的边构成了该连通分量的一棵DFS(或BPS)生成树。

G的各个连通分量的DFS(或BFS)生成树组成了G的DFS(或BFS)生成森林。

（4）若G是非强连通的有向图，且源点又不是有向图的根，则遍历时一般也只能得到该有向图的生成森林。

参考资料来源：百度百科-生成树算法