讀古今文學網 > 學習JavaScript數據結構與算法（第2版） > 9.4 圖的遍歷 >

9.4 圖的遍歷

和樹數據結構類似，我們可以訪問圖的所有節點。有兩種算法可以對圖進行遍歷：廣度優先搜索（Breadth-First Search，BFS）和深度優先搜索（Depth-First Search，DFS）。圖遍歷可以用來尋找特定的頂點或尋找兩個頂點之間的路徑，檢查圖是否連通，檢查圖是否含有環等。

在實現算法之前，讓我們來更好地理解一下圖遍歷的思想方法。

圖遍歷算法的思想是必須追蹤每個第一次訪問的節點，並且追蹤有哪些節點還沒有被完全探索。對於兩種圖遍歷算法，都需要明確指出第一個被訪問的頂點。

完全探索一個頂點要求我們查看該頂點的每一條邊。對於每一條邊所連接的沒有被訪問過的頂點，將其標注為被發現的，並將其加進待訪問頂點列表中。

為了保證算法的效率，務必訪問每個頂點至多兩次。連通圖中每條邊和頂點都會被訪問到。

廣度優先搜索算法和深度優先搜索算法基本上是相同的，只有一點不同，那就是待訪問頂點列表的數據結構。

算法

數據結構

描述

深度優先搜索

棧

通過將頂點存入棧中（在第3章中學習過），頂點是沿著路徑被探索的，存在新的相鄰頂點就去訪問

廣度優先搜索

隊列

通過將頂點存入隊列中（在第4章中學習過），最先入隊列的頂點先被探索

當要標注已經訪問過的頂點時，我們用三種顏色來反映它們的狀態。

  • 白色：表示該頂點還沒有被訪問。

  • 灰色：表示該頂點被訪問過，但並未被探索過。

  • 黑色：表示該頂點被訪問過且被完全探索過。

這就是之前提到的務必訪問每個頂點最多兩次的原因。

9.4.1　廣度優先搜索

廣度優先搜索算法會從指定的第一個頂點開始遍歷圖，先訪問其所有的相鄰點，就像一次訪問圖的一層。換句話說，就是先寬後深地訪問頂點，如下圖所示：

以下是從頂點v開始的廣度優先搜索算法所遵循的步驟。

(1) 創建一個隊列Q。

(2) 將v 標注為被發現的（灰色），並將v入隊列Q。

(3) 如果Q非空，則運行以下步驟：

　　(a) 將u從Q中出隊列；

　　(b) 將標注u為被發現的（灰色）；

　　(c) 將u 所有未被訪問過的鄰點（白色）入隊列；

　　(d) 將u 標注為已被探索的（黑色）。

讓我們來實現廣度優先搜索算法： 

var initializeColor = function{
  var color = ;
  for (var i=0; i<vertices.length; i++){
    color[vertices[i]] = 'white'; //{1}
  }
  return color;
};

this.bfs = function(v, callback){

  var color = initializeColor,  //{2}
  queue = new Queue;        //{3}
  queue.enqueue(v);               //{4}

  while (!queue.isEmpty){       //{5}
    var u = queue.dequeue,   //{6}
    neighbors = adjList.get(u); //{7}
    color[u] = 'grey';                      // {8}
    for (var i=0; i<neighbors.length; i++){ // {9}
      var w = neighbors[i];               // {10}
      if (color[w] === 'white'){          // {11}
        color[w] = 'grey';              // {12}
        queue.enqueue(w);               // {13}
      }
    }
    color[u] = 'black'; // {14}
    if (callback) {     // {15}
      callback(u);
    }
  }
};

廣度優先搜索和深度優先搜索都需要標注被訪問過的頂點。為此，我們將使用一個輔助數組color。由於當算法開始執行時，所有的頂點顏色都是白色（行{1}），所以我們可以創建一個輔助函數initializeColor，為這兩個算法執行此初始化操作。

讓我們深入學習廣度優先搜索方法的實現。我們要做的第一件事情是用initializeColor函數來將color數組初始化為white（行{2}）。我們還需要聲明和創建一個Queue實例（行{3}），它將會存儲待訪問和待探索的頂點。

