JavaScript實現圖結構
- 2020 年 4 月 5 日
- 筆記
JavaScript實現圖結構
一、圖論
1.1.圖的簡介
什麼是圖？
- 圖結構是一種與樹結構有些相似的數據結構；
- 圖論是數學的一個分支，並且，在數學中，樹是圖的一種；
- 圖論以圖為研究對象，研究頂點和邊組成的圖形的數學理論和方法；
- 主要的研究目的為：事物之間的聯繫，頂點代表事物，邊代表兩個事物間的關係；
圖的特點：
- 一組頂點：通常用 V （Vertex）表示頂點的集合；
- 一組邊：通常用 E （Edge）表示邊的集合；
- 邊是頂點和頂點之間的連線；
- 邊可以是有向的，也可以是無向的。比如A—-B表示無向，A —> B 表示有向；
圖的常用術語：
-
頂點：表示圖中的一個節點；
-
邊：表示頂點和頂點給之間的連線；
-
相鄰頂點：由一條邊連接在一起的頂點稱為相鄰頂點；
-
度：一個頂點的度是相鄰頂點的數量；
-
路徑：
- 簡單路徑：簡單路徑要求不包含重複的頂點；
- 迴路：第一個頂點和最後一個頂點相同的路徑稱為迴路；
-
無向圖：圖中的所有邊都是沒有方向的；
-
有向圖：圖中的所有邊都是有方向的；
-
無權圖：無權圖中的邊沒有任何權重意義；
-
帶權圖：帶權圖中的邊有一定的權重含義；
1.2.圖的表示
鄰接矩陣
表示圖的常用方式為：鄰接矩陣。
-
可以使用二維數組來表示鄰接矩陣；
-
鄰接矩陣讓每個節點和一個整數相關聯，該整數作為數組的下標值；
-
使用一個二維數組來表示頂點之間的連接；
如上圖所示：
- 二維數組中的0表示沒有連線，1表示有連線；
- 如：A[ 0 ] [ 3 ] = 1，表示 A 和 C 之間有連接；
- 鄰接矩陣的對角線上的值都為0，表示A – A ，B – B，等自迴路都沒有連接（自己與自己之間沒有連接）；
- 若為無向圖，則鄰接矩陣應為對角線上元素全為0的對稱矩陣；
鄰接矩陣的問題：
- 如果圖是一個稀疏圖，那麼鄰接矩陣中將存在大量的 0，造成存儲空間的浪費；
鄰接表
另外一種表示圖的常用方式為：鄰接表。
- 鄰接表由圖中每個頂點以及和頂點相鄰的頂點列表組成；
- 這個列表可用多種方式存儲，比如：數組/鏈表/字典（哈希表）等都可以；
如上圖所示：
- 圖中可清楚看到A與B、C、D相鄰，假如要表示這些與A頂點相鄰的頂點（邊），可以通過將它們作為A的值（value）存入到對應的數組/鏈表/字典中。
- 之後，通過鍵（key）A可以十分方便地取出對應的數據；
鄰接表的問題：
- 鄰接表可以簡單地得出出度，即某一頂點指向其他頂點的個數；
- 但是，鄰接表計算入度（指向某一頂點的其他頂點的個數稱為該頂點的入度）十分困難。此時需要構造逆鄰接表才能有效計算入度；
二、封裝圖結構
在實現過程中採用鄰接表的方式來表示邊，使用字典類來存儲鄰接表。
2.1.添加字典類和隊列類
首先需要引入之前實現的，之後會用到的字典類和隊列類：
//封裝字典類 function Dictionary(){ //字典屬性 this.items = {} //字典操作方法 //一.在字典中添加鍵值對 Dictionary.prototype.set = function(key, value){ this.items[key] = value } //二.判斷字典中是否有某個key Dictionary.prototype.has = function(key){ return this.items.hasOwnProperty(key) } //三.從字典中移除元素 Dictionary.prototype.remove = function(key){ //1.判斷字典中是否有這個key if(!this.has(key)) return false //2.從字典中刪除key delete this.items[key] return true } //四.根據key獲取value Dictionary.prototype.get = function(key){ return this.has(key) ? this.items[key] : undefined } //五.獲取所有keys Dictionary.prototype.keys = function(){ return Object.keys(this.items) } //六.size方法 Dictionary.prototype.keys = function(){ return this.keys().length } //七.clear方法 Dictionary.prototype.clear = function(){ this.items = {} } } // 基於數組封裝隊列類 function Queue() { // 屬性 this.items = [] // 方法 // 1.將元素加入到隊列中 Queue.prototype.enqueue = element => { this.items.push(element) } // 2.從隊列中刪除前端元素 Queue.prototype.dequeue = () => { return this.items.shift() } // 3.查看前端的元素 Queue.prototype.front = () => { return this.items[0] } // 4.查看隊列是否為空 Queue.prototype.isEmpty = () => { return this.items.length == 0; } // 5.查看隊列中元素的個數 Queue.prototype.size = () => { return this.items.length } // 6.toString方法 Queue.prototype.toString = () => { let resultString = '' for (let i of this.items){ resultString += i + ' ' } return resultString } } 2.2.創建圖類
先創建圖類Graph，並添加基本屬性，再實現圖類的常用方法：
//封裝圖類 function Graph (){ //屬性：頂點(數組)/邊(字典) this.vertexes = [] //頂點 this.edges = new Dictionary() //邊 } 2.3.添加頂點與邊
如圖所示：
創建一個數組對象vertexes存儲圖的頂點；創建一個字典對象edges存儲圖的邊，其中key為頂點，value為存儲key頂點相鄰頂點的數組。
程式碼實現：
//添加方法 //一.添加頂點 Graph.prototype.addVertex = function(v){ this.vertexes.push(v) this.edges.set(v, []) //將邊添加到字典中，新增的頂點作為鍵，對應的值為一個存儲邊的空數組 } //二.添加邊 Graph.prototype.addEdge = function(v1, v2){//傳入兩個頂點為它們添加邊 this.edges.get(v1).push(v2)//取出字典對象edges中存儲邊的數組，並添加關聯頂點 this.edges.get(v2).push(v1)//表示的是無向表，故要添加互相指向的兩條邊 } 2.4.轉換為字元串輸出
為圖類Graph添加toString方法，實現以鄰接表的形式輸出圖中各頂點。
程式碼實現：
//三.實現toString方法:轉換為鄰接表形式 Graph.prototype.toString = function (){ //1.定義字元串，保存最終結果 let resultString = "" //2.遍歷所有的頂點以及頂點對應的邊 for (let i = 0; i < this.vertexes.length; i++) {//遍歷所有頂點 resultString += this.vertexes[i] + '-->' let vEdges = this.edges.get(this.vertexes[i]) for (let j = 0; j < vEdges.length; j++) {//遍歷字典中每個頂點對應的數組 resultString += vEdges[j] + ' '; } resultString += 'n' } return resultString } 測試程式碼：
//測試程式碼 //1.創建圖結構 let graph = new Graph() //2.添加頂點 let myVertexes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'] for (let i = 0; i < myVertexes.length; i++) { graph.addVertex(myVertexes[i]) } //3.添加邊 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') //4.輸出結果 console.log(graph.toString()); 測試結果：
2.5.圖的遍歷
圖的遍歷思想：
- 圖的遍歷思想與樹的遍歷思想一樣，意味著需要將圖中所有的頂點都訪問一遍，並且不能有重複的訪問（上面的toString方法會重複訪問）；
遍歷圖的兩種演算法：
- 廣度優先搜索（Breadth – First Search，簡稱BFS）;
- 深度優先搜索（Depth – First Search，簡稱DFS）;
- 兩種遍歷演算法都需要指定第一個被訪問的頂點；
為了記錄頂點是否被訪問過，使用三種顏色來表示它們的狀態
- 白色：表示該頂點還沒有被訪問過；
- 灰色：表示該頂點被訪問過，但其相鄰頂點並未完全被訪問過；
- 黑色：表示該頂點被訪問過，且其所有相鄰頂點都被訪問過；
首先封裝initializeColor方法將圖中的所有頂點初始化為白色，程式碼實現如下：
//四.初始化狀態顏色 Graph.prototype.initializeColor = function(){ let colors = [] for (let i = 0; i < this.vertexes.length; i++) { colors[this.vertexes[i]] = 'white'; } return colors } 廣度優先搜索
廣度優先搜索演算法的思路：
- 廣度優先搜索演算法會從指定的第一個頂點開始遍歷圖，先訪問其所有的相鄰頂點，就像一次訪問圖的一層；
- 也可以說是先寬後深地遍歷圖中的各個頂點；
實現思路：
基於隊列可以簡單地實現廣度優先搜索演算法：
- 首先創建一個隊列Q（尾部進，首部出）；
- 調用封裝的initializeColor方法將所有頂點初始化為白色；
- 指定第一個頂點A，將A標註為灰色（被訪問過的節點），並將A放入隊列Q中；
- 循環遍歷隊列中的元素，只要隊列Q非空，就執行以下操作：
- 先將灰色的A從Q的首部取出；
- 取出A後，將A的所有未被訪問過（白色）的相鄰頂點依次從隊列Q的尾部加入隊列，並變為灰色。以此保證，灰色的相鄰頂點不重複加入隊列；
- A的全部相鄰節點加入Q後，A變為黑色，在下一次循環中被移除Q外；
程式碼實現：
//五.實現廣度搜索(BFS) //傳入指定的第一個頂點和處理結果的函數 Graph.prototype.bfs = function(initV, handler){ //1.初始化顏色 let colors = this.initializeColor() //2.創建隊列 let que = new Queue() //3.將頂點加入到隊列中 que.enqueue(initV) //4.循環從隊列中取出元素，隊列為空才停止 while(!que.isEmpty()){ //4.1.從隊列首部取出一個頂點 let v = que.dequeue() //4.2.從字典對象edges中獲取和該頂點相鄰的其他頂點組成的數組 let vNeighbours = this.edges.get(v) //4.3.將v的顏色變為灰色 colors[v] = 'gray' //4.4.遍歷v所有相鄰的頂點vNeighbours,並且加入隊列中 for (let i = 0; i < vNeighbours.length; i++) { const a = vNeighbours[i]; //判斷相鄰頂點是否被探測過，被探測過則不加入隊列中；並且加入隊列後變為灰色，表示被探測過 if (colors[a] == 'white') { colors[a] = 'gray' que.enqueue(a) } } //4.5.處理頂點v handler(v) //4.6.頂點v所有白色的相鄰頂點都加入隊列後，將頂點v設置為黑色。此時黑色頂點v位於隊列最前面，進入下一次while循環時會被取出 colors[v] = 'black' } } 過程詳解：
下為指定的第一個頂點為A時的遍歷過程：
- 如 a 圖所示，將在字典edges中取出的與A相鄰的且未被訪問過的白色頂點B、C、D放入隊列que中並變為灰色，隨後將A變為黑色並移出隊列；
- 接著，如圖 b 所示，將在字典edges中取出的與B相鄰的且未被訪問過的白色頂點E、F放入隊列que中並變為灰色，隨後將B變為黑色並移出隊列；
- 如 c 圖所示，將在字典edges中取出的與C相鄰的且未被訪問過的白色頂點G（A，D也相鄰不過已變為灰色，所以不加入隊列）放入隊列que中並變為灰色，隨後將C變為黑色並移出隊列；
- 接著，如圖 d 所示，將在字典edges中取出的與D相鄰的且未被訪問過的白色頂點H放入隊列que中並變為灰色，隨後將D變為黑色並移出隊列。
如此循環直到隊列中元素為0，即所有頂點都變黑並移出隊列後才停止，此時圖中頂點已被全部遍歷。
測試程式碼：
//測試程式碼 //1.創建圖結構 let graph = new Graph() //2.添加頂點 let myVertexes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'] for (let i = 0; i < myVertexes.length; i++) { graph.addVertex(myVertexes[i]) } //3.添加邊 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') //4.測試bfs遍歷方法 let result = "" graph.bfs(graph.vertexes[0], function(v){ result += v + "-" }) console.log(result); 測試結果：
可見，安裝了廣度優先搜索的順序不重複地遍歷了所有頂點。
深度優先搜索
廣度優先演算法的思路：
- 深度優先搜索演算法將會從指定的第一個頂點開始遍歷圖，沿著一條路徑遍歷直到該路徑的最後一個頂點都被訪問過為止；
- 接著沿原來路徑回退並探索下一條路徑，即先深後寬地遍歷圖中的各個頂點；
實現思路：
- 可以使用棧結構來實現深度優先搜索演算法；
- 深度優先搜索演算法的遍歷順序與二叉搜索樹中的先序遍歷較為相似，同樣可以使用遞歸來實現（遞歸的本質就是函數棧的調用）。
基於遞歸實現深度優先搜索演算法：定義dfs方法用於調用遞歸方法dfsVisit，定義dfsVisit方法用於遞歸訪問圖中的各個頂點。
在dfs方法中：
- 首先，調用initializeColor方法將所有頂點初始化為白色；
- 然後，調用dfsVisit方法遍歷圖的頂點；
在dfsVisit方法中：
- 首先，將傳入的指定節點v標註為灰色；
- 接著，處理頂點V；
- 然後，訪問V的相鄰頂點；
- 最後，將頂點v標註為黑色；
程式碼實現：
//六.實現深度搜索(DFS) Graph.prototype.dfs = function(initV, handler){ //1.初始化頂點顏色 let colors = this.initializeColor() //2.從某個頂點開始依次遞歸訪問 this.dfsVisit(initV, colors, handler) } //為了方便遞歸調用，封裝訪問頂點的函數，傳入三個參數分別表示：指定的第一個頂點、顏色、處理函數 Graph.prototype.dfsVisit = function(v, colors, handler){ //1.將顏色設置為灰色 colors[v] = 'gray' //2.處理v頂點 handler(v) //3.訪問V的相鄰頂點 let vNeighbours = this.edges.get(v) for (let i = 0; i < vNeighbours.length; i++) { let a = vNeighbours[i]; //判斷相鄰頂點是否為白色，若為白色，遞歸調用函數繼續訪問 if (colors[a] == 'white') { this.dfsVisit(a, colors, handler) } } //4.將v設置為黑色 colors[v] = 'black' } 過程詳解：
這裡主要解釋一下程式碼中的第3步操作：訪問指定頂點的相鄰頂點。
- 以指定頂點A為例，先從儲存頂點及其對應相鄰頂點的字典對象edges中取出由頂點A的相鄰頂點組成的數組：
- 第一步：A頂點變為灰色，隨後進入第一個for循環，遍歷A白色的相鄰頂點：B、C、D；在該for循環的第1次循環中（執行B），B頂點滿足：colors == "white"，觸發遞歸，重新調用該方法；
- 第二步：B頂點變為灰色，隨後進入第二個for循環，遍歷B白色的相鄰頂點：E、F；在該for循環的第1次循環中（執行E），E頂點滿足：colors == "white"，觸發遞歸，重新調用該方法；
- 第三步：E頂點變為灰色，隨後進入第三個for循環，遍歷E白色的相鄰頂點：I；在該for循環的第1次循環中（執行I），I頂點滿足：colors == "white"，觸發遞歸，重新調用該方法；
- 第四步：I頂點變為灰色，隨後進入第四個for循環，由於頂點I的相鄰頂點E不滿足：colors == "white"，停止遞歸調用。過程如下圖所示：
- 第五步：遞歸結束後一路向上返回，首先回到第三個for循環中繼續執行其中的第2、3…次循環，每次循環的執行過程與上面的同理，直到遞歸再次結束後，再返回到第二個for循環中繼續執行其中的第2、3…次循環….以此類推直到將圖的所有頂點訪問完為止。
下圖為遍歷圖中各頂點的完整過程：
- 發現表示訪問了該頂點，狀態變為灰色；
- 探索表示既訪問了該頂點，也訪問了該頂點的全部相鄰頂點，狀態變為黑色；
- 由於在頂點變為灰色後就調用了處理函數handler，所以handler方法的輸出順序為發現頂點的順序即：A、B、E、I、F、C、D、G、H 。
測試程式碼：
//測試程式碼 //1.創建圖結構 let graph = new Graph() //2.添加頂點 let myVertexes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'] for (let i = 0; i < myVertexes.length; i++) { graph.addVertex(myVertexes[i]) } //3.添加邊 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') //4.測試dfs遍歷頂點 let result = "" graph.dfs(graph.vertexes[0], function(v){ result += v + "-" }) console.log(result); 測試結果：
2.6.完整實現
//封裝圖結構 function Graph (){ //屬性：頂點(數組)/邊(字典) this.vertexes = [] //頂點 this.edges = new Dictionary() //邊 //方法 //添加方法 //一.添加頂點 Graph.prototype.addVertex = function(v){ this.vertexes.push(v) this.edges.set(v, []) //將邊添加到字典中，新增的頂點作為鍵，對應的值為一個存儲邊的空數組 } //二.添加邊 Graph.prototype.addEdge = function(v1, v2){//傳入兩個頂點為它們添加邊 this.edges.get(v1).push(v2)//取出字典對象edges中存儲邊的數組，並添加關聯頂點 this.edges.get(v2).push(v1)//表示的是無向表，故要添加互相指向的兩條邊 } //三.實現toString方法:轉換為鄰接表形式 Graph.prototype.toString = function (){ //1.定義字元串，保存最終結果 let resultString = "" //2.遍歷所有的頂點以及頂點對應的邊 for (let i = 0; i < this.vertexes.length; i++) {//遍歷所有頂點 resultString += this.vertexes[i] + '-->' let vEdges = this.edges.get(this.vertexes[i]) for (let j = 0; j < vEdges.length; j++) {//遍歷字典中每個頂點對應的數組 resultString += vEdges[j] + ' '; } resultString += 'n' } return resultString } //四.初始化狀態顏色 Graph.prototype.initializeColor = function(){ let colors = [] for (let i = 0; i < this.vertexes.length; i++) { colors[this.vertexes[i]] = 'white'; } return colors } //五.實現廣度搜索(BFS) //傳入指定的第一個頂點和處理結果的函數 Graph.prototype.bfs = function(initV, handler){ //1.初始化顏色 let colors = this.initializeColor() //2.創建隊列 let que = new Queue() //3.將頂點加入到隊列中 que.enqueue(initV) //4.循環從隊列中取出元素 while(!que.isEmpty()){ //4.1.從隊列中取出一個頂點 let v = que.dequeue() //4.2.獲取和頂點相相鄰的其他頂點 let vNeighbours = this.edges.get(v) //4.3.將v的顏色變為灰色 colors[v] = 'gray' //4.4.遍歷v所有相鄰的頂點vNeighbours,並且加入隊列中 for (let i = 0; i < vNeighbours.length; i++) { const a = vNeighbours[i]; //判斷相鄰頂點是否被探測過，被探測過則不加入隊列中；並且加入隊列後變為灰色，表示被探測過 if (colors[a] == 'white') { colors[a] = 'gray' que.enqueue(a) } } //4.5.處理頂點v handler(v) //4.6.頂點v所有白色的相鄰頂點都加入隊列後，將頂點v設置為黑色。此時黑色頂點v位於隊列最前面，進入下一次while循環時會被取出 colors[v] = 'black' } } //六.實現深度搜索(DFS) Graph.prototype.dfs = function(initV, handler){ //1.初始化頂點顏色 let colors = this.initializeColor() //2.從某個頂點開始依次遞歸訪問 this.dfsVisit(initV, colors, handler) } //為了方便遞歸調用，封裝訪問頂點的函數，傳入三個參數分別表示：指定的第一個頂點、顏色、處理函數 Graph.prototype.dfsVisit = function(v, colors, handler){ //1.將顏色設置為灰色 colors[v] = 'gray' //2.處理v頂點 handler(v) //3.訪問v相連的其他頂點 let vNeighbours = this.edges.get(v) for (let i = 0; i < vNeighbours.length; i++) { let a = vNeighbours[i]; //判斷相鄰頂點是否為白色，若為白色，遞歸調用函數繼續訪問 if (colors[a] == 'white') { this.dfsVisit(a, colors, handler) } } //4.將v設置為黑色 colors[v] = 'black' } } 
