队列和BFS：广度优先搜索(BFS)的一个常见应用是寻找从根节点到目标节点的最短路径。示例这里我们举一个例子来说明如何使用BFS来寻找根节点A和目标节点G之间的最短路径。见解看完上面的动画，我们来回答以下问题：1.节点是按什么顺序处理的？在第一轮中，我们处理根节点。在第二轮中，我们处理根节点的下一个节点；第三轮，我们处理距离根节点两步的节点；等等等等。类似于树的层序遍历，越靠近根节点的节点越早遍历。如果节点X在第k轮加入队列，则根节点到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
