一、是什么
在計算機科學中，圖是一種抽象的數(shù)據(jù)類型，在圖中的數(shù)據(jù)元素通常稱為結點，V是所有頂點的集合，E是所有邊的集合
如果兩個頂點v,w，只能由v向w，而不能由w向v，那么我們就把這種情況叫做一個從?v?到?w?的有向邊。v也被稱做初始點，w也被稱為終點。這種圖就被稱做有向圖
如果v和w是沒有順序的，從v到達w和從w到達v是完全相同的，這種圖就被稱為無向圖
圖的結構比較復雜，任意兩個頂點之間都可能存在聯(lián)系，因此無法以數(shù)據(jù)元素在存儲區(qū)中的物理位置來表示元素之間的關系
常見表達圖的方式有如下：
-
鄰接矩陣
-
鄰接表
鄰接矩陣
通過使用一個二維數(shù)組G[N][N]進行表示N個點到N-1編號，通過鄰接矩陣可以立刻看出兩頂點之間是否存在一條邊，只需要檢查鄰接矩陣行i和列j是否是非零值，對于無向圖，鄰接矩陣是對稱的
鄰接表
存儲方式如下圖所示：
?在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ù)據(jù)結構還可能包含和每條邊相關聯(lián)的數(shù)值（edge value），例如一個標號或一個數(shù)值（即權重，weight；表示花費、容量、長度等）
二、操作
關于的圖的操作常見的有：
- 深度優(yōu)先遍歷
- 廣度優(yōu)先遍歷
首先構建一個圖的鄰接矩陣表示，如下面的圖：
?用代碼表示則如下：
const graph = {
0: [1, 4],
1: [2, 4],
2: [2, 3],
3: [],
4: [3],
}
深度優(yōu)先遍歷
也就是盡可能的往深處的搜索圖的分支
實現(xiàn)思路是，首先應該確定一個根節(jié)點，然后對根節(jié)點的沒訪問過的相鄰節(jié)點進行深度優(yōu)先遍歷
確定以 0 為根節(jié)點，然后進行深度遍歷，然后遍歷1，接著遍歷 2，然后3，此時完成一條分支0 - 1- 2- 3的遍歷，換一條分支，也就是4，4后面因為3已經(jīng)遍歷過了，所以就不訪問了
用代碼表示則如下：
const visited = new Set()
const dfs = (n) => {
console.log(n)
visited.add(n) // 訪問過添加記錄
graph[n].forEach(c => {
if(!visited.has(c)){ // 判斷是否訪問呢過
dfs(c)
}
})
}
廣度優(yōu)先遍歷
先訪問離根節(jié)點最近的節(jié)點，然后進行入隊操作，解決思路如下：
- 新建一個隊列，把根節(jié)點入隊
- 把隊頭出隊并訪問
- 把隊頭的沒訪問過的相鄰節(jié)點入隊
- 重復二、三步驟，知道隊列為空
用代碼標識則如下：
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)
}
})
}
}
三、總結
通過上面的初步了解，可以看到圖就是由頂點的有窮非空集合和頂點之間的邊組成的集合，分成了無向圖與有向圖
圖的表達形式可以分成鄰接矩陣和鄰接表兩種形式，在javascript中，則可以通過二維數(shù)組和對象的形式進行表達
圖實際是很復雜的，后續(xù)還可以延伸出無向圖和帶權圖，對應如下圖所示：
文章來源：http://www.zghlxwxcb.cn/news/detail-855150.html
參考文獻
- 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
如果對您有所幫助，歡迎您點個關注，我會定時更新技術文檔，大家一起討論學習，一起進步。
?
文章來源地址http://www.zghlxwxcb.cn/news/detail-855150.html
到了這里，關于說說你對圖的理解？相關操作有哪些？的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