照著本章開頭解釋過的步驟，bfs方法接受一個頂點作為算法的起始點。起始頂點是必要的，我們將此頂點入隊列（行{4}）。

如果隊列非空（行{5}），我們將通過出隊列（行{6}）操作從隊列中移除一個頂點，並取得一個包含其所有鄰點的鄰接表（行{7}）。該頂點將被標注為grey（行{8}），表示我們發現了它（但還未完成對其的探索）。

對於u（行{9}）的每個鄰點，我們取得其值（該頂點的名字——行{10}），如果它還未被訪問過（顏色為white——行{11}），則將其標注為我們已經發現了它（顏色設置為grey——行{12}），並將這個頂點加入隊列中（行{13}），這樣當其從隊列中出列的時候，我們可以完成對其的探索。

當完成探索該頂點和其相鄰頂點後，我們將該頂點標注為已探索過的（顏色設置為black——行{14}）。

我們實現的這個bfs方法也接受一個回調（我們在第8章中遍歷樹時使用了一個相似的方法）。這個參數是可選的，如果我們傳遞了回調函數（行{15}），會用到它。

讓我們執行下面這段代碼來測試一下這個算法： 

function printNode(value){ //{16}
  console.log('Visited vertex: ' + value); //{17}
}
graph.bfs(myVertices[0], printNode); //{18}

首先，我們聲明了一個回調函數（行{16}），它僅僅在瀏覽器控制台上輸出已經被完全探索過的頂點的名字。接著，我們會調用bfs方法，給它傳遞第一個頂點（A——從本章開頭聲明的myVertices數組）和回調函數。當我們執行這段代碼時，該算法會在瀏覽器控制台輸出下示的結果： 

Visited vertex: A
Visited vertex: B
Visited vertex: C
Visited vertex: D
Visited vertex: E
Visited vertex: F
Visited vertex: G
Visited vertex: H
Visited vertex: I

如你所見，頂點被訪問的順序和本節開頭的示意圖中所展示的一致。

  1. 使用BFS尋找最短路徑

    到目前為止，我們只展示了BFS算法的工作原理。我們可以用該算法做更多事情，而不只是輸出被訪問頂點的順序。例如，考慮如何來解決下面這個問題。

    給定一個圖G 和源頂點v，找出對每個頂點u，u和v之間最短路徑的距離（以邊的數量計）。

    對於給定頂點v，廣度優先算法會訪問所有與其距離為1的頂點，接著是距離為2的頂點，以此類推。所以，可以用廣度優先算法來解這個問題。我們可以修改bfs方法以返回給我們一些信息：

    • 從v 到u 的距離d[u]；

    • 前溯點pred[u]，用來推導出從v 到其他每個頂點u 的最短路徑。

    讓我們來看看改進過的廣度優先方法的實現： 

    this.BFS = function(v){
    　
  var color = initializeColor,
  queue = new Queue,
  d = ,    //{1}
  pred = ; //{2}
  queue.enqueue(v);
    　
  for (var i=0; i<vertices.length; i++){ //{3}
    d[vertices[i]] = 0;                //{4}
    pred[vertices[i]] = null;          //{5}
  }
    　
  while (!queue.isEmpty){
    var u = queue.dequeue,
    neighbors = adjList.get(u);
    color[u] = 'grey';
    for (i=0; i<neighbors.length; i++){
      var w = neighbors[i];
      if (color[w] === 'white'){
        color[w] = 'grey';
        d[w] = d[u] + 1;           //{6}
        pred[w] = u;               //{7}
        queue.enqueue(w);
      }
    }
    color[u] = 'black';
  }
  return { //{8}
    distances: d,
    predecessors: pred
  };
};

    這個版本的BFS方法有些什麼改變？

    　本章源代碼中包含兩個bfs方法：bfs（第一個）和BFS（改進版）。

    我們還需要聲明數組d（行{1}）來表示距離，以及pred數組來表示前溯點。下一步則是對圖中的每一個頂點，用0來初始化數組d（行{4}），用null來初始化數組pred。

    當我們發現頂點u的鄰點w時，則設置w的前溯點值為u（行{7}）。我們還通過給d[u]加1來設置v和w之間的距離（u是w的前溯點，d[u]的值已經有了）。

    方法最後返回了一個包含d和pred的對象（行{8}）。

    現在，我們可以再次執行BFS方法，並將其返回值存在一個變量中： 

    var shortestPathA = graph.BFS(myVertices[0]);
