JavaScript數據結構——圖的實現
- 2019 年 10 月 3 日
- 筆記
在電腦科學中，圖是一種網路結構的抽象模型，它是一組由邊連接的頂點組成。一個圖G = (V, E)由以下元素組成：
- V：一組頂點
- E：一組邊，連接V中的頂點
下圖表示了一個圖的結構：
在介紹如何用JavaScript實現圖之前，我們先介紹一些和圖相關的術語。
如上圖所示，由一條邊連接在一起的頂點稱為相鄰頂點，A和B是相鄰頂點，A和D是相鄰頂點，A和C是相鄰頂點……A和E是不相鄰頂點。一個頂點的度是其相鄰頂點的數量，A和其它三個頂點相連，所以A的度為3，E和其它兩個頂點相連，所以E的度為2……路徑是一組相鄰頂點的連續序列，如上圖中包含路徑ABEI、路徑ACDG、路徑ABE、路徑ACDH等。簡單路徑要求路徑中不包含有重複的頂點，如果將環的最後一個頂點去掉，它也是一個簡單路徑。例如路徑ADCA是一個環，它不是一個簡單路徑，如果將路徑中的最後一個頂點A去掉，那麼它就是一個簡單路徑。如果圖中不存在環，則稱該圖是無環的。如果圖中任何兩個頂點間都存在路徑，則該圖是連通的，如上圖就是一個連通圖。如果圖的邊沒有方向，則該圖是無向圖，上圖所示為無向圖，反之則稱為有向圖，下圖所示為有向圖：
在有向圖中，如果兩個頂點間在雙向上都存在路徑，則稱這兩個頂點是強連通的，如上圖中C和D是強連通的，而A和B是非強連通的。如果有向圖中的任何兩個頂點間在雙向上都存在路徑，則該有向圖是強連通的，非強連通的圖也稱為稀疏圖。
此外，圖還可以是加權的。前面我們看到的圖都是未加權的，下圖為一個加權的圖：
可以想像一下，前面我們介紹的樹和鏈表也屬於圖的一種特殊形式。圖在電腦科學中的應用十分廣泛，例如我們可以搜索圖中的一個特定頂點或一條特定的邊，或者尋找兩個頂點間的路徑以及最短路徑，檢測圖中是否存在環等等。
存在多種不同的方式來實現圖的數據結構，下面介紹幾種常用的方式。
鄰接矩陣
在鄰接矩陣中，我們用一個二維數組來表示圖中頂點之間的連接，如果兩個頂點之間存在連接，則這兩個頂點對應的二維數組下標的元素的值為1，否則為0。下圖是用鄰接矩陣方式表示的圖：
如果是加權的圖，我們可以將鄰接矩陣中二維數組裡的值1改成對應的加權數。鄰接矩陣方式存在一個缺點，如果圖是非強連通的，則二維數組中會有很多的0，這表示我們使用了很多的存儲空間來表示根本不存在的邊。另一個缺點就是當圖的頂點發生改變時，對於二維數組的修改會變得不太靈活。
鄰接表
圖的另外一種實現方式是鄰接表，它是對鄰接矩陣的一種改進。鄰接表由圖中每個頂點的相鄰頂點列表所組成。如下圖所示，我們可以用數組、鏈表、字典或散列表來表示鄰接表。
關聯矩陣
我們還可以用關聯矩陣來表示圖。在關聯矩陣中，矩陣的行表示頂點，列表示邊。關聯矩陣通常用於邊的數量比頂點多的情況下，以節省存儲空間。如下圖所示為關聯矩陣方式表示的圖：
下面我們重點看下如何用鄰接表的方式表示圖。我們的Graph類的骨架如下，它用鄰接表方式來實現無向圖：
class Graph { constructor () { this.vertices = []; // 用來存放圖中的頂點 this.adjList = new Dictionary(); // 用來存放圖中的邊 } // 向圖中添加一個新頂點 addVertex (v) {} // 向圖中添加a和b兩個頂點之間的邊 addEdge (a, b) {} }
在Graph類中，我們用數組vertices來保存圖中的所有頂點，用字典（請參考《JavaScript數據結構——字典和散列表的實現》一文中的Dictionary類）adjList來保存圖中每一個頂點到相鄰頂點的關係列表，在字典中，頂點被作為鍵值。請參考前面我們給出的鄰接表的示意圖。然後在Graph類中，我們提供兩個方法，方法addVertex()用來向圖中添加一個新頂點，方法addEdge()用來向圖中添加給定的頂點a和頂點b之間的邊。讓我們來看下這兩個方法的實現。
addVertex (v) { if (!this.vertices.includes(v)) { this.vertices.push(v); this.adjList.set(v, []); } }
要添加一個新頂點，首先要判斷該頂點在圖中是否已經存在了，如果已經存在則不能添加。如果不存在，就在vertices數組中添加一個新元素，然後在字典adjList中添加一個以該頂點作為key的新元素，值為空數組。
addEdge (a, b) { // 如果圖中沒有頂點a，先添加頂點a if (!this.adjList.has(a)) { this.addVertex(a); } // 如果圖中沒有頂點b，先添加頂點b if (!this.adjList.has(b)) { this.addVertex(b); } this.adjList.get(a).push(b); // 在頂點a中添加指向頂點b的邊 this.adjList.get(b).push(a); // 在頂點b中添加指向頂點a的邊 }
addEdge()方法也很簡單，首先要確保給定的兩個頂點a和b在圖中必須存在，如果不存在，則調用addVertex()方法進行添加，然後分別在字典中找到鍵值為頂點a和鍵值為頂點b的元素，在對應的值中添加一個新元素。
下面是Graph類的完整程式碼，其中的toString()方法是為了我們測試用的，它的存在不是必須的。
1 class Graph { 2 constructor () { 3 this.vertices = []; // 用來存放圖中的頂點 4 this.adjList = new Dictionary(); // 用來存放圖中的邊 5 } 6 7 // 向圖中添加一個新頂點 8 addVertex (v) { 9 if (!this.vertices.includes(v)) { 10 this.vertices.push(v); 11 this.adjList.set(v, []); 12 } 13 } 14 15 // 向圖中添加a和b兩個頂點之間的邊 16 addEdge (a, b) { 17 // 如果圖中沒有頂點a，先添加頂點a 18 if (!this.adjList.has(a)) { 19 this.addVertex(a); 20 } 21 // 如果圖中沒有頂點b，先添加頂點b 22 if (!this.adjList.has(b)) { 23 this.addVertex(b); 24 } 25 26 this.adjList.get(a).push(b); // 在頂點a中添加指向頂點b的邊 27 this.adjList.get(b).push(a); // 在頂點b中添加指向頂點a的邊 28 } 29 30 // 獲取圖的vertices 31 getVertices () { 32 return this.vertices; 33 } 34 35 // 獲取圖中的adjList 36 getAdjList () { 37 return this.adjList; 38 } 39 40 toString() { 41 let s = ''; 42 this.vertices.forEach((v) => { 43 s += `${v} -> `; 44 this.adjList.get(v).forEach((n) => { 45 s += `${n} `; 46 }); 47 s += 'n'; 48 }); 49 return s; 50 } 51 }
Graph
對於本文一開始給出的圖，我們添加下面的測試用例：
let graph = new Graph(); let myVertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']; myVertices.forEach((v) => { graph.addVertex(v); }); graph.addEdge('A', 'B'); graph.addEdge('A', 'C'); graph.addEdge('A', 'D'); graph.addEdge('C', 'D'); graph.addEdge('C', 'G'); graph.addEdge('D', 'G'); graph.addEdge('D', 'H'); graph.addEdge('B', 'E'); graph.addEdge('B', 'F'); graph.addEdge('E', 'I'); console.log(graph.toString());
下面是測試結果：
A -> B C D B -> A E F C -> A D G D -> A C G H E -> B I F -> B G -> C D H -> D I -> E
可以看到，與示意圖是相符合的。
和樹類似，我們也可以對圖進行遍歷，以訪問圖中的所有頂點。圖的遍歷方式分為兩種：廣度優先（Breadth-First Search，BFS）和深度優先（Depth-First Search，DFS）。對圖的遍歷可以用來尋找特定的頂點或兩個頂點之間的最短路徑，以及檢查圖是否連通、圖中是否含有環等。
| 演算法 | 數據結構 | 描述 |
| 深度優先 | 棧 | 將圖的頂點存入棧中（有關棧的介紹可以參考《JavaScript數據結構——棧的實現與應用》），頂點是沿著路徑被探索的，存在新的相鄰頂點就去訪問。 |
| 廣度優先 | 隊列 | 將圖的頂點存入隊列中（有關隊列的介紹可以參考《JavaScript數據結構——隊列的實現與應用》），最先入隊列的頂點先被探索。 |
在接下來要實現的演算法中，我們按照如下的約定對圖中的頂點進行遍歷，每個頂點最多訪問兩次：
- 白色：表示該頂點未被訪問。
- 灰色：表示該頂點被訪問過，但未被探索。
- 黑色：表示該頂點被訪問並且被探索過。
廣度優先
廣度優先演算法會從指定的第一個頂點開始遍歷圖，先訪問這個頂點的所有相鄰頂點，然後再訪問這些相鄰頂點的相鄰頂點，以此類推。最終，廣度優先演算法會先廣後深地訪問圖中的所有頂點。下面是廣度優先遍歷的示意圖：
由於我們採用鄰接表的方式來存儲圖的數據，對於圖的每個頂點，都有一個字典與之對應，字典的鍵值為頂點的值，字典的內容為與該頂點相鄰的頂點列表。基於這種數據結構，我們可以考慮將所有頂點的鄰接頂點存入隊列，然後依次處理隊列中的頂點。下面是具體的遍歷步驟：
- 將開始頂點存入隊列。
- 遍歷開始頂點的所有鄰接頂點，如果這些鄰接頂點沒有被訪問過（顏色為白色），則將它們標記為被訪問（顏色為灰色），然後加入隊列。
- 將開始頂點標記為被處理（顏色為黑色）。
- 循環處理隊列中的頂點，直到隊列為空。
下面是該演算法的具體實現：
let Colors = { WHITE: 0, GREY: 1, BLACK: 2 }; let initializeColor = vertices => { let color = {}; vertices.forEach(v => color[v] = Colors.WHITE); return color; }; let breadthFirstSearch = (graph, startVertex, callback) => { let vertices = graph.getVertices(); let adjList = graph.getAdjList(); let color = initializeColor(vertices); let queue = new Queue(); queue.enqueue(startVertex); while (!queue.isEmpty()) { let u = queue.dequeue(); adjList.get(u).forEach(n => { if (color[n] === Colors.WHITE) { color[n] = Colors.GREY; queue.enqueue(n); } }); color[u] = Colors.BLACK; if (callback) callback(u); } };
breadthFirstSearch()方法接收一個graph對象，圖的數據通過該對象傳入。參數startVertex指定了遍歷的起始頂點。回調函數callback規定了要如何處理被遍歷到的頂點。
首先通過initializeColor()函數將所有的頂點標記為未被訪問過（顏色為白色），這些顏色保存在以頂點值為key的color對象中。圖的vertices和adjList屬性可以通過getVertices()和getAdjList()方法得到，然後構造一個隊列queue（有關隊列類Queue請參考《JavaScript數據結構——隊列的實現與應用》），按照上面描述的步驟對圖的頂點進行遍歷。
在前面我們給出的測試用例的基礎上，添加下面的程式碼，來看看breadthFirstSearch()方法的執行結果：
breadthFirstSearch(graph, 'A', value => console.log(`visited vertex: ${value}`));
參數graph為前面測試用例中Graph類的實例，也就是我們用來保存圖的數據的對象，’A’被作為遍歷的起始頂點，在回調函數中，列印一行文本，用來展示頂點被遍歷的順序。下面是測試結果：
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
嘗試將’I’作為起始頂點，看看執行結果：
visited vertex: I visited vertex: E visited vertex: B visited vertex: A visited vertex: F visited vertex: C visited vertex: D visited vertex: G visited vertex: H
為了方便理解，我們將頂點I放到最上面。從頂點I開始，首先遍歷到的是它的相鄰頂點E，然後是E的相鄰頂點B，其次是B的相鄰頂點A和F，A的相鄰頂點C和D，C的相鄰頂點G（D已經被遍歷過了），最後是D的相鄰頂點H（C和G已經被遍歷過了）。
尋找最短路徑
前面展示了廣度優先演算法的工作原理，我們可以使用它做更多的事情，例如在一個圖G中，從頂點v開始到其它所有頂點間的最短距離。我們考慮一下如何用BFS來實現尋找最短路徑。
假設兩個相鄰頂點間的距離為1，從頂點v開始，在其路徑上每經過一個頂點，距離加1。下面是對breadthFirstSearch()方法的改進，用來返回從起始頂點開始到其它所有頂點間的距離，以及所有頂點的前置頂點。
let BFS = (graph, startVertex) => { let vertices = graph.getVertices(); let adjList = graph.getAdjList(); let color = initializeColor(vertices); let queue = new Queue(); let distances = {}; let predecessors = {}; queue.enqueue(startVertex); // 初始化所有頂點的距離為0，前置節點為null vertices.forEach(v => { distances[v] = 0; predecessors[v] = null; }); while (!queue.isEmpty()) { let u = queue.dequeue(); adjList.get(u).forEach(n => { if (color[n] === Colors.WHITE) { color[n] = Colors.GREY; distances[n] = distances[u] + 1; predecessors[n] = u; queue.enqueue(n); } }); color[u] = Colors.BLACK; } return {distances, predecessors}; };
在BFS()方法中，我們定義了兩個對象distances和predecessors，用來保存從起始頂點出發到其它所有頂點的距離以及這些頂點的前置頂點。BFS()方法不需要callback回調函數，因為它會自行輸出最終結果。與breadthFirstSearch()方法的邏輯類似，只不過在開始的時候將所有頂點的距離初始化為0，前置頂點初始化為null，然後在遍歷的過程中，重新設置頂點的distances值和predecessors值。我們仍然將頂點A作為起始頂點，來看看測試結果：
console.log(BFS(graph, 'A'));
{ 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' } }
如你所見，distances為從頂點A開始到其它所有頂點的最短距離（相鄰頂點間的距離為1），predecessors記錄了所有頂點的前置頂點。以BFS()方法的返回結果為基礎，通過下面的程式碼，我們可以得出從頂點A開始到其它所有頂點的最短路徑：
let shortestPathA = BFS(graph, 'A'); let startVertex = 'A'; myVertices.forEach(v => { let path = new Stack(); for (let v2 = v; v2 !== startVertex; v2 = shortestPathA.predecessors[v2]) { path.push(v2); } path.push(startVertex); let s = path.pop(); while (!path.isEmpty()) { s += ` - ${path.pop()}`; } console.log(s); });
其中的Stack類可以參考《JavaScript數據結構——棧的實現與應用》。下面是對應的執行結果：
A A - B A - C A - D A - B - E A - B - F A - C - G A - D - H A - B - E - I
以上我們說的都是未加權的圖，對於加權的圖，廣度優先演算法並不是最合適的。下面給出了另外幾種最短路徑演算法：
Dijkstra – 尋找從指定頂點到其它所有頂點的最短路徑的貪心演算法。
1 const INF = Number.MAX_SAFE_INTEGER; 2 const minDistance = (dist, visited) => { 3 let min = INF; 4 let minIndex = -1; 5 for (let v = 0; v < dist.length; v++) { 6 if (visited[v] === false && dist[v] <= min) { 7 min = dist[v]; 8 minIndex = v; 9 } 10 } 11 return minIndex; 12 }; 13 const dijkstra = (graph, src) => { 14 const dist = []; 15 const visited = []; 16 const { length } = graph; 17 for (let i = 0; i < length; i++) { 18 dist[i] = INF; 19 visited[i] = false; 20 } 21 dist[src] = 0; 22 for (let i = 0; i < length - 1; i++) { 23 const u = minDistance(dist, visited); 24 visited[u] = true; 25 for (let v = 0; v < length; v++) { 26 if (!visited[v] && graph[u][v] !== 0 && dist[u] !== INF && dist[u] + graph[u][v] < dist[v]) { 27 dist[v] = dist[u] + graph[u][v]; 28 } 29 } 30 } 31 return dist; 32 };
dijkstra
Floyd-Warshall – 計算圖中所有最短路徑的動態規劃演算法。
1 const floydWarshall = graph => { 2 const dist = []; 3 const { length } = graph; 4 for (let i = 0; i < length; i++) { 5 dist[i] = []; 6 for (let j = 0; j < length; j++) { 7 if (i === j) { 8 dist[i][j] = 0; 9 } else if (!isFinite(graph[i][j])) { 10 dist[i][j] = Infinity; 11 } else { 12 dist[i][j] = graph[i][j]; 13 } 14 } 15 } 16 for (let k = 0; k < length; k++) { 17 for (let i = 0; i < length; i++) { 18 for (let j = 0; j < length; j++) { 19 if (dist[i][k] + dist[k][j] < dist[i][j]) { 20 dist[i][j] = dist[i][k] + dist[k][j]; 21 } 22 } 23 } 24 } 25 return dist; 26 };
floydWarshall
Kruskal – 求解加權無向連通圖的最小生成樹（MST）的貪心演算法。
1 const INF = Number.MAX_SAFE_INTEGER; 2 const find = (i, parent) => { 3 while (parent[i]) { 4 i = parent[i]; // eslint-disable-line prefer-destructuring 5 } 6 return i; 7 }; 8 const union = (i, j, parent) => { 9 if (i !== j) { 10 parent[j] = i; 11 return true; 12 } 13 return false; 14 }; 15 const initializeCost = graph => { 16 const cost = []; 17 const { length } = graph; 18 for (let i = 0; i < length; i++) { 19 cost[i] = []; 20 for (let j = 0; j < length; j++) { 21 if (graph[i][j] === 0) { 22 cost[i][j] = INF; 23 } else { 24 cost[i][j] = graph[i][j]; 25 } 26 } 27 } 28 return cost; 29 }; 30 const kruskal = graph => { 31 const { length } = graph; 32 const parent = []; 33 let ne = 0; 34 let a; 35 let b; 36 let u; 37 let v; 38 const cost = initializeCost(graph); 39 while (ne < length - 1) { 40 for (let i = 0, min = INF; i < length; i++) { 41 for (let j = 0; j < length; j++) { 42 if (cost[i][j] < min) { 43 min = cost[i][j]; 44 a = u = i; 45 b = v = j; 46 } 47 } 48 } 49 u = find(u, parent); 50 v = find(v, parent); 51 if (union(u, v, parent)) { 52 ne++; 53 } 54 cost[a][b] = cost[b][a] = INF; 55 } 56 return parent; 57 };
kruskal
Prime – 求解加權無向連通圖的最小生成樹（MST）的貪心演算法。
1 const INF = Number.MAX_SAFE_INTEGER; 2 const minKey = (graph, key, visited) => { 3 // Initialize min value 4 let min = INF; 5 let minIndex = 0; 6 for (let v = 0; v < graph.length; v++) { 7 if (visited[v] === false && key[v] < min) { 8 min = key[v]; 9 minIndex = v; 10 } 11 } 12 return minIndex; 13 }; 14 const prim = graph => { 15 const parent = []; 16 const key = []; 17 const visited = []; 18 const { length } = graph; 19 for (let i = 0; i < length; i++) { 20 key[i] = INF; 21 visited[i] = false; 22 } 23 key[0] = 0; 24 parent[0] = -1; 25 for (let i = 0; i < length - 1; i++) { 26 const u = minKey(graph, key, visited); 27 visited[u] = true; 28 for (let v = 0; v < length; v++) { 29 if (graph[u][v] && !visited[v] && graph[u][v] < key[v]) { 30 parent[v] = u; 31 key[v] = graph[u][v]; 32 } 33 } 34 } 35 return parent; 36 };
prim
深度優先
深度優先演算法從圖的第一個頂點開始，沿著這個頂點的一條路徑遞歸查找到最後一個頂點，然後返回並探查路徑上的其它路徑，直到所有路徑都被訪問到。最終，深度優先演算法會先深後廣地訪問圖中的所有頂點。下面是深度優先遍歷的示意圖：
我們仍然採用和廣度優先演算法一樣的思路，一開始將所有的頂點初始化為白色，然後沿著路徑遞歸探查其餘頂點，當頂點被訪問過，將顏色改為灰色，如果頂點被探索過（處理過），則將顏色改為黑色。下面是深度優先演算法的具體實現：
let depthFirstSearchVisit = (u, color, adjList, callback) => { color[u] = Colors.GREY; if (callback) callback(u); adjList.get(u).forEach(n => { if (color[n] === Colors.WHITE) { depthFirstSearchVisit(n, color, adjList, callback); } }); color[u] = Colors.BLACK; }; let depthFirstSearch = (graph, callback) => { let vertices = graph.getVertices(); let adjList = graph.getAdjList(); let color = initializeColor(vertices); vertices.forEach(v => { if (color[v] === Colors.WHITE) { depthFirstSearchVisit(v, color, adjList, callback); } }); };
具體執行步驟為：
- 將圖中所有頂點的顏色初始化為白色。
- 遍歷頂點，此時A作為第一個頂點，它的顏色為白色，於是調用函數depthFirstSearchVisit()，並將頂點A、color、graph.adjList作為參數傳入。
- 在depthFirstSearchVisit()函數內部，由於頂點A被訪問過了，所以將顏色設置為灰色，並執行callback回調函數（如果存在），然後遍歷A的鄰接頂點B、C、D。
- B未被訪問過，顏色為白色，所以將B作為參數遞歸調用depthFirstSearchVisit()函數。B設置為灰色，callback(‘B’)。遍歷B的鄰接節點E和F。
- E未被訪問過，顏色為白色，所以將E作為參數遞歸調用depthFirstSearchVisit()函數。E設置為灰色，callback(‘E’)。遍歷E的鄰接節點I。
- I未被訪問過，顏色為白色，所以將I作為參數遞歸調用depthFirstSearchVisit()函數。I設置為灰色，callback(‘I’)。I沒有鄰接節點，然後將I設置為黑色。遞歸返回到5。
- E沒有其它鄰接節點，將E設置為黑色。遞歸返回到4。
- 遍歷B的另一個鄰接節點F，F未被訪問過，顏色為白色，所以將F作為參數遞歸調用depthFirstSearchVisit()函數。F設置為灰色，callback(‘F’)。F沒有鄰接節點，然後將F設置為黑色。遞歸返回到4。
- B的所有鄰接節點都被訪問過了，將B設置為黑色。遞歸返回到3。
- 訪問A的第二個鄰接節點C，C未被訪問過，顏色為白色，所以將C作為參數遞歸調用depthFirstSearchVisit()函數。C設置為灰色，callback(‘C’)。遍歷C的鄰接節點D、G。
- D未被訪問過，顏色為白色，所以將D作為參數遞歸調用depthFirstSearchVisit()函數。D設置為灰色，callback(‘D’)。遍歷D的鄰接節點G和H。
- G未被訪問過，顏色為白色，所以將G作為參數遞歸調用depthFirstSearchVisit()函數。G設置為灰色，callback(‘G’)。G沒有鄰接節點，然後將G設置為黑色。遞歸返回到11。
- 遍歷D的另一個鄰接節點H，H未被訪問過，顏色為白色，所以將H作為參數遞歸調用depthFirstSearchVisit()函數。H設置為灰色，callback(‘H’)。H沒有鄰接節點，然後將H設置為黑色。遞歸返回到11。
- D的所有鄰接節點都被訪問過了，將D設置為黑色。遞歸返回到10。
- 遍歷C的另一個鄰接節點G，由於G已經被訪問過，對C的鄰接節點的遍歷結束。將C設置為黑色。遞歸返回到3。
- 訪問A的最後一個鄰接節點D，由於D已經被訪問過，對A的鄰接節點的遍歷結束。將A設置為黑色。
- 然後對剩餘的節點進行遍歷。由於剩餘的節點都被設置為黑色了，所以程式結束。
對應的測試用例及執行結果如下：
depthFirstSearch(graph, value => console.log(`visited vertex: ${value}`));
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
為了便於理解，我們將整個遍歷過程用下面的示意圖來展示：
前面說過，深度優先演算法的數據結構是棧，然而這裡我們並沒有使用棧來存儲任何數據，而是使用了函數的遞歸調用，其實遞歸也是棧的一種表現形式。另外一點，如果圖是連通的（即圖中任何兩個頂點之間都存在路徑），我們可以對上述程式碼中的depthFirstSearch()方法進行改進，只需要對圖的起始頂點開始遍歷一次就可以了，而不需要遍歷圖的所有頂點，因為從起始頂點開始的遞歸就可以覆蓋圖的所有頂點。
拓撲排序
前面展示了深度優先演算法的工作原理，我們可以使用它做更多的事情，例如拓撲排序（toplogical sorting，也叫做topsort或者toposort）。與廣度優先演算法類似，我們也對上面的depthFirstSeach()方法進行改進，以說明如何使用深度優先演算法來實現拓撲排序：
let DFSVisit = (u, color, discovery, finished, predecessors, time, adjList) => { color[u] = Colors.GREY; discovery[u] = ++time.count; adjList.get(u).forEach(n => { if (color[n] === Colors.WHITE) { predecessors[n] = u; DFSVisit(n, color, discovery, finished, predecessors, time, adjList); } }); color[u] = Colors.BLACK; finished[u] = ++time.count; }; let DFS = graph => { let vertices = graph.getVertices(); let adjList = graph.getAdjList(); let color = initializeColor(vertices); let discovery = {}; let finished = {}; let predecessors = {}; let time = { count: 0 }; vertices.forEach(v => { finished[v] = 0; discovery[v] = 0; predecessors[v] = null; }); vertices.forEach(v => { if (color[v] === Colors.WHITE) { DFSVisit(v, color, discovery, finished, predecessors, time, adjList); } }); return {discovery, finished, predecessors}; };
DFS()方法會輸出圖中每個頂點的發現時間和探索時間，我們假定時間從0開始，每經過一步時間值加1。在DFS()方法中，我們用變數discovery，finished，predecessors來保存每個頂點的發現時間、探索時間和前置頂點（這個和廣度優先演算法中尋找最短路徑中的一致，但最終執行結果會有區別），最終的輸出結果中也會反映這三個值。這裡需要注意的是，變數time之所以被定義為對象而不是一個普通的數字，是因為我們需要在函數間傳遞這個變數，如果只是作為值傳遞，函數內部對變數的修改不會影響到它的原始值，但是我們就是需要在函數遞歸調用的過程中不斷記錄time的變化過程，所以採用值傳遞的方式顯然不行。因此我們將time定義為一個對象，對象被作為引用傳遞給函數，這樣在函數內部對它的修改就會反映到原始值上。
來看看對DFS()方法的測試結果：
console.log(DFS(graph));
{ discovery: { A: 1, B: 2, C: 10, D: 11, E: 3, F: 7, G: 12, H: 14, I: 4 }, finished: { A: 18, B: 9, C: 17, D: 16, E: 6, F: 8, G: 13, H: 15, I: 5 }, predecessors: { A: null, B: 'A', C: 'A', D: 'C', E: 'B', F: 'B', G: 'D', H: 'D', I: 'E' } }
我們將結果反映到示意圖上，這樣更加直觀：
示意圖上每一個頂點左邊的數字是頂點的發現時間，右邊的數字是頂點的探索時間，全部完成時間是18，可以結合前面的深度優先演算法遍歷過程示意圖來看，它們是對應的。同時我們也看到，深度優先演算法的predecessors和廣度優先演算法的predecessors會有所不同。
拓撲排序只能應用於有向無環圖（DAG）。基於上面DFS()方法的返回結果，我們可以對頂點的完成時間（探索時間finished）進行排序，以得到我們需要的拓撲排序結果。
如果要實現有向圖，只需要對前面我們實現的Graph類的addEdge()方法略加修改，將最後一行刪掉。當然，我們也可以在Graph類的構造函數中指明是有向圖還是無向圖，下面是改進後的Graph類：
1 class Graph { 2 constructor (isDirected = false) { 3 this.isDirected = isDirected; 4 this.vertices = []; // 用來存放圖中的頂點 5 this.adjList = new Dictionary(); // 用來存放圖中的邊 6 } 7 8 // 向圖中添加一個新頂點 9 addVertex (v) { 10 if (!this.vertices.includes(v)) { 11 this.vertices.push(v); 12 this.adjList.set(v, []); 13 } 14 } 15 16 // 向圖中添加a和b兩個頂點之間的邊 17 addEdge (a, b) { 18 // 如果圖中沒有頂點a，先添加頂點a 19 if (!this.adjList.has(a)) { 20 this.addVertex(a); 21 } 22 // 如果圖中沒有頂點b，先添加頂點b 23 if (!this.adjList.has(b)) { 24 this.addVertex(b); 25 } 26 27 this.adjList.get(a).push(b); // 在頂點a中添加指向頂點b的邊 28 if (this.isDirected !== true) { 29 this.adjList.get(b).push(a); // 如果為無向圖，則在頂點b中添加指向頂點a的邊 30 } 31 } 32 33 // 獲取圖的vertices 34 getVertices () { 35 return this.vertices; 36 } 37 38 // 獲取圖中的adjList 39 getAdjList () { 40 return this.adjList; 41 } 42 43 toString() { 44 let s = ''; 45 this.vertices.forEach((v) => { 46 s += `${v} -> `; 47 this.adjList.get(v).forEach((n) => { 48 s += `${n} `; 49 }); 50 s += 'n'; 51 }); 52 return s; 53 } 54 }
Graph
然後我們對有向圖應用DFS演算法：
let graph = new Graph(); let myVertices = ['A', 'B', 'C', 'D', 'E', 'F']; myVertices.forEach((v) => { graph.addVertex(v); }); graph.addEdge('A', 'C'); graph.addEdge('A', 'D'); graph.addEdge('B', 'D'); graph.addEdge('B', 'E'); graph.addEdge('C', 'F'); graph.addEdge('F', 'E'); console.log(DFS(graph));
下面是返回結果：
{ discovery: { A: 1, B: 11, C: 2, D: 8, E: 4, F: 3 }, finished: { A: 10, B: 12, C: 7, D: 9, E: 5, F: 6 }, predecessors: { A: null, B: null, C: 'A', D: 'A', E: 'F', F: 'C' } }
示意圖如下：
對頂點的完成時間進行倒序排序，得到的拓撲排序結果為：B – A – D – C – F – E。
下一章我們將介紹如何用JavaScript來實現各種常見的排序演算法。
