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

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

输入困惑：

特定DFS通过CLRS给出不关心你来自哪里搜索。搜索的确切结果取决于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进行寻路时，只需在找到节点时停下来，然后将堆栈一直处理到原始节点以查找路径。