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