广度优先与深度优先搜索的输入/输出-Java 学习之路

我的问题不是关于任何一种搜索类型的机制 . 我觉得它比那更平凡 - 我不理解任何一个的输入和输出 . 更具体地说，在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 ﬁnished.
9 f [u] ← time ← time+1

2 回答

0
输入混乱：

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]
```
回复于 2024-04-20T21:53:05+08:00
1

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

使用DFS进行路径寻找时，只需在找到节点时停止，然后将堆栈一直处理到原始节点以查找路径 .

回复于 2024-04-20T21:53:05+08:00

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

2 回答

相关问题