console.log(shortestPathA);

    對頂點A執行BFS方法，以下將會是輸出： 

    distances: [A: 0, B: 1, C: 1, D: 1, E: 2, F: 2, G: 2, H: 2 , I: 3],
predecessors: [A: null, B: "A", C: "A", D: "A", E: "B", F: "B", G: "C", H: "D", I: "E"]

    這意味著頂點A與頂點B、C和D的距離為1；與頂點E、F、G和H的距離為2；與頂點I的距離為3。

    通過前溯點數組，我們可以用下面這段代碼來構建從頂點A到其他頂點的路徑： 

    var fromVertex = myVertices[0]; //{9}
for (var i=1; i<myVertices.length; i++){ //{10}
  var toVertex = myVertices[i], //{11}
  path = new Stack;       //{12}
  for (var v=toVertex; v!== fromVertex;
  v=shortestPathA.predecessors[v]) { //{13}
    path.push(v);                          //{14}
  }
  path.push(fromVertex);        //{15}
  var s = path.pop;           //{16}
  while (!path.isEmpty){      //{17}
    s += ' - ' + path.pop;  //{18}
  }
  console.log(s); //{19}
}

    我們用頂點A作為源頂點（行{9}）。對於每個其他頂點（除了頂點A——行{10}），我們會計算頂點A到它的路徑。我們從頂點數組得到toVertex（行{11}），然後會創建一個棧來存儲路徑值（行{12}）。

    接著，我們追溯toVertex到fromVertex的路徑（行{13}）。變量v被賦值為其前溯點的值，這樣我們能夠反向追溯這條路徑。將變量v添加到棧中（行{14}）。最後，源頂點也會被添加到棧中，以得到完整路徑。

    這之後，我們創建了一個s字符串，並將源頂點賦值給它（它是最後一個加入棧中的，所以它是第一個被彈出的項 ——行{16}）。當棧是非空的，我們就從棧中移出一個項並將其拼接到字符串s的後面（行{18}）。最後（行{19}）在控制台上輸出路徑。

    執行該代碼段，我們會得到如下輸出： 

    A - B
A - C
A - D
A - B - E
A - B - F
A - C - G
A - D - H
A - B - E - I

    這裡，我們得到了從頂點A到圖中其他頂點的最短路徑（衡量標準是邊的數量）。

  2. 深入學習最短路徑算法

    本章中的圖不是加權圖。如果要計算加權圖中的最短路徑（例如，城市A和城市B之間的最短路徑——GPS和Google Maps中用到的算法），廣度優先搜索未必合適。

    舉些例子，Dijkstra算法解決了單源最短路徑問題。Bellman-Ford算法解決了邊權值為負的單源最短路徑問題。A*搜索算法解決了求僅一對頂點間的最短路徑問題，它用經驗法則來加速搜索過程。Floyd-Warshall算法解決了求所有頂點對間的最短路徑這一問題。

    如本章開頭提到的，圖是一個廣泛的主題，對最短路徑問題及其變種問題，我們有很多的解決方案。但在開始學習這些其他解決方案前，我們需要掌握好圖的基本概念，這是本章涵蓋的內容。而這些其他解決方案則不會在本章講述，但你可以自行探索圖的奇妙世界。

9.4.2　深度優先搜索

深度優先搜索算法將會從第一個指定的頂點開始遍歷圖，沿著路徑直到這條路徑最後一個頂點被訪問了，接著原路回退並探索下一條路徑。換句話說，它是先深度後廣度地訪問頂點，如下圖所示：

深度優先搜索算法不需要一個源頂點。在深度優先搜索算法中，若圖中頂點v 未訪問，則訪問該頂點v。

要訪問頂點v，照如下步驟做。

(1) 標注v為被發現的（灰色）。

(2) 對於v 的所有未訪問的鄰點w，訪問頂點w，標注v為已被探索的（黑色）。

