1

我的问题并不是关于这两种搜索类型的机制。我觉得它比这更平凡 - 我不了解两者的输入和输出。更具体地说，在 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
4

2 回答 2

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 的版本生成了一个森林（图的每个组件都有一棵树），而不仅仅是一棵树，这可能更适合他们的目的。

输出混乱：

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

Print-Path-To-Root(v)
1 while v ≠ Nil
2   do print v
3      v ← π[v]
于 2010-11-19T19:24:01.067 回答
0

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

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

于 2010-11-18T15:17:58.537 回答