1. 圖
1.1了解圖
圖是網(wǎng)狀結(jié)構(gòu)的抽象模型,圖示由一組由邊連接的節(jié)點.它由節(jié)點邊組成,節(jié)點之間的由邊連接,一個節(jié)點可以對應(yīng)很多.(這些邊的數(shù)量稱為這個節(jié)點度).相鄰節(jié)點的順序組成的序列叫做路徑.路徑中由沒有重復(fù)節(jié)點的叫做簡單路徑.路徑中最后一個頂點和第一個節(jié)點相同的構(gòu)成環(huán),有向圖的邊帶箭頭的(有序的).每個節(jié)點都有邊的圖強(qiáng)連通圖.
我們還可以使用圖來表示道路、航班以及通信,下面是一個非常簡單的圖
下面我們來介紹圖的一些基本概念
由一些邊連接在一起的頂點稱為相鄰頂點,比如,在上圖中A和B相鄰的, A和C相鄰的,A和E是不相鄰的.
一個頂點的度是其相鄰頂點的數(shù)量, 比如,A和其他兩個頂點相連接,因此A的度為2.
路徑是頂點v1,v2,...v3的一個連續(xù)序列,其中vi和vi+1是相鄰的,以上的示意圖中,其中包含路徑是ABE和ACG
簡單路徑要求不包含重復(fù)的頂點,舉個例子,ACG就是一個簡單路徑.除去最后一個頂點(因為它和第一個頂點是同一個頂點),環(huán)也是一個簡單路徑,比如ABCA(最后一個頂點重新回到A).
1.2 創(chuàng)建圖
要儲存圖中的節(jié)點, 并且表明節(jié)點間邊的關(guān)系,我們可以采用多種方法來實現(xiàn).最常見的有鄰接矩陣和鄰接表
鄰接矩陣
鄰接矩陣的屬性比較復(fù)雜,每個節(jié)點都和一個整數(shù)相關(guān)聯(lián),該整數(shù)將作為數(shù)組的索引.我們用一個二維數(shù)組來表示頂點之間的連接.如果索引為i的節(jié)點和j相鄰,則array[i][j] === 1,否者array[i][j] === 0.如下圖所示
假設(shè)我們有如下的圖
此時對應(yīng)的鄰接矩陣如下圖:
鄰接矩陣使用二維數(shù)組來描述節(jié)點間的連接關(guān)系.但是當(dāng)節(jié)點比邊多很多時,此時我們可以很明顯的看到矩陣中將會有很多0, 這意味著我們浪費了計算機(jī)的儲存空間來表示了根本不存在的邊.例如,當(dāng)我們要找給定頂點的相鄰頂點,我們也不得不迭代一整行.鄰接矩陣表示不夠好的另一個理由是,圖中的頂點可能會改變,而二維數(shù)組不太靈活.
鄰接表
我們也可以使用一種叫做鄰接表的方法來表示圖.鄰接表由圖中每個頂點的相鄰頂點列表組成.存在好幾種發(fā)生來表示這種數(shù)據(jù)結(jié)構(gòu).我們可以用列表(數(shù)組),鏈表,甚至是哈希表或是字典來表示相鄰頂點表.下面的列表展示了鄰接表的數(shù)據(jù)結(jié)構(gòu).
- A: B C
- B: D
- C: B
- D: B
接下來我們使用鏈接表的方法來創(chuàng)建圖
// 圖結(jié)構(gòu) 類
class Graph {
constructor() {
// 儲存所有的節(jié)點
this.vertices = [];
// 儲存每個頂點對應(yīng)的相鄰頂點
this.edges = {}
}
// 添加頂點
addVertex(...rest) {
rest.map(v => {
// 如果頂點已經(jīng)添加 return
if (this.vertices.includes(v)) return
//頂點不存在 添加頂點
this.vertices.push(v);
// 初始化頂點的邊儲存信息
this.edges[v] = [];
})
}
// 添加邊
addEdge(v, w) {
// 如果不存在對應(yīng)的節(jié)點, 則添加到圖中
if(!this.vertices.includes(v) || !this.vertices.includes(w)){
this.addVertex(v, w);
}
// 如果兩個頂點之間已經(jīng)存在相鄰關(guān)系,則返回
if (this.edges[v].includes(w)) return;
//兩個頂點之間相互添加邊信息
this.edges[v].push(w);
this.edges[w].push(v);
}
}
接下來我們來簡單測試一下這個代碼
let graph = new Graph();
graph.addVertex('A','B',"C",'D');
graph.addEdge('A','B')
graph.addEdge('B', 'C')
graph.addEdge('B', 'D')
graph.addEdge('C', 'D');
graph.addEdge('C', 'A');
console.log(graph)
為了更方便的我們調(diào)試,我們來實現(xiàn)Graph類的toString方法,以便在控制臺來輸出圖
toString(){
let s = "";
for(let vertice of this.vertices){
s += `${vertice} --->`;
for(let edg of this.edges[vertice]){
s += `${edg}`;
}
s += '\n'
}
return s
}
我們?yōu)猷徑颖肀硎痉?gòu)建了一個字符串, 首先迭代vertices數(shù)組列表,將其每一項的頂點追加到字符串中,接著我們通過這個頂點取出該頂點的所有鄰接表,同樣我們迭代該鄰接表,并將其相鄰頂點追加到我們的字符串中,鏈接表迭代完成后,我們該該字符串添加一個換行符,這樣我們可以在控制臺看到應(yīng)該漂亮的輸出.此時控制臺輸入如下:
A --->BC
B --->ACD
C --->BDA
D --->BC
1.3 圖的遍歷
和樹的數(shù)據(jù)結(jié)構(gòu)類似, 我們也可以實現(xiàn)訪問圖中的所有節(jié)點.有兩種算法可以實現(xiàn)對圖的遍歷:廣度優(yōu)先搜索和深度優(yōu)先搜索.圖的遍歷可以用來尋找特定的節(jié)點或者兩個頂點之間的路徑,檢測圖是否連通,檢測圖是否含有環(huán),等等,
圖遍歷算法的核心思想是必須追蹤每一次訪問的節(jié)點,并且追蹤有哪些節(jié)點還沒有被完全探索.對于兩種圖的遍歷算法.都需要明確指出第一次被訪問的節(jié)點.
當(dāng)要標(biāo)注的節(jié)點已經(jīng)訪問過的節(jié)點時, 此時我們需要用三種顏色來反映它們的狀態(tài).
- 白色: 表示該節(jié)點還沒有被訪問過.
- 灰色: 表示該節(jié)點被訪問過, 但還未被探索過.
- 黑色: 表示該頂點被訪問過且被完全探索過.
const Colors = {
WHITE:0,
CRET:1,
BLACK:2,
}
為了有助于在廣度優(yōu)先和深度優(yōu)先算法中標(biāo)記頂點,我們使用Colors變量(作為一個枚舉器),聲明如下,
兩個算法實現(xiàn)之前還需要一個輔助對象來幫助儲存頂點是否被儲存過.在每個算法的前頭,所有的頂點會被標(biāo)記為未訪問.我們使用下面的函數(shù)來初始化每個頂點的顏色.
const initializeColor = vertices =>{
let color = {};
for(let i=0,len=vertices.length;i<len;i++){
color[vertices[i]] = Colors.WHITE;
}
return color
}
1.3.1廣度優(yōu)先遍歷
廣度優(yōu)先搜索算法會從指定的第一次頂點開始遍歷,先訪問其所有的鄰點,就像一次訪問圖的一層.換句話來說,就是先寬后深地訪問頂點.
廣度優(yōu)先遍歷和深度優(yōu)先遍歷的算法基本都相同,只有一點不同,那就是待訪問頂點的數(shù)據(jù)結(jié)構(gòu).廣度優(yōu)先遍歷使用的是數(shù)據(jù)結(jié)構(gòu)為隊列.下面我們來簡單地來實現(xiàn)一個隊列類.代碼如下.
// 單向隊列
class Queue {
constructor() {
this.queue = []
}
//入隊
enqueue(...items){
return items.map(item => {
this.queue.push(item);
return item
})
}
// 出隊
dequeue(){
return this.queue.shift()
}
// 返回隊頭
first(){
return this.queue[0];
}
//清空隊列
clear(){
this.queue = [];
}
// 返回隊列的長度
size(){
return this.items.length;
}
//隊列是否為空
isEmpty(){
return this.size() === 0
}
}
以下是從頂點v開始的廣度優(yōu)先搜索算法的核心步驟
- 創(chuàng)建一個隊列Q.
- 將頂點v標(biāo)注為灰色,并加入隊列.
- 如果隊列q非空. 則進(jìn)行以下遍歷步驟.
- 從隊列Q中取出u;
- 標(biāo)注u為被發(fā)現(xiàn)的(灰色);
- 將所有未被訪問的的鄰點(白色)加入隊列;
- 標(biāo)注頂點u為已被探索的(黑色)
下面我們來簡單實現(xiàn)廣度優(yōu)先搜索算法.為了方便, 我們直接在Graph類中實現(xiàn)一個bfs(breadthFirstSearch)方法.
bfs(startVertex,callback){
const vertices = this.vertices;
const edges = this.edges;
const color = initializeColor(vertices);
const queue = new Queue();
// 入口頂點入隊
quene.enQueue(startVertex)
//循環(huán)隊列進(jìn)行發(fā)現(xiàn)或探索
while(!quene.isEmpty()){
// 取出隊首頂點
const u = queue.deQueue();
// 獲取頂點對應(yīng)的相鄰頂點
const neighbors = edges[u];
//標(biāo)注頂點為灰色
color[u] = Colors.GREY;
//探索頂點u的所有鄰點列表
neighbors.forEach(w =>{
// 如果鄰點不為白色,說明節(jié)點已經(jīng)被訪問過了, 則不進(jìn)行任何操作
if(color[w] !== Colors.WHITE) return;
// 將u所有未被訪問的節(jié)點加入隊列, 并標(biāo)注為灰色
quene.enQueue(w);
color[w] = Colors.GREY
})
// 探索結(jié)束,改變狀態(tài)為BLACK
color[u] = Colors.BLACK;
// 如果存在callback, 則將頂點u傳入?yún)?shù)傳遞到callback
if(callback){
callback(u)
}
}
}
上面的bfs方法接受一個頂點和可選的callback函數(shù)方便來訪問廣度優(yōu)先搜索到的每一個節(jié)點,在實現(xiàn)bfs算法之前我們第一次事情就是用initialize函數(shù)來將color數(shù)組初始化為白色.我們還需要聲明一個和創(chuàng)建一個Quene實例,它將會儲存代訪問和待探索的節(jié)點.
接下來我們來用之前的圖實例來簡單測試一下這個方法
graph.bfs('A',(v) =>{
console.log(v)
})
// 依次在控制臺打印 A B C D
1.3.2使用bfs尋找最短路徑
利用bfs我們可以輸出訪問頂點的順序,但是bfs的用途遠(yuǎn)不止如此, 我們還可以使用bfs來找尋最短路徑,例如我們考慮如下問題.
給定一個圖G和源頂點v,找出頂點u和v之間最短路徑的距離.
對于給定的頂點v,廣度優(yōu)先算法會訪問所有的與其距離為1的頂點,接著是距離為2的頂點.所以我們可以使用廣度優(yōu)先算法來解決這個問題.我們可以稍微修改一下我們之前寫的bfs方法以返回給我們一些信息.
- 從v到u的距離distances[u]
- 從v到u的具體路徑
BFS(v){
const vertices = this.vertices;
const edges = this.edges;
const color = initializeColor(vertices);
const queue = new Queue();
const info = {}
// 入口頂點入隊, 狀態(tài)改變, 初始信息
queue.enqueue(v);
color[v] = Colors.GREY;
info[v] = {distance:0, path:v}
//發(fā)現(xiàn)和探索
while(!queue.isEmpty()){
//獲取頂點和其所有鄰點
const u = queue.dequeue();
const neighbors = edges[u];
color[u] = Colors.GREY;
neighbors.forEach(w =>{
if(color[w] !== Colors.WHITE) return;
color[w] = Colors.GREY;
//記錄對應(yīng)的鄰點w和u組之間的距離和路徑
info[w] = {
distance:info[u].distance+1,
path:info[u].path + '->' + w
}
queue.enqueue(w)
})
color[u] = Colors.GREY
}
return info
}
當(dāng)我們對頂點u的鄰點進(jìn)行探索時,我們會判斷當(dāng)前鄰點是否被訪問過, 如果沒有被訪問過, 此時我們將鄰點的狀態(tài)設(shè)置為被訪問過,并記錄鄰點w和u之間的距離.我們還通過info[u] .distance+ 1 `來增加u和w之間的距離,并且將w的頂點u的路徑path和w連接累積起來,并記錄在info[w]上.
let graph = new Graph;
graph.addEdge("A" , "B");
graph.addEdge("A" , "C");
graph.addEdge("A" , "E");
graph.addEdge("B" , "D");
graph.addEdge("B" , "E");
graph.addEdge("C" , "F");
graph.addEdge("E" , "F");
console.log(graph.BFS("A"));
此時我們會得到如下輸出
{
A: {distance: 0, path: "A"}
B: {distance: 1, path: "A->B"}
C: {distance: 1, path: "A->C"}
D: {distance: 2, path: "A->B->D"}
E: {distance: 1, path: "A->E"}
F: {distance: 2, path: "A->C->F"}
}
這意味著頂點A與B、C、E的距離為1, 與頂點D、F的距離為2. 對應(yīng)的路徑在path字段中, 我們可以很方便的看到對應(yīng)的路徑信息.
1.3.3深度優(yōu)先搜索算法
深度優(yōu)先搜索算法將會從第一個指定的頂點開始遍歷圖,沿著路徑直到這條路徑最后一個頂點被訪問了, 接著原路回退并探索下一條路徑.換句話來說,它是先深度后廣度地訪問節(jié)點.
深度優(yōu)先搜索算法不需要一個源頂點,在深度優(yōu)先搜索算法中,若圖中的頂點v未訪問,則訪問該頂點v,要訪問頂點v,照如下步驟做:
- 標(biāo)注v為被發(fā)現(xiàn)的(灰色)
- 對于v的所有被訪問的(白色)的鄰點w,訪問頂點w.
- 標(biāo)注v為已被探索的(黑色).
深度優(yōu)先搜索的步驟為是遞歸的,這意味值深度優(yōu)先搜索算法使用棧來儲存函數(shù)調(diào)用(由遞歸調(diào)用所創(chuàng)建的棧)
接下來我們來簡單實現(xiàn)深度優(yōu)先算法
// 遞歸探索頂點
const dfsWalk = (u,color,edgs,callback) =>{
// 將頂點u狀態(tài)設(shè)為灰色(已發(fā)現(xiàn))
color[u] = Colors.GREY;
if(callback) callback(u);
// 獲取頂點對應(yīng)的鄰點列表
const neighbors = edgs[u];
// 探索頂點的所有鄰點
neighbors.forEach(w =>{
// 如果鄰點w狀態(tài)為白色(未被訪問), 則遞歸調(diào)用dfsWalk, 添加頂點w入棧
if(w !== Colors.WHITE) return;
dfsWalk(w,color,edgs,callback)
})
// 探索結(jié)束, 將狀態(tài)設(shè)置黑色(已被探索)
color[u] = Colors.BLACK
}
//深度優(yōu)先搜索
const dfs = (graph,callback) =>{
// 淺拷貝圖中的所有頂點和鄰點列表
const vertices = {...graph.vertices};
const edges = {...graph.edges};
const color = initializeColor(vertices);
//探索所有的頂點
Object.values(vertices).forEach(v =>{
dfsWalk(v,color,edges,callback)
})
}
接下來來調(diào)用dfs函數(shù)
dfs(graph,(v) =>{
console.log(v)
})
依次在控制臺輸出 A B C E D F