如你所見，深度優先搜索的步驟是遞歸的，這意味著深度優先搜索算法使用棧來存儲函數調用（由遞歸調用所創建的棧）。

讓我們來實現一下深度優先算法： 

this.dfs = function(callback){
  var color = initializeColor; //{1}

  for (var i=0; i<vertices.length; i++){ //{2}
    if (color[vertices[i]] === 'white'){ //{3}
      dfsVisit(vertices[i], color, callback); //{4}
    }
  }
};

var dfsVisit = function(u, color, callback){
  color[u] = 'grey'; //{5}
  if (callback) {    //{6}
    callback(u);
  }
  var neighbors = adjList.get(u);         //{7}
  for (var i=0; i<neighbors.length; i++){ //{8}
    var w = neighbors[i];               //{9}
    if (color[w] === 'white'){          //{10}
      dfsVisit(w, color, callback);   //{11}
    }
  }
  color[u] = 'black'; //{12}
};

首先，我們創建顏色數組（行{1}），並用值white為圖中的每個頂點對其做初始化，廣度優先搜索也這麼做的。接著，對於圖實例中每一個未被訪問過的頂點（行{2}和{3}），我們調用私有的遞歸函數dfsVisit，傳遞的參數為頂點、顏色數組以及回調函數（行{4}）。

當訪問u頂點時，我們標注其為被發現的（grey——行{5}）。如果有callback函數的話（行{6}），則執行該函數輸出已訪問過的頂點。接下來一步是取得包含頂點u所有鄰點的列表（行{7}）。對於頂點u的每一個未被訪問過（顏色為white——行{10}和行{8}）的鄰點w（行{9}），我們將調用dfsVisit函數，傳遞w和其他參數（行{11}——添加頂點w入棧，這樣接下來就能訪問它）。最後，在該頂點和鄰點按深度訪問之後，我們回退，意思是該頂點已被完全探索，並將其標注為black（行{12}）。

讓我們執行下面的代碼段來測試一下dfs方法： 

graph.dfs(printNode);

輸出如下： 

Visited vertex: A
Visited vertex: B
Visited vertex: E
Visited vertex: I
Visited vertex: F
Visited vertex: C
Visited vertex: D
Visited vertex: G
Visited vertex: H

這個順序和本節開頭處示意圖所展示的一致。下面這個示意圖展示了該算法每一步的執行過程：

在我們示例所用的圖中，行{4}只會被執行一次，因為所有其他的頂點都有路徑到第一個調用dfsVisit函數的頂點（頂點A）。如果頂點B第一個調用函數，則行{4}將會為其他頂點再執行一次（比如頂點A）。

  1. 探索深度優先算法

    到目前為止，我們只是展示了深度優先搜索算法的工作原理。我們可以用該算法做更多的事情，而不只是輸出被訪問頂點的順序。

    對於給定的圖G，我們希望深度優先搜索算法遍歷圖G的所有節點，構建「森林」（有根樹的一個集合）以及一組源頂點（根），並輸出兩個數組：發現時間和完成探索時間。我們可以修改dfs方法來返回給我們一些信息：

    • 頂點u 的發現時間d[u]；

    • 當頂點u 被標注為黑色時，u 的完成探索時間f [u]；

    • 頂點u 的前溯點p[u]。

    讓我們來看看改進了的DFS方法的實現： 

    var time = 0; //{1}
