什么是圖？
在計算機程序設計中，圖結構也是一種非常常見的數據結構
但是圖論其實是一個非常大的話題
圖結構是一種與樹結構有些相似的數據結構
圖論是數學的一個分支，并且在數學概念上，樹是圖的一種
它以圖為研究對象，研究頂點和邊組成的圖形的數學理論和方法
主要研究的目的是事務之間的關系，定點代表事務，邊代表兩個事物間的關系
圖的現實案例
人與人之間的關系網
甚至科學家們在觀察人與人之間的關系網時，還發現了六度空間理論
六度空間理論
理論上認為世界任何不認識的兩個人只需要很少的中間人就可以建立起聯系。
并非一定經過六步，只是需要很少的步驟
圖通常有什么特點？
一組頂點：通常用V(Vertex)表示頂點的集合
一組邊：通常用E(Edge)表示邊的集合
邊是頂點和頂點之間的連線
邊可以是有向的，也可以是無向的
比如A—-B，通常表示無向
A—->B，通常表示有向
七橋問題
圖形一筆畫完的條件：有0個奇點或有2個奇點
我們來看一下口這個字有4個偶點0個奇點所以一筆能夠畫完(由雙數的邊連接的都是偶點，由單數的邊連接的都是奇點)
田字不能一筆畫成，因為它的奇點有四個(紅色)違反了規則。
圖的術語
頂點
頂點剛才我們已經介紹過了，表示圖中的一個節點
比如下圖中的數字
邊
邊剛才我們也介紹過了，表示頂點和頂點之間的連線
比如地鐵站中兩個站點之間的直接連線，就是一個邊
注意：這里的邊不要叫做路徑，路徑有其他的概念，待會兒我們會介紹
下圖中 0 – 1有一條邊，1 – 2有一條邊，0 – 2沒有邊
相鄰頂點
由一條邊連接在一起的頂點稱為相鄰頂點
度
一個頂點的度是相鄰頂點的數量
比如0頂點和其他兩個頂點相連，0頂點的度是2
比如1頂點和其他四個頂點相連，1頂點的度是4
路徑
路徑是頂點v1,v2…,vn的一個連續序列，比如下圖中0 1 5 9 就是一條路徑
簡單路徑：簡單路徑要求不包含重復的頂點，比如0 1 5 9是一條簡單路徑
回路：第一個頂點和最后一個頂點相同的路徑稱為回路 比如0 1 5 6 3 0
無向圖：
下圖圖就是一張無向圖，因為所有的邊都沒有方向
比如 0 – 1之間有邊，那么說明這條邊可以保證0 ->1，也可以保證1 ->0
無權圖:
下圖就是一張無權圖(邊沒有攜帶權重)，圖中的邊是沒有任何意義的。
不能說4-9的邊比0-1的邊更遠或者更長。
有向圖
有向圖表示的圖中的邊是有方向的
比如0->1,不能保證一定可以1->0,要根據方向來定，比如下圖就是一張有向圖
帶權圖
帶權圖表示邊有一定的權重
這里的權重可以是任意你希望表示的數據
比如距離或者花費的時間或者票價
圖的表示
怎么在程序中表示圖呢？
我們知道一個圖包含很多頂點，另外包含頂點和頂點之間的連線(邊)
這兩個都是非常重要的圖信息，因此都需要在程序中提現出來
頂點的表示相對簡單，我們先討論頂點的表示
上面的頂點，我們抽象成1 2 3 4，也可以抽象成A B C D
在后面的案例中，我們使用A B C D
那么這些A B C D我們可以使用一個數組來存儲起來(存儲所有的頂點)
當然A B C D有可能還表示其他含義的數據(比如村莊的名字)
那么邊如何表示呢？
因為邊是兩個頂點之間的關系，所以表示起來會稍微麻煩一些
鄰接表
鄰接表由圖中每個頂點以及和頂點相鄰的頂點列表組成
這個列表有很多種方式來存儲：數組/鏈表/哈希表都可以
圖片解析
比如我們要表示和A頂點有關聯的頂點(邊)，A和B/C/D有邊
那么我們可以通過A找到對應的數組/鏈表/哈希表，再取出其中的內容即可
鄰接表的問題：
鄰接表計算出度是比較簡單的(出度：指向別人的數量，入度:指向自己的數量)
鄰接表如果需要計算有向圖的入度，那么是非常麻煩的事情
它必須構造一個逆鄰接表，才能有效的計算入度，但是在開發中出度相對用的比較少
圖的遍歷思想
圖的遍歷思想和樹的遍歷思想是一樣的
圖的遍歷意味著需要將圖中每個頂點都訪問一遍，并且不能有重復的訪問
有兩種算法可以對圖進行遍歷
廣度優先搜索(Breadth-first Search,簡稱BFS)
深度優先搜索(Depth-First Search,簡稱DFS)
兩種遍歷算法都需要明確指定第一個被訪問的頂點
遍歷的思想
兩種算法的思想：
BFS：基于隊列，入隊列的頂點先被探索
DFS:基于棧或使用遞歸，通過將頂點存入棧中，頂點是沿著路徑被探索的，存在新的相鄰頂點就去訪問
為了記錄頂點是否被訪問過，我們同時使用三種顏色來反映他們的狀態：
白色：表示該頂點還沒有被訪問過
灰色：表示該頂點被訪問過，但未被探索過
黑色：表示該頂點被訪問過且被完全探索過
廣度優先搜索
廣度優先搜索算法思路：
廣度優先算法會從指定的第一個頂點開始遍歷圖，先訪問其所有的相鄰節點，就像一次訪問圖的一層，換句話說，就是先寬后深的訪問頂點
深度優先搜索思路：
深度優先搜索算法將會從第一個指定的頂點開始遍歷圖，沿著路徑知道這條路經最后被訪問了。
接著原路回退并探索下一條路徑
代碼實現
class Graph {
constructor() {
this.vertexes = [];
this.edges = [];
}
// 添加頂點
addVertex(v) {
this.vertexes.push(v);
this.edges[v] = [];
}
// 添加邊
addEdge(v1, v2) {
this.edges[v1].push(v2);
this.edges[v2].push(v1);
}
// toString
toString() {
let resString = '';
for (let i = 0; i < this.vertexes.length; i++) {
let v = this.vertexes[i];
resString += v + '->';
for (let j = 0; j < this.edges[v].length; j++) {
resString += this.edges[v][j]
}
resString += 'n'
}
return resString;
}
// 初始化顏色
initColors() {
let colors = [];
for (let i = 0; i < this.vertexes.length; i++) {
let v = this.vertexes[i];
for (let j = 0; j < this.edges[v].length; j++) {
colors[this.edges[v][j]] = 'white'
}
}
return colors;
}
// 廣度遍歷 bfs bfs(v, handler) {
let colors = this.initColors();
let items = [];
items.push(v);
colors[v] = 'gray';
while (items.length > 0) {
let headData = items.shift();
for (let i = 0; i < this.edges[headData].length; i++) {
let e = this.edges[headData][i];
if (colors[e] == 'white') {
colors[e] = 'gray';
items.push(e)
}
}
handler(headData)
colors[v] = 'black';
}
}
// dfs 深度遍歷
dfs(v, handler) {
let colors = this.initColors();
this.dfsSearch(v, handler, colors)
}
dfsSearch(v, handler, colors) {
colors[v] = 'gray';
handler(v);
colors[v] = 'black';
for (let i = 0; i < this.edges[v].length; i++) {
let e = this.edges[v][i];
if (colors[e] == 'white') {
this.dfsSearch(e, handler, colors)
}
}
}
}
代碼測試
let graph = new Graph();
//添加頂點操作
let myVertexes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];
myVertexes.forEach(v => graph.addVertex(v));
//添加邊操作
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('E', 'I');
//toString方法測試
alert(graph.toString());
//深度遍歷測試
let resString = '';
graph.dfs(myVertexes[0], function (key) {
resString += key + ' '
})
alert(resString)
//廣度遍歷測試
let resString1 = '';
graph.bfs(myVertexes[0], function (key) {
resString1 += key + ' '
})
alert(resString1)
程序員燈塔
轉載請注明原文鏈接：數據結構與算法學習——圖論
)
