队列和 BFS —— 栈和 DFS
队列和 BFS:
广度优先搜索(BFS)的一个常见应用是找出从根结点到目标结点的最短路径。
示例
这里我们提供一个示例来说明如何使用 BFS 来找出根结点 A
和目标结点 G
之间的最短路径。
洞悉
观看上面的动画后,让我们回答以下问题:
1. 结点的处理顺序是什么?
在第一轮中,我们处理根结点。在第二轮中,我们处理根结点旁边的结点;在第三轮中,我们处理距根结点两步的结点;等等等等。
与树的层序遍历类似,越是接近根结点的结点将越早地遍历
。
如果在第 k 轮中将结点 X
添加到队列中,则根结点与 X
之间的最短路径的长度恰好是 k
。也就是说,第一次找到目标结点时,你已经处于最短路径中。
2. 队列的入队和出队顺序是什么?
如上面的动画所示,我们首先将根结点排入队列。然后在每一轮中,我们逐个处理已经在队列中的结点,并将所有邻居添加到队列中。值得注意的是,新添加的节点不会
立即遍历,而是在下一轮中处理。
结点的处理顺序与它们添加
到队列的顺序是完全相同的顺序
,即先进先出(FIFO)。这就是我们在 BFS 中使用队列的原因。
栈和 DFS:
与 BFS 类似,深度优先搜索
(DFS)也可用于查找从根结点到目标结点的路径。在本文中,我们提供了示例来解释 DFS 是如何工作的以及栈是如何逐步帮助 DFS 工作的。
示例
我们来看一个例子吧。我们希望通过 DFS 找出从根结点 A
到目标结点 G
的路径。
洞悉
观看上面的动画后,让我们回答以下问题:
1. 结点的处理顺序是什么?
在上面的例子中,我们从根结点 A
开始。首先,我们选择结点 B
的路径,并进行回溯,直到我们到达结点 E
,我们无法更进一步深入。然后我们回溯到 A
并选择第二条路径到结点 C
。从 C
开始,我们尝试第一条路径到 E
但是 E
已被访问过。所以我们回到 C
并尝试从另一条路径到 F
。最后,我们找到了 G
。
总的来说,在我们到达最深的
结点之后,我们只
会回溯并尝试另一条路径。
因此,你在 DFS 中找到的第一条路径并不总是最短的路径。例如,在上面的例子中,我们成功找出了路径
A-> C-> F-> G
并停止了 DFS。但这不是从A
到G
的最短路径。
2. 栈的入栈和退栈顺序是什么?
如上面的动画所示,我们首先将根结点推入到栈中;然后我们尝试第一个邻居 B
并将结点 B
推入到栈中;等等等等。当我们到达最深的结点 E
时,我们需要回溯。当我们回溯时,我们将从栈中弹出最深的结点
,这实际上是推入到栈中的最后一个结点
。
结点的处理顺序是完全相反的顺序
,就像它们被添加
到栈中一样,它是后进先出(LIFO)。这就是我们在 DFS 中使用栈的原因。
总结:
显然BFS可以找到根节点到目标节点最短的路径,DFS可以最快的找到根节点到目标节点的路线,但却不一定是最短的。具体可参考维基百科:
BFS:https://zh.wikipedia.org/wiki/广度优先搜索
DFS:https://zh.wikipedia.org/wiki/深度优先搜索
欢迎关注微.信公.众号:爱写Bug
最新文章
- java解析json数据
- 转换,2D,3D
- OpenMP之枚举排序
- js中的预加载与懒加载(延迟加载)
- SQL SERVER基础语句
- FireDAC如何连接ORACLE数据库
- SPRING IN ACTION 第4版笔记-第三章ADVANCING WIRING-009-用SPEL给bean运行时注入依赖值
- linux下安装MySQL5.6记录
- ArrayList和List主要区别 就是ArrayList类型不安全。
- Swift数组字面量
- React和Vue的组件更新比较
- Xshell显示图形化界面
- Struts2中的值栈
- TCP、UDP以及HTTP的简单讲解
- C++类有继承时,析构函数必须为虚函数
- 【个人项目总结】C#四则运算表达式生成程序
- Python全栈开发-Day2-Python基础2
- java基础入门系列1
- 3d打印机的软件系统组成部分
- ES monitoring
热门文章
- C++入门到理解阶段二基础篇(3)——C++数据类型
- pandas 学习 第7篇:DataFrame - 数据处理(应用、操作索引、重命名、合并)
- vscode wsl git 换行符问题autocrlf
- linux 安装 nvm, node.js, npm
- C# - 操作Word文档小实验
- 8.智能快递柜SDK(联网型锁板)
- [20190524]浅谈模糊查询.txt
- [Go] 并发imap收信
- 使history命令显示时间
- 对CNN 的理解