国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

隊(duì)列和 BFS —— 棧和 DFS

Kyxy / 1631人閱讀

摘要：隊(duì)列和廣度優(yōu)先搜索的一個(gè)常見應(yīng)用是找出從根結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的最短路徑。然后在每一輪中，我們逐個(gè)處理已經(jīng)在隊(duì)列中的結(jié)點(diǎn)，并將所有鄰居添加到隊(duì)列中。這就是我們在中使用隊(duì)列的原因。

隊(duì)列和 BFS：

廣度優(yōu)先搜索（BFS）的一個(gè)常見應(yīng)用是找出從根結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的最短路徑。

示例

這里我們提供一個(gè)示例來說明如何使用 BFS 來找出根結(jié)點(diǎn) A 和目標(biāo)結(jié)點(diǎn) G 之間的最短路徑。

洞悉

觀看上面的動(dòng)畫后，讓我們回答以下問題：

1. 結(jié)點(diǎn)的處理順序是什么？

在第一輪中，我們處理根結(jié)點(diǎn)。在第二輪中，我們處理根結(jié)點(diǎn)旁邊的結(jié)點(diǎn)；在第三輪中，我們處理距根結(jié)點(diǎn)兩步的結(jié)點(diǎn)；等等等等。

與樹的層序遍歷類似，越是接近根結(jié)點(diǎn)的結(jié)點(diǎn)將越早地遍歷。

如果在第 k 輪中將結(jié)點(diǎn) X 添加到隊(duì)列中，則根結(jié)點(diǎn)與 X 之間的最短路徑的長度恰好是 k。也就是說，第一次找到目標(biāo)結(jié)點(diǎn)時(shí)，你已經(jīng)處于最短路徑中。

2. 隊(duì)列的入隊(duì)和出隊(duì)順序是什么？

如上面的動(dòng)畫所示，我們首先將根結(jié)點(diǎn)排入隊(duì)列。然后在每一輪中，我們逐個(gè)處理已經(jīng)在隊(duì)列中的結(jié)點(diǎn)，并將所有鄰居添加到隊(duì)列中。值得注意的是，新添加的節(jié)點(diǎn)不會(huì)立即遍歷，而是在下一輪中處理。

結(jié)點(diǎn)的處理順序與它們添加到隊(duì)列的順序是完全相同的順序，即先進(jìn)先出（FIFO）。這就是我們在 BFS 中使用隊(duì)列的原因。

棧和 DFS：

與 BFS 類似，深度優(yōu)先搜索（DFS）也可用于查找從根結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的路徑。在本文中，我們提供了示例來解釋 DFS 是如何工作的以及棧是如何逐步幫助 DFS 工作的。

示例

我們來看一個(gè)例子吧。我們希望通過 DFS 找出從根結(jié)點(diǎn) A 到目標(biāo)結(jié)點(diǎn) G 的路徑。

洞悉

觀看上面的動(dòng)畫后，讓我們回答以下問題：

1. 結(jié)點(diǎn)的處理順序是什么？

在上面的例子中，我們從根結(jié)點(diǎn) A 開始。首先，我們選擇結(jié)點(diǎn) B 的路徑，并進(jìn)行回溯，直到我們到達(dá)結(jié)點(diǎn) E，我們無法更進(jìn)一步深入。然后我們回溯到 A 并選擇第二條路徑到結(jié)點(diǎn) C 。從 C 開始，我們嘗試第一條路徑到 E 但是 E 已被訪問過。所以我們回到 C 并嘗試從另一條路徑到 F。最后，我們找到了 G。

總的來說，在我們到達(dá)最深的結(jié)點(diǎn)之后，我們只會(huì)回溯并嘗試另一條路徑。

因此，你在 DFS 中找到的第一條路徑并不總是最短的路徑。例如，在上面的例子中，我們成功找出了路徑 A-> C-> F-> G 并停止了 DFS。但這不是從 A 到 G 的最短路徑。

2. 棧的入棧和退棧順序是什么？

如上面的動(dòng)畫所示，我們首先將根結(jié)點(diǎn)推入到棧中；然后我們嘗試第一個(gè)鄰居 B 并將結(jié)點(diǎn) B 推入到棧中；等等等等。當(dāng)我們到達(dá)最深的結(jié)點(diǎn) E 時(shí)，我們需要回溯。當(dāng)我們回溯時(shí)，我們將從棧中彈出最深的結(jié)點(diǎn)，這實(shí)際上是推入到棧中的最后一個(gè)結(jié)點(diǎn)。

結(jié)點(diǎn)的處理順序是完全相反的順序，就像它們被添加到棧中一樣，它是后進(jìn)先出（LIFO）。這就是我們在 DFS 中使用棧的原因。

總結(jié)：

顯然BFS可以找到根節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)最短的路徑，DFS可以最快的找到根節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路線，但卻不一定是最短的。具體可參考維基百科：

