graph-algorithm - 如果在邻居节点中找到目标，我们是否停止深度优先搜索？

Question

只是想弄清楚这个算法。考虑一棵具有根节点和 3 个子节点的小树。A是根，BCD是它的孩子，然后根B有孩子E。如果目标是D，我们是在根扩展后立即停止还是继续向下遍历到E，回来，然后尝试扩展C 在我们去 D 之前？

Answer 1

您检查树中的每一片叶子，尽可能深入地走所有路径。因此，如果您在BCD上有一个订单（即您通过枚举 A 的叶子按此顺序获得它们），您将首先进入ABE，然后是C，最后一个是D。

这通常是通过有一个特殊的结构来存储无人看管的叶子来完成的。