資訊專欄INFORMATION COLUMN
摘要：隊列和廣度優先搜索的一個常見應用是找出從根結點到目標結點的最短路徑。然后在每一輪中，我們逐個處理已經在隊列中的結點，并將所有鄰居添加到隊列中。這就是我們在中使用隊列的原因。
隊列和 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
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/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 ...
閱讀 2107·2021-11-05 09:42
閱讀 2851·2021-09-23 11:21
閱讀 2841·2019-08-30 14:00
閱讀 3314·2019-08-30 13:15
閱讀 465·2019-08-29 17:18
閱讀 3547·2019-08-29 16:29
閱讀 2749·2019-08-29 14:06
閱讀 2794·2019-08-23 14:41
