绘制深度优先搜索树

Question

我试图解决一些纸考试一些问题，我有这样的问题：

考虑图G =（N，A），其中N = {A，B， （0,5），（5,4），（4,5），（4,1），（1，c，d，e，f，g，h}和A是在一组弧之后的 。 ，2），（2,3），（3,4），（4,3），（0,6），（6,7）}和I 必须绘制G的深度优先搜索树T根为0

这是图：

我得到了下面的树：

，答案是这一个：

（对于上述两种情况下，请忽略箭头） 我不明白为什么。任何人都可以向我解释我做错了什么？ 谢谢！

Answer 1

这两棵树都是正确的，它们都可以通过深度优先搜索生成。就我的理解而言，这里的关键点在于，对于给定的图形，可能存在多个深度优先的搜索树，具体取决于当前节点的子节点的选择顺序。更确切地说，深度优先搜索没有任何关于如何迭代儿童的明确规则，这不是一个确定性的过程。如评论所示，您找到的解决方案可以通过选择具有最小节点索引的孩子来获得，而提出的解决方案可以通过选择具有最大节点索引的孩子来生成。