【戲玩演算法】12-圖

語言: CN / TW / HK

theme: fancy highlight: atom-one-light


持續創作,加速成長!這是我參與「掘金日新計劃 · 6 月更文挑戰」的第27天,點選檢視活動詳情

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

🫐 寫在前面

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

🍊 什麼是圖

資料結構中的圖並不是圖片的圖,而是網路結構的抽象模型,更具體的說圖是一組由邊連線的節點。

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

北京地鐵線路圖.png

上圖來源於網路,侵刪

圖這個資料結構還可以分為有向圖無向圖,所謂的有向圖和無向圖就是有沒有方向,如下圖:

01_有向圖和無向圖.png

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

🍉 JavaScript表示圖

JavaScript並沒有圖這個資料結構,我們可以使用物件和陣列來構建一個圖。

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

  • 臨界矩陣

鄰接表

🍋 鄰接矩陣表示法

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

02_鄰接矩陣表示法.png

在上圖中,二維陣列中的1表示有連線,0表示沒有連線。

🍌 鄰接表表示法

使用鄰接表表示法時,鄰接表由圖中每個頂點以及和頂點相鄰的頂點列表組成,這個列表可以是個陣列,連結串列字典等結構;如下圖所示:

03_鄰接表表示法.png

🍍 圖的常用操作

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

```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作為程式語言,從前端的角度去介紹資料結構與演算法,如果對你所有幫助,可以點個關注支援一下啊\~