BFS：https://zh.wikipedia.org/wiki/廣度優(yōu)先搜索

DFS：https://zh.wikipedia.org/wiki/深度優(yōu)先搜索

歡迎關(guān)注微.信公.眾號：愛寫B(tài)ug

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/76182.html

相關(guān)文章

  • 用JavaScript來學(xué)習(xí)樹「譯」

    摘要：樹可謂是開發(fā)者最常碰到的數(shù)據(jù)結(jié)構(gòu)之一了要知道整張網(wǎng)頁就是一棵樹啊所以我們就來學(xué)習(xí)樹這一數(shù)據(jù)結(jié)構(gòu)吧在這篇文章中我們將創(chuàng)建一棵樹并且用兩種不同的方法來遍歷它深度優(yōu)先遍歷和寬度廣度優(yōu)先遍歷方法使用借助棧這一數(shù)據(jù)結(jié)構(gòu)來訪問樹的每個(gè)節(jié)點(diǎn)則借助了隊(duì) 樹可謂是web開發(fā)者最常碰到的數(shù)據(jù)結(jié)構(gòu)之一了. 要知道, 整張網(wǎng)頁就是一棵DOM樹啊 (Document Object Model ). 所以我...

    Youngdze 評論0 收藏0

  • 算法第四版4.1-無向圖詳解

    摘要：樹是一副無環(huán)連通圖?；ゲ幌噙B的樹組成的集合稱為森林。表示無向圖的數(shù)據(jù)類型圖的基本操作的兩個(gè)構(gòu)造，得到頂點(diǎn)數(shù)和邊數(shù)，增加一條邊。該方法不符合第一個(gè)條件，上百萬個(gè)頂點(diǎn)的圖是很常見的空間不滿足。 四種重要的圖模型： 無向圖（簡單連接） 有向圖（連接有方向性） 加權(quán)圖（連接帶有權(quán)值） 加權(quán)有向圖（連接既有方向性又帶有權(quán)值） 無向圖 定義：由一組頂點(diǎn)和一組能夠?qū)蓚€(gè)頂點(diǎn)相連的邊組成。 特殊：...

    scola666 評論0 收藏0

  • js 中二叉樹的深度遍歷與廣度遍歷(遞歸實(shí)現(xiàn)與非遞歸實(shí)現(xiàn))

    摘要：樹中結(jié)點(diǎn)的最大層次稱為樹的深度或高度。二叉樹有深度遍歷和廣度遍歷，深度遍歷有前序中序和后序三種遍歷方法。二叉樹的前序遍歷可以用來顯示目錄結(jié)構(gòu)等中序遍歷可以實(shí)現(xiàn)表達(dá)式樹，在編譯器底層很有用后序遍歷可以用來實(shí)現(xiàn)計(jì)算目錄內(nèi)的文件及其信息等。 樹的簡介 棧、隊(duì)列、鏈表等數(shù)據(jù)結(jié)構(gòu)，都是順序數(shù)據(jù)結(jié)構(gòu)。而樹是非順序數(shù)據(jù)結(jié)構(gòu)。樹型結(jié)構(gòu)是一類非常重要的非線性結(jié)構(gòu)。直觀地，樹型結(jié)構(gòu)是以分支關(guān)系定義的層次結(jié)...

    Yuanf 評論0 收藏0

  • js版本的BFS&DFS

    摘要：隊(duì)列棧隊(duì)列是先進(jìn)先出，后進(jìn)后出，常用的操作是取第一個(gè)元素尾部加入一個(gè)元素。棧是后進(jìn)先出，就像一個(gè)垃圾桶，后入的垃圾先被倒出來。遍歷中間過程，每一個(gè)節(jié)點(diǎn)入棧的時(shí)候是灰色的，出棧的時(shí)候是黑色的。 0. 前言 廣度優(yōu)先搜索(BFS)和深度優(yōu)先搜索(DFS)，大家可能在oj上見過，各種求路徑、最短路徑、最優(yōu)方法、組合等等。于是，我們不妨動(dòng)手試一下js版本怎么玩。 1.隊(duì)列、棧 隊(duì)列是先進(jìn)先出，...

    劉福 評論0 收藏0

  • [LintCode] Topological Sorting [BFS & DFS]

    摘要：當(dāng)隊(duì)列非空時(shí)，拿出最后放入的元素。若減后入度為，則這個(gè)結(jié)點(diǎn)遍歷完成，放入結(jié)果數(shù)組和隊(duì)列。遞歸函數(shù)去遍歷的，繼續(xù)在中標(biāo)記，使得所有點(diǎn)只遍歷一次。最深的點(diǎn)最先，根結(jié)點(diǎn)最后，加入結(jié)果數(shù)組的頭部處。 Problem Given an directed graph, a topological order of the graph nodes is defined as follow: For ...

    draveness 評論0 收藏0

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<