大家好，我是小丞同學，一名大二的前端愛好者
這篇文章将講解資料結構中的圖
非常感謝你的閱讀，不對的地方歡迎指正
願你忠于自己，熱愛生活
知識點搶先看
什麼是圖結構？
圖結構有什麼應用場景？
圖結構有什麼方法？
如何實作一個圖結構？
LeetCode 實戰
歡迎大家關注本專欄，持續關注最新文章~
本專欄的其他内容
從這裡開始 【化解資料結構】從這裡開啟資料結構和算法
棧 【化解資料結構】什麼是棧？手寫實作一個棧結構!
隊列 【化解資料結構】詳解隊列，優先隊列，循環隊列，并實作一個隊列
集合 【化解資料結構】詳解集合結構，并實作一個集合
字典 【化解資料結構】詳解字典結構，并實作一個字典
樹 【化解資料結構】詳解樹結構，并實作二叉搜尋樹
堆 【化解資料結構】詳解堆結構，并實作最小堆結構
碎碎念
太棒了，這篇文章是資料結構部分的最後一篇文章了，敲鍵盤都累了，呼呼~，圖結構是一個我認為非常有意思的結構，它能表示我們生活中很常見的場景，也能解決很多的問題，一起來探尋一下吧
一、什麼是圖結構？
圖結構是一種網絡結構的抽象模型，是一組由邊連接配接而成的節點
同時圖可以表示任何二進制關系，比如道路、航班…
那為什麼可以表示二進制關系呢？
因為圖中的每一條邊都是由兩個節點相連而成的，是以圖可以表示任何二進制關系
在我們生活中，每天使用的微信等社交軟體，我們的好友關系網也能被形象成一種圖結構，如圖，圖能表示各種豐富的關系結構
在 JS 中沒有圖結構，我們可以用對象或者數組來建構一個圖結構
如此抽象的圖結構，我們該如何來表示它們呢，我們這裡會講到 3 中方法
鄰接矩陣
鄰接表
關聯矩陣
二、圖的相關術語
一個圖由 G = (V,E) 組成，V 表示一組頂點， E 表示一組邊，連接配接 V 中的頂點
就例如，下面這個圖結構，key 表示頂點，value 表示與這個頂點相連的節點
const graph = {
0: [1, 2],
1: [2],
2: [0, 3],
3: [3]
}; 術語 含義
頂點 圖的基本單元，也就是圖中的節點
邊 頂點之間的關聯關系，被稱為邊
相鄰頂點 由一條邊連接配接在一起的頂點
度 一個頂點包含的相鄰頂點的數量
如何來了解這些術語呢？我們來結合圖結構解釋一下
還是這個圖，我們對節點 A 分析一下
A節點和 B 節點相鄰，A 和 D 是相鄰的，A 和 C 是相鄰的，A 和 E 不是相鄰的，是以 A 節點和 B,C,D 是相鄰節點
圖中的每一個節點都能作為頂點存在
A 節點的度，由于 A 與其他三個節點相連，是以 A 節點的度為 3 ，圖中的 D 節點和其他 4 個節點相連，是以它的度為 4
可以看到圖中 CDG 形成了一個環，是以這個圖也稱為有環的
如果圖中每兩個頂點間存在路徑，則圖是連通的
有向圖
圖中節點之間邊線是單向的
無向圖
圖中節點之間的邊線是雙向的，或者沒有方向，稱為無向圖
三、如何表示一個圖？
圖的表示有很多種方法，不存在絕對的方法，需要根據待解決的問題來确定圖的類型
1. 鄰接矩陣
我們可以采用一個二維數組來确定頂點間的連接配接關系，如果 A 能連接配接到 B 那麼我們就置為 1 ，如果連不到就是 0
如圖 A 連接配接 B 節點，是以 第一行第二列為 1，表示 A 連接配接 B
2. 鄰接表
采用鄰接表來表示一個圖更形象更容易了解
它直接就表示哪個頂點和哪個頂點連接配接，十厘清晰
如圖 B 節點連接配接 C,D 節點，C節點連接配接 E 節點，十分的友善，推薦使用
四、圖的操作
接下來的操作基于這個圖結構來進行，這是用一個鄰接表來表示的一個圖結構
const graph = {
0:[1, 2],
1:[2],
2:[0, 3],
3:[3]
} 1. 深度優先周遊（DFS）
盡可能深的搜尋圖的分支，類似于樹的前序周遊
先通路根節點
對根節點的沒通路過的相鄰節點挨個進行深度優先周遊
代碼實作
// 記錄通路過的節點
const visited = new Set()
// 深度優先周遊
const dfs = (n) => {
console.log(n);
visited.add(n)
// 擷取所有相鄰節點
graph[n].forEach(c => {
// 如果沒有通路過
if (!visited.has(c)) {
dfs(c)
}
})
}
// 根節點
dfs(2) 輸出結果 ：2 0 1 3
2. 廣度優先周遊（BFS）
先通路離根節點最近的節點，類似于樹的層序周遊
周遊的方法
建立一個隊列，把根節點入隊并通路
把對頭沒有通路過的相鄰節點入隊
重複，直至隊列為空
// 廣度優先周遊
const bfs = (n) => {
const visited = new Set();
visited.add(n);
const q = [n];
while (q.length) {
const n = q.shift();
console.log(n);
graph[n].forEach(c => {
if (!visited.has(c)) {
q.push(c)
visited.add(c);
}
});
}
} 輸出結果：2 0 3 1
還有很多類似于最短路徑、拓撲排序、關鍵路徑等問題，難度有點大，就不讨論了有興趣的自己去研究吧~
五、圖結構有哪些方法？
根據上面的介紹，我們對圖結構有了一定的了解，接下來我們封裝一個圖結構，首先，先了解圖結構有哪些方法
方法 含義
addVertex(value) 向圖中添加一個頂點
addEdge(a,b) 向圖中添加兩點之間的邊
getVertices() 傳回圖的頂點清單
toString() 以字元串的形式輸出
六、手寫實作無向圖結構
1. 建立 Graph 類
首先我們需要建立一個 Graph 構造函數，用來存放圖中的屬性和方法
在這裡我們添加了兩個屬性，一個 vertices 用來儲存頂點， edgs 表示鄰接表
class Graph {
constructor() {
this.vertices = [] // 儲存頂點
this.edges = [] // 儲存邊，相當于鄰接表
}
} 2. 實作 addVertex 方法
添加這個頂點，我們先判斷一下圖中有沒有這個頂點，有的話我們就不添加了，沒有的話，添加到頂點清單中，同時添加到鄰接表中來建立邊關系
addVertex(value) {
// 如果沒有這個頂點
if(!this.vertices.includes(value)){
this.vertices.push(value) // 添加到頂點清單中
this.edges[value] = [] // 添加到鄰接表中
}
} 3. 實作 addEdge 方法
我們通過這個方法來建立邊連接配接的關系，接收兩個參數，表示需要進行連接配接的兩個節點，當這兩個節點都存在，并且沒有進行連接配接時，我們再進行鄰接表的修改操作，具體實作就是，将 a 放到 b 的連接配接數組中，b 放到 a 的連接配接數組中
addEdge(a,b) {
if(this.vertices.includes(a) && this.vertices.includes(b)) {
if(!this.edges[a].includes(b)) {
this.edges[a].push(b)
this.edges[b].push(a)
}
}
} 4. 實作 getVertices 方法
隻需要傳回我們的頂點數組即可
getVertices() {
return this.vertices
} 5. 實作 toString 方法
實作這個方法的關鍵在于，理清每一個層級之間的關系
采用數組來實作鄰接表，會造成周遊是時間複雜度變高，個人認為後期可以采用 map 或者 set 類進行實作
實作思路
先周遊頂點清單
在鄰接表中找到頂點清單對應的對象
拼接字元串，實作輸出
toString() {
let s = "";
// 周遊圖的頂點清單
for (let i = 0; i < this.vertices.length; i++) {
// 采用模闆字元串進行拼接
s += `${this.vertices[i]} -> `;
// 擷取頂點對應的鄰接表數組
const neighbors = this.edges[this.vertices[i]]
//周遊該鄰接表數組，解構數組成字元串
for (let j = 0; j < neighbors.length; j++) {
s += `${neighbors[j]} `;
}
// 每一個頂點單獨成行
s += "\n";
}
return s;
} 這樣一個簡單的圖結構，我們就實作了
6. 示範
基于上面的代碼我們進行操作示範
const graph = new Graph()
graph.addVertex(2)
graph.addVertex(1)
graph.addVertex(3)
graph.addVertex(0)
graph.addEdge(0,1)
graph.addEdge(0,2)
graph.addEdge(1,2)
graph.addEdge(2,3)
console.log(graph.toString()); 輸出結果戰術
符合我們的預期，完成封裝