摘要：队列和广度优先搜索的一个常见应用是找出从根结点到目标结点的最短路径。然后在每一轮中，我们逐个处理已经在队列中的结点，并将所有邻居添加到队列中。这就是我们在中使用队列的原因。
队列和 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
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/76182.html
摘要：树可谓是开发者最常碰到的数据结构之一了要知道整张网页就是一棵树啊所以我们就来学习树这一数据结构吧在这篇文章中我们将创建一棵树并且用两种不同的方法来遍历它深度优先遍历和宽度广度优先遍历方法使用借助栈这一数据结构来访问树的每个节点则借助了队 树可谓是web开发者最常碰到的数据结构之一了. 要知道, 整张网页就是一棵DOM树啊 (Document Object Model ). 所以我...
摘要：树是一副无环连通图。互不相连的树组成的集合称为森林。表示无向图的数据类型图的基本操作的两个构造，得到顶点数和边数，增加一条边。该方法不符合第一个条件，上百万个顶点的图是很常见的空间不满足。 四种重要的图模型： 无向图（简单连接） 有向图（连接有方向性） 加权图（连接带有权值） 加权有向图（连接既有方向性又带有权值） 无向图 定义：由一组顶点和一组能够将两个顶点相连的边组成。 特殊：...
摘要：树中结点的最大层次称为树的深度或高度。二叉树有深度遍历和广度遍历，深度遍历有前序中序和后序三种遍历方法。二叉树的前序遍历可以用来显示目录结构等中序遍历可以实现表达式树，在编译器底层很有用后序遍历可以用来实现计算目录内的文件及其信息等。 树的简介 栈、队列、链表等数据结构，都是顺序数据结构。而树是非顺序数据结构。树型结构是一类非常重要的非线性结构。直观地，树型结构是以分支关系定义的层次结...
摘要：队列栈队列是先进先出，后进后出，常用的操作是取第一个元素尾部加入一个元素。栈是后进先出，就像一个垃圾桶，后入的垃圾先被倒出来。遍历中间过程，每一个节点入栈的时候是灰色的，出栈的时候是黑色的。 0. 前言 广度优先搜索(BFS)和深度优先搜索(DFS)，大家可能在oj上见过，各种求路径、最短路径、最优方法、组合等等。于是，我们不妨动手试一下js版本怎么玩。 1.队列、栈 队列是先进先出，...
摘要：当队列非空时，拿出最后放入的元素。若减后入度为，则这个结点遍历完成，放入结果数组和队列。递归函数去遍历的，继续在中标记，使得所有点只遍历一次。最深的点最先，根结点最后，加入结果数组的头部处。 Problem Given an directed graph, a topological order of the graph nodes is defined as follow: For ...
阅读 2106·2021-11-05 09:42
阅读 2850·2021-09-23 11:21
阅读 2840·2019-08-30 14:00
阅读 3313·2019-08-30 13:15
阅读 464·2019-08-29 17:18
阅读 3546·2019-08-29 16:29
阅读 2748·2019-08-29 14:06
阅读 2793·2019-08-23 14:41
