【戲玩算法】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作為編程語言,從前端的角度去介紹數據結構與算法,如果對你所有幫助,可以點個關注支持一下啊\~
- 用ChatGPT學Nginx是一種什麼體驗
- 【好物分享】分享給前端開發的28個資源(網站、軟件、插件),簡直是提高效率必備
- Vite3.0都來了,你還捲動嗎?(Vite3.0新特性一覽)
- 【好物分享】在命令行讀Markdown,這個感覺太舒服了
- 從0開始使用pnpm構建一個Monorepo方式管理的demo
- 我畫了5張腦圖可以讓你快速入門TypeScript
- 我看着MDN文檔,手寫了幾個數組實例方法
- 淺談JavaScript中的特殊函數
- 如何通過SSH配合VSCode收穫超舒適的遠程開發體驗
- CSS的calc函數不會還有人沒有用吧
- 【戲玩算法】12-圖
- 誰説前端不能搞紅黑樹,用這55張圖拿JS一起手撕紅黑樹
- 簡單總結了10個JavaScript代碼優化小tips
- NaiveUI中看起來沒啥用的組件(文字漸變)實現原來這麼簡單
- 面試官讓我用Flex寫色子佈局,我直接給寫了6個
- Vue3 TS Vite NaiveUI搭建一個項目骨架
- 用一萬多字從頭到尾介紹【函數式編程】
- 這8張腦圖幾乎概括了所有的佈局方案,確定不看看嗎?
- 【戲玩算法】07-字典
- 還在console.log一把梭嗎?console還有其他騷操作