怎么画深度优先生成树和广度优先生成树【简答题】

一、题目不给存储结构【比较简单】

深度优先生成树

画法，一般从1节点出发DFS，当然不止图中这一条路，答案不唯一

走到10节点发现卡了，所以回溯到7节点

走到8节点发现卡了，回溯到6节点

这样就可以把图中每一个节点都访问到了

广度优先生成树

画法，从1节点开始BFS，分别走到2、3、4、5
然后，分别从2、3、4、5开始BFS【谢谢：weixin_47785172 勘误】

然后，分别再从6、7开始BFS

通过这样处理后，每个节点就都访问到了

一、题目给存储结构【比较难一点】

如果题目给了邻接表，答案就固定下来了，个人觉得考试更喜欢考，因为考试好改卷子

深度优先生成树

从1节点开始DFS，从邻接表可以看到第一个相连接的是2，所以1->2
2节点邻接表第一个相连接是1，因为1节点已经访问了，所以跳过1节点，2->5节点
剩下的同理

从1开始出发，发现走到4就到尽头了，后面的就是回溯了，最后答案就是下面的结果了

广度优先生成树

从1开始出发，将1所连接的2、5、3、4都走到，然后再依次走2、5、3、4的邻接点，直到所有节点都访问一遍

备注：考试的时候，只要画上面的彩色的色就可以了，黑色的线就不用画了