摘要：圖的相關(guān)術(shù)語有一條邊相連的頂點(diǎn)叫相鄰頂點(diǎn)一個(gè)頂點(diǎn)的度就是該頂點(diǎn)的相鄰頂點(diǎn)數(shù)路徑指頂點(diǎn)組成的連續(xù)序列簡單路徑?jīng)]有重復(fù)頂點(diǎn)有向圖和無向圖圖的表示鄰接矩陣代表節(jié)點(diǎn)和節(jié)點(diǎn)相鄰，否則不相鄰鄰接表相當(dāng)于把每個(gè)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)一一列舉出來。

1.1.有一條邊相連的頂點(diǎn)叫相鄰頂點(diǎn)；
1.2.一個(gè)頂點(diǎn)的度就是該頂點(diǎn)的相鄰頂點(diǎn)數(shù)；
1.3.路徑指頂點(diǎn)組成的連續(xù)序列；
1.4.簡單路徑?jīng)]有重復(fù)頂點(diǎn)；
1.5.有向圖和無向圖

arrayi ===1代表i節(jié)點(diǎn)和j節(jié)點(diǎn)相鄰，否則不相鄰

相當(dāng)于把每個(gè)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)一一列舉出來。

形式和鄰接矩陣一樣，只是把鄰接矩陣的直接維度換成對應(yīng)的邊，適用于邊比頂點(diǎn)多的情況。

接下來就采用鄰接表的方式創(chuàng)建上面的圖并且采用字典來表示：

/創(chuàng)建字典類
    function Dictionary(){
    var items = {};
    
    //set(key,value)向字典里添加新元素，這里主要用來添加邊
    this.set = function(key,value){
        items[key] = value;
    }

    //has(key)如果存在就返回true，否則false
    this.has = function(key){
        return key in items;
    }

    //get(key)通過key查找特定的數(shù)值并返回，這里主要用來查找頂點(diǎn)對應(yīng)的邊數(shù)組
    this.get = function(key){
        return this.has(key) ? items[key] : undefined;
    }
}

//創(chuàng)建圖類Graph()
function Graph(){
    var vertices = [];    //用來儲存頂點(diǎn)
    var adjList = new Dictionary();    //用來儲存邊

    //創(chuàng)建initializeColor用來初始化各個(gè)頂點(diǎn)的顏色，為遍歷過程中的標(biāo)記做準(zhǔn)備
    var initializeColor = function(){
        var color = [];
        for (var i=0; i";
            var neighbors = adjList.get(vertices[i]);
            for(var j=0; j
3.3.創(chuàng)建實(shí)例
//創(chuàng)建實(shí)例
var graph = new Graph();
var myVertices = ["A","B","C","D","E","F","G","H","I"];
//添加頂點(diǎn)
for(var i=0; i
輸出的結(jié)果為：
A->B C D 
B->A E F 
C->A G D 
D->A C G H 
E->B I 
F->B 
G->C D 
H->D 
I->E 

4.圖的遍歷
4.1.廣度優(yōu)先遍歷

采用隊(duì)列的方式，先添加節(jié)點(diǎn)的先被探索；
采用三種顏色來反應(yīng)節(jié)點(diǎn)的狀態(tài)：
白色：還沒被訪問；
灰色：被訪問但未被探索；
黑色：被訪問且探索過；
思路：
首先搜索節(jié)點(diǎn)A，探索A節(jié)點(diǎn)的相鄰節(jié)點(diǎn)B,C,D,把其加入隊(duì)列中，再逐一出隊(duì)列進(jìn)行探索，從而實(shí)現(xiàn)廣度遍歷。
添加bfs方法
//廣度優(yōu)先遍歷，在Graph()類中添加以下方法
    this.bfs = function(v, callback){
        var color = initializeColor();    //初始化節(jié)點(diǎn)，都標(biāo)記為白色
        var queue = [];    //創(chuàng)建隊(duì)列用來頂點(diǎn)的入隊(duì)；
        queue.push(v);    //訪問的節(jié)點(diǎn)入隊(duì)列
        while(!queue.length==0){    //如果隊(duì)列非空就執(zhí)行以下
            var u = queue.shift();    //節(jié)點(diǎn)出隊(duì)列
            var neighbors = adjList.get(u);  //探索節(jié)點(diǎn)對應(yīng)的邊
            color[u] = "grey";    //把搜索過的節(jié)點(diǎn)變成灰色
            for (var i=0; i
創(chuàng)建bfs實(shí)例
//bfs實(shí)例
function printNode(value){
    console.log("Visited vertex:"+value);
}
graph.bfs(myVertices[0],printNode);

bfs輸出結(jié)果
Visited vertex:A
Visited vertex:B
Visited vertex:C
Visited vertex:D
Visited vertex:E
Visited vertex:F
Visited vertex:G
Visited vertex:H
Visited vertex:I

使用BFS尋找最短路徑

this.BFS = function(v){
        var color = initializeColor(),
        queue = [],
        d = [],    //用來儲存從v到u的距離
        pred = [];    //用來儲存節(jié)點(diǎn)的前溯點(diǎn)
        queue.push(v);

        for(var i=0; i
創(chuàng)建BFS實(shí)例
//BFS實(shí)例
var shortestPathA = graph.BFS(myVertices[0]);//需要輸入頭節(jié)點(diǎn)myVertices[0]
//console.log(shortestPathA);

//搜索路徑BFS
var fromVertex = myVertices[0];
for (var i=1; i
BFS輸出結(jié)果
A-B
A-C
A-D
A-B-E
A-B-F
A-C-G
A-D-H
A-B-E-I

4.2.深度優(yōu)先遍歷

采用棧的方式，先添加節(jié)點(diǎn)的先被探索；
由遞歸實(shí)現(xiàn)。

思路：
從節(jié)點(diǎn)A開始，探索到A的相鄰節(jié)點(diǎn)B,C,D壓入棧中（這里的代碼采用for循環(huán)，所以沒有實(shí)質(zhì)上的棧，但是用棧更容易理解），接著搜索B，探索到B的相鄰節(jié)點(diǎn)E,F壓入棧中，以此遞歸。
添加dfs方法
this.dfs = function(callback){
var color = initializeColor();
for (var i=0; i
}
var dfsVisit = function(u, color, callback){
color[u] = "grey";
if(callback){
    callback(u);
}
var neighbors = adjList.get(u);
for(var i=0; i
}
創(chuàng)建dfs實(shí)例
graph.dfs(printNode);

dfs輸出結(jié)果
Visited vertex:A
Visited vertex:B
Visited vertex:E
Visited vertex:I
Visited vertex:F
Visited vertex:C
Visited vertex:G
Visited vertex:D
Visited vertex:H

關(guān)注微信公眾號“廈猿”，獲取更多前端學(xué)習(xí)資料！