广度优先与深度优先搜索的输入/输出

Question

我的问题实际上并不是关于这两种搜索类型的机制。我觉得它比这更平凡 - 我不理解其中任何一个的输入和输出。更具体地说，在 CLRS 中，BFS 将图和源节点作为输入，但 DFS 仅采用图。 DFS 不关心你从哪里搜索吗？

这就是输入混乱。输出混乱在于，在 DFS 中，当你完成后，你会得到一个类似表的结构，记录每个节点的发现和完成时间，对吗？如何从中提取解决方案，即从源节点到目标节点的路径？

我希望我说得有道理。谢谢！

编辑：这就是我所说的 DFS 不采用源节点的意思。这是来自 CLRS 的 DFS 伪代码。我没有看到它在任何地方使用源节点。我看到它所做的只是遍历图中的所有节点。

DFS(G)
1 for each vertex u ∈ V[G]
2 do color[u] ← WHITE
3 π[u]← NIL
4 time ← 0
5 for each vertex u ∈ V[G]
6 do if color[u] = WHITE
7 then DFS-VISIT(u)

DFS-VISIT(u)
1 color[u] ← GRAY ✄ White vertex u has just been discovered.
2 time ← time+1
3 d[u] ← time
4 for each v ∈ Adj[u] ✄ Explore edge (u,v).
5 do if color[v] = WHITE
6 then π[v] ← u
7 DFS-VISIT(v)
8 color[u] ← BLACK ✄ Blacken u;it is finished.
9 f [u] ← time ← time+1

Answer 1

输入混乱：

CLRS 给出的特定 DFS 不关心您从哪里搜索。搜索的确切结果将取决于 V[G] 中节点的顺序。通常我会认为 DFS 从一个节点开始，例如：

DFS-Simple(G, s)
1 for each vertex u ∈ V[G]
2   do color[u] ← WHITE
3 π[u]← NIL
4 time ← 0
5 DFS-VISIT(s)

CLRS 的版本会生成一个森林（图的每个组件对应一棵树），而不是仅仅一棵树，这可能更适合其目的。

输出混乱：

路径不是通过时间戳记录的，而是通过父指针π记录的。例如，给定一个节点 v，您可以像这样打印其根节点的路径：

Print-Path-To-Root(v)
1 while v ≠ Nil
2   do print v
3      v ← π[v]

Answer 2

BFS 和 DFS 都将源节点作为输入。

当使用 DFS 进行寻路时，您只需在找到节点时停止，然后一直向上堆栈到原始节点以查找路径。