一、是什么

在計算機科學中，圖是一種抽象的數據類型，在圖中的數據元素通常稱為結點，V是所有頂點的集合，E是所有邊的集合

如果兩個頂點v,w，只能由v向w，而不能由w向v，那么我們就把這種情況叫做一個從 v 到 w 的有向邊。v也被稱做初始點，w也被稱為終點。這種圖就被稱做有向圖

如果v和w是沒有順序的，從v到達w和從w到達v是完全相同的，這種圖就被稱為無向圖

圖的結構比較復雜，任意兩個頂點之間都可能存在聯系，因此無法以數據元素在存儲區中的物理位置來表示元素之間的關系

常見表達圖的方式有如下：

• 鄰接矩陣
• 鄰接表

鄰接矩陣

通過使用一個二維數組G[N][N]進行表示N個點到N-1編號，通過鄰接矩陣可以立刻看出兩頂點之間是否存在一條邊，只需要檢查鄰接矩陣行i和列j是否是非零值，對于無向圖，鄰接矩陣是對稱的

鄰接表

存儲方式如下圖所示：

在javascript中，可以使用Object進行表示，如下：

1. const graph = { 
2.   A: [2, 3, 5], 
3.   B: [2], 
4.   C: [0, 1, 3], 
5.   D: [0, 2], 
6.   E: [6], 
7.   F: [0, 6], 
8.   G: [4, 5] 
9. } 

圖的數據結構還可能包含和每條邊相關聯的數值(edge value)，例如一個標號或一個數值(即權重，weight;表示花費、容量、長度等)

二、操作

關于圖的操作常見的有：

• 深度優先遍歷
• 廣度優先遍歷

首先構建一個圖的鄰接矩陣表示，如下面的圖：

用代碼表示則如下：

1. const graph = { 
2.   0: [1, 4], 
3.   1: [2, 4], 
4.   2: [2, 3], 
5.   3: [], 
6.   4: [3], 
7. } 

深度優先遍歷

也就是盡可能的往深處的搜索圖的分支

實現思路是，首先應該確定一個根節點，然后對根節點的沒訪問過的相鄰節點進行深度優先遍歷

確定以 0 為根節點，然后進行深度遍歷，然后遍歷1，接著遍歷 2，然后3，此時完成一條分支0 - 1- 2- 3的遍歷，換一條分支，也就是4，4后面因為3已經遍歷過了，所以就不訪問了

用代碼表示則如下：

1. const visited = new Set() 
2. const dfs = (n) => { 
3.   console.log(n) 
4.   visited.add(n) // 訪問過添加記錄 
5.   graph[n].forEach(c => { 
6.     if(!visited.has(c)){ // 判斷是否訪問呢過 
7.       dfs(c) 
8.     } 
9.   }) 
10. } 

廣度優先遍歷

先訪問離根節點最近的節點，然后進行入隊操作，解決思路如下：

• 新建一個隊列，把根節點入隊
• 把隊頭出隊并訪問
• 把隊頭的沒訪問過的相鄰節點入隊
• 重復二、三步驟，知道隊列為空

用代碼標識則如下：

1. const visited = new Set() 
2. const dfs = (n) => { 
3.   visited.add(n) 
4.   const q = [n] 
5.   while(q.length){ 
6.     const n = q.shift() 
7.     console.log(n) 
8.     graph[n].forEach(c => { 
9.       if(!visited.has(c)){ 
10.         q.push(c)   
11.         visited.add(c) 
12.       } 
13.     }) 
14.   } 
15. } 

三、總結

通過上面的初步了解，可以看到圖就是由頂點的有窮非空集合和頂點之間的邊組成的集合，分成了無向圖與有向圖

圖的表達形式可以分成鄰接矩陣和鄰接表兩種形式，在javascript中，則可以通過二維數組和對象的形式進行表達

圖實際是很復雜的，后續還可以延伸出無向圖和帶權圖，對應如下圖所示：

參考文獻

https://zh.wikipedia.org/wiki/%E5%9B%BE_(%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84)

https://www.kancloud.cn/imnotdown1019/java_core_full/2159607

原文鏈接：https://mp.weixin.qq.com/s/rzyhoK0UjtOjFObVL9HUBQ