绘制深度优先搜索树
Draw the depth first search tree
我正在尝试解决一些纸质考试的问题，但我遇到了这个问题：
Consider the graph G = (N,A) where N={a,b,c,d,e,f,g,h} and A is the
following set of arcs:
{(0,5),(5,4),(4,5),(4,1),(1,2),(2,3),(3,4),(4,3),(0,6),(6,7)} and I
have to draw the depth-first search tree T for G with the root being 0
这是图表：
我得到了以下树：
答案是这个：
（以上两种情况，请无视箭头）
我不明白为什么。谁能解释我做错了什么？
谢谢！
这两棵树都是正确的，因为它们都可以通过 depth-first 搜索生成。根据我的理解，这里的关键点是对于给定的图，可能存在多个 depth-first 搜索树，这取决于选择当前节点的 children 的顺序。更准确地说，depth-first 搜索，没有任何关于如何迭代 children 的明确规则，不是确定性过程。如评论中所示，您找到的解决方案可以通过选择具有最小节点索引的 child 来获得，而建议的解决方案可以通过选择具有最大节点索引的 child 来生成。
我正在尝试解决一些纸质考试的问题，但我遇到了这个问题：
Consider the graph G = (N,A) where N={a,b,c,d,e,f,g,h} and A is the following set of arcs: {(0,5),(5,4),(4,5),(4,1),(1,2),(2,3),(3,4),(4,3),(0,6),(6,7)} and I have to draw the depth-first search tree T for G with the root being 0
这是图表：
我得到了以下树：
答案是这个：
（以上两种情况，请无视箭头） 我不明白为什么。谁能解释我做错了什么？ 谢谢！
这两棵树都是正确的，因为它们都可以通过 depth-first 搜索生成。根据我的理解，这里的关键点是对于给定的图，可能存在多个 depth-first 搜索树，这取决于选择当前节点的 children 的顺序。更准确地说，depth-first 搜索，没有任何关于如何迭代 children 的明确规则，不是确定性过程。如评论中所示，您找到的解决方案可以通过选择具有最小节点索引的 child 来获得，而建议的解决方案可以通过选择具有最大节点索引的 child 来生成。