代码之家 › 专栏 › 技术社区 › Bad Request

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

depth-first-search breadth-first-search search algorithm

Bad Request · 技术社区 · 15 年前

我的问题不是关于两种搜索类型的机制。我觉得这比那要平凡得多——我不明白两者的输入和输出。更具体地说,在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 回复 | 直到 15 年前

antonakos 15 年前

输入混乱:

CLRS给出的特定df不关心从何处搜索。搜索的确切结果将取决于 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]

Gintautas Miliauskas 15 年前

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

使用DFS进行路径查找时,只需在找到节点时停止,然后将堆栈一直上移到原始节点即可找到路径。

推荐文章

Tony Hellmuth · 求矩阵中最大连通区域的大小

8 年前

Rxzlion · Python-回溯迷宫生成递归函数理解

8 年前

ssd · 使用DFS枚举子集

8 年前

Salmaan P · 在python中优化DFS

8 年前

ssharma · 平衡二叉树上预序和DFS的时间复杂度相同吗?

9 年前

101ldaniels · DFS发现和完成时间

9 年前

Upender Reddy · 从左上角到右下角单元格的最小路径,在这里我们可以在北、南、东、西方向进行遍历

10 年前

César Vallejo · 将宽度优先搜索更改为深度优先搜索,N-Queen解算器

10 年前

Ankit Mishra · 图与BFS和DFS树的等价性

10 年前

MJM · 使用DFS计算Java中5x5场地上可能的骑士移动

10 年前