資訊專欄INFORMATION COLUMN
摘要：深度優(yōu)先搜索上一次已經(jīng)提到，圖的遍歷一般有兩種算法，即廣度優(yōu)先和深度優(yōu)先。用深度優(yōu)先搜索算法對圖中的任務(wù)圖進(jìn)行拓?fù)渑判蜃罱K各頂點(diǎn)的發(fā)現(xiàn)和探索完成時(shí)間會保存在中。
深度優(yōu)先搜索（DFS）
上一次已經(jīng)提到，圖的遍歷一般有兩種算法，即廣度優(yōu)先和深度優(yōu)先。其中深度優(yōu)先搜索算法會從第一個(gè)指定的頂點(diǎn)開始遍歷圖，沿著路徑直到這條路徑最后一個(gè)頂點(diǎn)，接著原路回退并探索下一條路徑。換句話說，它是先深度后廣度地訪問頂點(diǎn)，如下圖1。
圖1
與廣度優(yōu)先算法不同，深度優(yōu)先算法不需要一個(gè)起始頂點(diǎn)，只要頂點(diǎn)v沒有被訪問，就訪問該頂點(diǎn)。
我們用三種狀態(tài)來反映頂點(diǎn)的狀態(tài)：
白色：表示該頂點(diǎn)還沒有被訪問。
灰色：表示該頂點(diǎn)被訪問過，但并未被探索過。
黑色：表示該頂點(diǎn)被訪問過且被完全探索過。
訪問某一頂點(diǎn)v的步驟如下：
標(biāo)注v為被發(fā)現(xiàn)的（灰色）
對于v的所有未訪問的鄰點(diǎn)w：訪問頂點(diǎn)w
標(biāo)注v為已被探索的（黑色）
因此深度優(yōu)先搜索的步驟是遞歸的，這意味著深度優(yōu)先搜索算法使用棧來存儲函數(shù)調(diào)用（由遞歸調(diào)用所創(chuàng)建的棧）。
與廣度優(yōu)先算法類似，在算法開始之前，我們需要將所有頂點(diǎn)置為白色（本文的所有代碼都是在圖中實(shí)現(xiàn)的Graph類中添加的）。
function Graph() {
var vertices = [];
var adjList = new Dictionary();
// 圖類的其他代碼省略...
var initializeColor = function(){
var color = [];
for (var i=0; i
接下來實(shí)現(xiàn)深度優(yōu)先算法的核心代碼：
this.dfs = function(callback){
var color = initializeColor(); // 將所有頂點(diǎn)初始化為白色
for (var i=0; i
對圖1中的圖執(zhí)行上述搜索算法的過程如圖2。
圖2
由于我們是從起始點(diǎn)A開始搜索的，{1}處的代碼只會執(zhí)行一次，因?yàn)樗衅渌旤c(diǎn)都有一條路徑到達(dá)A點(diǎn)。如果從B點(diǎn)開始搜索，{1}處的代碼便會執(zhí)行兩次。
搜索時(shí)間
給定一個(gè)圖G，要得到任意頂點(diǎn)u的發(fā)現(xiàn)時(shí)間（d[u]）以及完成對該頂點(diǎn)的搜索時(shí)間（f[u]），可以在上述代碼的基礎(chǔ)上做一定修改（修改的位置用空行隔開）：
this.DFS = function(){
var color = initializeColor(), //{2}
len = vertices.length,
d = new Array(len).fill([]), // 用于保存任意頂點(diǎn)u的發(fā)現(xiàn)時(shí)間
f = new Array(len).fill([]), // 用于保存任意頂點(diǎn)u探索完成的時(shí)
time = 0; // 用于記錄探索時(shí)間
for (var i=0; i
對于深度優(yōu)先算法，邊是從最近發(fā)現(xiàn)的頂點(diǎn)u處被向外探索的。只有連接到未發(fā)現(xiàn)的頂點(diǎn)的邊被探索了。當(dāng)u所有的邊都被探索了，該算法回退到u被發(fā)現(xiàn)的地方去探索其他的邊。這個(gè)過程持續(xù)到我們發(fā)現(xiàn)了所有從原始頂點(diǎn)能夠觸及的頂點(diǎn)。如果還留有任何其他未被發(fā)現(xiàn)的頂點(diǎn)，我們對新源頂點(diǎn)重復(fù)這個(gè)過程。重復(fù)該算法，直到圖中所有的頂點(diǎn)都被探索了。
觀察上述代碼可以發(fā)現(xiàn)，time的值只能在圖的頂點(diǎn)數(shù)量的一到兩倍之間，并且d[u]
拓?fù)渑判?/b>
給定圖3，假定每個(gè)頂點(diǎn)都是一個(gè)我們需要去執(zhí)行的任務(wù)。
圖3
這是一個(gè)有向無環(huán)圖（DAG），即任務(wù)的執(zhí)行是有順序的，例如，任務(wù)F不能在任務(wù)A之前執(zhí)行，并且該圖沒有環(huán)。
當(dāng)我們需要編排一些任務(wù)或步驟的執(zhí)行順序時(shí)，這稱為拓?fù)渑判?/strong>。比如，當(dāng)我們在開發(fā)一個(gè)項(xiàng)目時(shí)，首先我們得從客戶那里得到需求，接著開發(fā)客戶要求的東西，最后交付項(xiàng)目，但不能先交付項(xiàng)目再去收集需求。
拓?fù)渑判蛑荒軕?yīng)用于DAG。用深度優(yōu)先搜索算法對圖3中的任務(wù)圖進(jìn)行拓?fù)渑判颍?/p>
graph = new Graph();
myVertices = ["A","B","C","D","E","F"];
for (i=0; i
最終各頂點(diǎn)的發(fā)現(xiàn)和探索完成時(shí)間會保存在result中。圖4直觀地注明了各個(gè)頂點(diǎn)的發(fā)現(xiàn)時(shí)間/探索完成時(shí)間。
圖4
那么按照探索完成時(shí)間的倒序來排序得到的拓?fù)渑判驗(yàn)椋?br>B - A - D - C - F - E
需要注意的是，算法不同，得到的拓?fù)渑判蚩赡懿煌?，比如下面的拓?fù)渑判蛞彩强赡艿模?br>A - B - C - D - F - E
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://hztianpu.com/yun/91881.html
摘要：圖關(guān)聯(lián)矩陣在關(guān)聯(lián)矩陣表示的圖中，矩陣的行表示頂點(diǎn)，列表示邊。如圖，頂點(diǎn)數(shù)是，邊的數(shù)量是，用鄰接矩陣表示圖需要的空間是，而使用關(guān)聯(lián)矩陣表示圖需要的空間是。廣度優(yōu)先搜索算法數(shù)據(jù)結(jié)構(gòu)是隊(duì)列。深度優(yōu)先搜索算法數(shù)據(jù)結(jié)構(gòu)是棧。 定義 圖和散列表、二叉樹一樣，是一種非線性數(shù)據(jù)結(jié)構(gòu)。如圖1所示，圖由一系列頂點(diǎn)以及連接頂點(diǎn)的邊構(gòu)成。由一條邊連接在一起的頂點(diǎn)成為相鄰頂點(diǎn)，比如A和B、A和D是相鄰的，而A和...
摘要：廣度優(yōu)先搜索上一次已經(jīng)提到，圖的遍歷一般有兩種算法，即廣度優(yōu)先和深度優(yōu)先。其中廣度優(yōu)先搜索算法會從指定的第一個(gè)頂點(diǎn)開始遍歷圖，先訪問其所有的相鄰點(diǎn)，就像一次訪問圖的一層。其它最短路徑算法對于加權(quán)圖的最短路徑，廣度優(yōu)先算法可能并不合適。 廣度優(yōu)先搜索（BFS） 上一次已經(jīng)提到，圖的遍歷一般有兩種算法，即廣度優(yōu)先和深度優(yōu)先。其中廣度優(yōu)先搜索算法會從指定的第一個(gè)頂點(diǎn)開始遍歷圖，先訪問其所有的...
摘要：散列表上面的地圖向我們展示了如何用廣度優(yōu)先搜索的思想找到北京到廣州的最短路線。在廣度優(yōu)先搜索中，我們需要用到隊(duì)列的這種思想來實(shí)現(xiàn)查找。建立了下面這個(gè)模型武漢廣州西藏上海上海武漢廣州代碼完整實(shí)現(xiàn)，利用遞歸和廣度優(yōu)先搜索的思想實(shí)現(xiàn)。 什么是廣度優(yōu)先搜索？ 如果只是是背概念，幼兒園的小朋友都能背下來念給你聽。 假設(shè)看這篇文章的都和我一樣是個(gè)前端工程師，我們要從廣度優(yōu)先搜索（BFS）中學(xué)到什么...
摘要：達(dá)觀數(shù)據(jù)招人啦面向北京上海深圳成都四個(gè)地區(qū)提供人工智能算法產(chǎn)品銷售等多類崗位畢業(yè)多年，你的狀態(tài)還好嗎是否憂慮被甩在時(shí)代的邊緣是否擔(dān)心被機(jī)器取代是否不安現(xiàn)狀躍躍欲試來吧，選擇對的行業(yè)，與優(yōu)秀的人一起共事，與我們一起走在時(shí)代的風(fēng)口上，從事當(dāng)下最 showImg(https://segmentfault.com/img/bVbeHrX?w=720&h=400);達(dá)觀數(shù)據(jù)招人啦！ 面向北京、上...
閱讀 3084·2021-10-15 09:41
閱讀 1734·2021-09-22 15:56
閱讀 2209·2021-08-10 09:43
閱讀 3367·2019-08-30 13:56
閱讀 1891·2019-08-30 12:47
閱讀 746·2019-08-30 11:17
閱讀 2906·2019-08-30 11:09
閱讀 2253·2019-08-29 16:19
