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