【戲玩算法】12-圖

---

theme: fancy highlight: atom-one-light

---

持續創作，加速成長！這是我參與「掘金日新計劃 · 6 月更文挑戰」的第27天，點擊查看活動詳情

Hi~，我是一碗周，如果寫的文章有幸可以得到你的青睞，萬分有幸~

🫐 寫在前面

在上一篇文章中我們用了很大的篇幅來介紹紅黑樹，這篇文章我們來簡單的學習一下圖這個數據結構。

🍊 什麼是圖

數據結構中的圖並不是圖片的圖，而是網絡結構的抽象模型，更具體的説圖是一組由邊連接的節點。

圖在我們的生活中無處不在，它可以用來表示任何的二元關係，例如北京的地鐵線路圖：

上圖來源於網絡，侵刪

圖這個數據結構還可以分為有向圖和無向圖，所謂的有向圖和無向圖就是有沒有方向，如下圖：

每個邊也可以有權重，這個權重可以説是邊的值，在地圖中非常有用，例如上面的地鐵線路圖，這個權重可以表示兩個站的距離。

🍉 JavaScript表示圖

JavaScript並沒有圖這個數據結構，我們可以使用對象和數組來構建一個圖。

圖的表示方式通常為兩種：

• 臨界矩陣

鄰接表

🍋 鄰接矩陣表示法

使用鄰接矩陣表示法時，我們讓鄰接矩陣中的每個節點和一個數組相關聯，使用二維數組來表示，如下圖：

在上圖中，二維數組中的1表示有連線，0表示沒有連線。

🍌 鄰接表表示法

使用鄰接表表示法時，鄰接表由圖中每個頂點以及和頂點相鄰的頂點列表組成，這個列表可以是個數組，鏈表字典等結構；如下圖所示：

🍍 圖的常用操作

圖的常用操作有兩個，一個深度優先遍歷，一個廣度優先遍歷，現在用下面這個圖來實現這兩個遍歷：

```javascript const graph = { A: ['B', 'D'], B: ['A', 'C'], C: ['B', 'E', 'G'], D: ['A'], E: ['C', 'F'], F: ['E', 'G'], G: ['C', 'F', 'H'], H: ['G'], } module.exports = graph

```

🥭 深度優先遍歷

實現深度優先遍歷的思路如下：

訪問根節點

對根節點中沒有訪問過 （避免重複訪問）的相鄰節點進行深度優先遍歷。

實現代碼如下：

```javascript const graph = require('./graph')

// 記錄已經訪問的節點 const visited = new Set()

const dfs = n => { console.log(n) // 把已經當問的節點加入集合 visited.add(n) // 訪問所有節點 graph[n].forEach(c => { if (!visited.has(c)) { dfs(c) } }) } dfs('A') / * 結果 A B C E F G H D* / ```

🍎 廣度優先遍歷

實現廣度優先遍歷的思路如下：

新建一個隊列，把根節點入隊；

把隊頭出隊並訪問；

把隊頭的沒訪問過的相鄰節點入隊；

重複前面兩個步驟直到隊列為空。

實現代碼如下：

```javascript const graph = require('./graph')

// 記錄已經訪問的節點 const visited = new Set() // 將根節點記錄為已經訪問過 visited.add('A')

// 定義一個隊列 const q = ['A'] while (q.length) { // 隊頭出隊 const n = q.shift() console.log(n) // 相鄰節點依次入隊 graph[n].forEach(c => { if (!visited.has(c)) { q.push(c) visited.add(c) } }) } / * 結果 A B D C E G F H* /

```

🍏 寫在最後

這篇文章就簡單的介紹了一下圖這個數據結構，實現了深度優先搜索和廣度優先搜索兩個算法。

本專欄採用JavaScript作為編程語言，從前端的角度去介紹數據結構與算法，如果對你所有幫助，可以點個關注支持一下啊\~