是什么

圖是一種抽象的數(shù)據(jù)類型，在圖中的數(shù)據(jù)元素通常稱作節(jié)點，V是所以定點的集合，E是所有邊的集合

圖的分類

有向圖

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

無向圖

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

常見的圖表達方式

鄰接矩陣

通過一個二維數(shù)組G[N][N]表示N個點到N-1編號，通過鄰街矩陣可以立即看到兩個訂單直接是否存在一條邊

鄰接表

存儲方式如下

在javascript中永Object進行表示

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

用數(shù)組進行表示

?代碼A

const graph = {0: [1, 4],1: [2, 4],2: [2, 3],3: [],4: [3], }

常見的操作方式

深度優(yōu)先遍歷

廣度優(yōu)先遍歷

數(shù)據(jù)如上面的代碼A

深度優(yōu)先

const visited = new Set()
const dfs = (n) => {console.log(n)visited.add(n) // graph[n].forEach(c => {if(!visited.has(c)){ //demo，第一次，遍歷graph下的graph[1]和graph[4]dfs(c)}}) }dfs(0)

結(jié)果:0,1,2,3,4

這里只是恰巧是順數(shù)，如果把graph[0]改為[4,1]那結(jié)果會變成0，4，3，1，2

廣度優(yōu)先

const visited = new Set()
const dfs = (n) => {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)}})} }dfs(0)

結(jié)果

0，1，?4，2，3

備注

上面的set是用來做去重的?

使用場景

社交網(wǎng)絡(luò)。

社交網(wǎng)絡(luò)是典型的網(wǎng)絡(luò)結(jié)構(gòu)，圖可以用點來表達社交關(guān)系中的人，用點與點之間的連接來表達人與人的關(guān)系。比如我們想要去表示誰認識誰、誰和誰溝通、誰能夠影響誰等人與人之間的關(guān)系。一個具體的例子是在小紅書上，比如，A 關(guān)注了 B 的小紅書，可以用 A 指向 B 的線來連接表示。這些人與人的社交信息，可以用來去解釋社交網(wǎng)絡(luò)的信息流動。人與人之間的聯(lián)系也定義了我們是誰。

交通網(wǎng)絡(luò)。

交通網(wǎng)絡(luò)也可以用圖來表達。比如所有的城市可以用圖的節(jié)點來表示，城市間的交通渠道可以用邊來表示。像最近大家關(guān)注的疫情封城措施，也可以用數(shù)據(jù)結(jié)構(gòu)來理解，就是把交通網(wǎng)絡(luò)圖的一些邊進行了阻隔。
互聯(lián)網(wǎng)網(wǎng)站連接。

我們經(jīng)?？吹骄W(wǎng)站上會有指向其他網(wǎng)址的超鏈接。如果我們把互聯(lián)網(wǎng)所有的網(wǎng)頁定義成圖的節(jié)點，那么網(wǎng)頁與網(wǎng)頁之間的邊就是這些鏈接了。如果大家熟悉 Google 經(jīng)典的網(wǎng)頁排名算法 PageRank，就會知道，搜索引擎正是用指向一個網(wǎng)頁的引用數(shù)量去判斷一個網(wǎng)頁的質(zhì)量。

第 13 講：用圖來表達更為復雜的數(shù)據(jù)關(guān)系 · 數(shù)據(jù)結(jié)構(gòu)精講：從原理到實戰(zhàn) · 看云

更多

https://www.cnblogs.com/jaxu/p/11338294.html