this.DFS = function{
  var color = initializeColor, //{2}
  d = ,
  f = ,
  p = ;
  time = 0;
    　
  for (var i=0; i<vertices.length; i++){ //{3}
    f[vertices[i]] = 0;
    d[vertices[i]] = 0;
    p[vertices[i]] = null;
  }
  for (i=0; i<vertices.length; i++){
    if (color[vertices[i]] === 'white'){
      DFSVisit(vertices[i], color, d, f, p);
    }
  }
  return {           //{4}
    discovery: d,
    finished: f,
    predecessors: p
  };
};
    　
var DFSVisit = function(u, color, d, f, p){
  console.log('discovered ' + u);
  color[u] = 'grey';
  d[u] = ++time; //{5}
  var neighbors = adjList.get(u);
  for (var i=0; i<neighbors.length; i++){
    var w = neighbors[i];
    if (color[w] === 'white'){
      p[w] = u;                        // {6}
      DFSVisit(w,color, d, f, p);
    }
  }
  color[u] = 'black';
  f[u] = ++time;      //{7}
  console.log('explored ' + u);
};

    我們需要一個變量來要追蹤發現時間和完成探索時間（行{1}）。時間變量不能被作為參數傳遞，因為非對象的變量不能作為引用傳遞給其他JavaScript方法（將變量作為引用傳遞的意思是如果該變量在其他方法內部被修改，新值會在原始變量中反映出來）。接下來，我們聲明數組d、f和p（行{2}）。我們需要為圖的每一個頂點來初始化這些數組（行{3}）。在這個方法結尾處返回這些值（行{4}），之後我們要用到它們。

    當一個頂點第一次被發現時，我們追蹤其發現時間（行{5}）。當它是由引自頂點u的邊而被發現的，我們追蹤它的前溯點（行{6}）。最後，當這個頂點被完全探索後，我們追蹤其完成時間（行 {7}）。

    深度優先算法背後的思想是什麼？邊是從最近發現的頂點u 處被向外探索的。只有連接到未發現的頂點的邊被探索了。當u 所有的邊都被探索了，該算法回退到u 被發現的地方去探索其他的邊。這個過程持續到我們發現了所有從原始頂點能夠觸及的頂點。如果還留有任何其他未被發現的頂點，我們對新源頂點重複這個過程。重複該算法，直到圖中所有的頂點都被探索了。

    對於改進過的深度優先搜索，有兩點需要我們注意：

    • 時間（time）變量值的範圍只可能在圖頂點數量的一倍到兩倍之間；

    • 對於所有的頂點u，d[u]<f[u]（意味著，發現時間的值比完成時間的值小，完成時間意思是所有頂點都已經被探索過了）。

    在這兩個假設下，我們有如下的規則：

    1 ≤ d[u] < f[u] ≤ 2|V|

    如果對同一個圖再跑一遍新的深度優先搜索方法，對圖中每個頂點，我們會得到如下的發現/完成時間：

    但我們能用這些新信息來做什麼呢？來看下一節。

  2. 拓撲排序——使用深度優先搜索

    給定下圖，假定每個頂點都是一個我們需要去執行的任務：

    　這是一個有向圖，意味著任務的執行是有順序的。例如，任務F 不能在任務A之前執行。注意這個圖沒有環，意味著這是一個無環圖。所以，我們可以說該圖是一個有向無環圖（DAG）。

    當我們需要編排一些任務或步驟的執行順序時，這稱為拓撲排序（topological sorting，英文亦寫作topsort或是toposort）。在日常生活中，這個問題在不同情形下都會出現。例如，當我們開始學習一門計算機科學課程，在學習某些知識之前得按順序完成一些知識儲備（你不可以在上算法I前先上算法II）。當我們在開發一個項目時，需要按順序執行一些步驟，例如，首先我們得從客戶那裡得到需求，接著開發客戶要求的東西，最後交付項目。你不能先交付項目再去收集需求。

    拓撲排序只能應用於DAG。那麼，如何使用深度優先搜索來實現拓撲排序呢？讓我們在本節開頭的示意圖上執行一下深度優先搜索。 

    graph = new Graph;
myVertices = ['A','B','C','D','E','F'];
for (i=0; i<myVertices.length; i++){
  graph.addVertex(myVertices[i]);
}
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('B', 'D');
graph.addEdge('B', 'E');
graph.addEdge('C', 'F');
graph.addEdge('F', 'E');
var result = graph.DFS;

    這段代碼將創建圖，添加邊，執行改進版本的深度優先搜索算法，並將結果保存到result變量。下圖展示了深度優先搜索算法執行後，該圖的發現和完成時間。

    現在要做的僅僅是以倒序來排序完成時間數組，這便得出了該圖的拓撲排序： 

    B - A - D - C - F - E

    注意之前的拓撲排序結果僅是多種可能性之一。如果我們稍微修改一下算法，就會有不同的結果，比如下面這個結果也是眾多其他可能性中的一個： 

    A - B - C - D - F - E

    這也是一個可以接受的結果。

    學習JavaScript數據結構與算法（第2版）