成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專(zhuān)欄INFORMATION COLUMN

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

Kyxy / 1634人閱讀

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

隊(duì)列和 BFS：

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

示例

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

洞悉

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

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

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

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

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

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

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

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

棧和 DFS：

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

示例

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

洞悉

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

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

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

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

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

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

如上面的動(dòng)畫(huà)所示，我們首先將根結(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）。這就是我們?cè)?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)注微.信公.眾號(hào)：愛(ài)寫(xiě)B(tài)ug

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/76182.html

相關(guān)文章

  • 用JavaScript來(lái)學(xué)習(xí)樹(shù)「譯」

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

    Youngdze 評(píng)論0 收藏0

  • 算法第四版4.1-無(wú)向圖詳解

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

    scola666 評(píng)論0 收藏0

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

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

    Yuanf 評(píng)論0 收藏0

  • js版本的BFS&DFS

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

    劉福 評(píng)論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 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

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