用JavaScript实现图的广度优先和深度优先遍历

1.图的相关术语

1.1.有一条边相连的顶点叫相邻顶点;
1.2.一个顶点的度就是该顶点的相邻顶点数;
1.3.路径指顶点组成的连续序列;
1.4.简单路径没有重复顶点;
1.5.有向图和无向图


2.图的表示

2.1.邻接矩阵

图片描述
arrayi ===1代表i节点和j节点相邻,否则不相邻

2.2.邻接表

enter image description here
相当于把每个节点的相邻节点一一列举出来。

2.3.关联矩阵

形式和邻接矩阵一样,只是把邻接矩阵的直接维度换成对应的边,适用于边比顶点多的情况。

3.创建图类

图片描述
接下来就采用邻接表的方式创建上面的图并且采用字典来表示:

3.1.创建字典类

/创建字典类
    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查找特定的数值并返回,这里主要用来查找顶点对应的边数组
    this.get = function(key){
        return this.has(key) ? items[key] : undefined;
    }
}

3.2.创建图类

//创建图类Graph()
function Graph(){
    var vertices = [];    //用来储存顶点
    var adjList = new Dictionary();    //用来储存边

    //创建initializeColor用来初始化各个顶点的颜色,为遍历过程中的标记做准备
    var initializeColor = function(){
        var color = [];
        for (var i=0; i<vertices.length; i++){
            color[vertices[i]] = 'white';
        }
        return color;
    }
    
    //addVertex(key)用来添加顶点
    this.addVertex = function(v){
        vertices.push(v);
        adjList.set(v, []);
    }

    //addEdge(key,value)用来添加边v-w
    this.addEdge = function(v,w){
        adjList.get(v).push(w);
        adjList.get(w).push(v);
    }

    //toString()把邻接表转化成字符串的形式,便于输出显示
    this.toString = function(){
        var s = '';
        for(var i=0; i<vertices.length; i++){
            s += vertices[i] + '->';
            var neighbors = adjList.get(vertices[i]);
            for(var j=0; j<neighbors.length; j++){
                s += neighbors[j] + ' ';
            }
            s += '\n';
        }
        return s;
    }
}

3.3.创建实例

//创建实例
var graph = new Graph();
var myVertices = ['A','B','C','D','E','F','G','H','I'];
//添加顶点
for(var i=0; i<myVertices.length; i++){
    graph.addVertex(myVertices[i]);
}

//逐一加入边
graph.addEdge('A','B');
graph.addEdge('A','C');
graph.addEdge('A','D');
graph.addEdge('C','G');
graph.addEdge('C','D');
graph.addEdge('D','G');
graph.addEdge('D','H');
graph.addEdge('B','E');
graph.addEdge('B','F');
graph.addEdge('E','I');
console.log(graph.toString());

输出的结果为:

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.广度优先遍历

图片描述
采用队列的方式,先添加节点的先被探索;
采用三种颜色来反应节点的状态:
白色:还没被访问;
灰色:被访问但未被探索;
黑色:被访问且探索过;

思路:

首先搜索节点A,探索A节点的相邻节点B,C,D,把其加入队列中,再逐一出队列进行探索,从而实现广度遍历。

添加bfs方法

//广度优先遍历,在Graph()类中添加以下方法
    this.bfs = function(v, callback){
        var color = initializeColor();    //初始化节点,都标记为白色
        var queue = [];    //创建队列用来顶点的入队;
        queue.push(v);    //访问的节点入队列
        while(!queue.length==0){    //如果队列非空就执行以下
            var u = queue.shift();    //节点出队列
            var neighbors = adjList.get(u);  //探索节点对应的边
            color[u] = 'grey';    //把搜索过的节点变成灰色
            for (var i=0; i<neighbors.length; i++){  
                var w = neighbors[i];
                if(color[w] === 'white'){    //如果探索到的子节点是白色就逐一变灰并入队列
                    color[w] = 'grey';
                    queue.push(w);
                }
            }
            color[u] = 'black';        //节点完成搜索和探索的过程,直接变黑
            if(callback){    
                callback(u);        //回调函数,可以用来输出
            }
        }
    }

创建bfs实例

//bfs实例
function printNode(value){
    console.log('Visited vertex:'+value);
}
graph.bfs(myVertices[0],printNode);

bfs输出结果

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 = [];    //用来储存节点的前溯点
        queue.push(v);

        for(var i=0; i<vertices.length; i++){
            d[vertices[i]] = 0;        //初始化
            pred[vertices[i]] = null;
        }

        while(!queue.length == 0){
            var u = queue.shift();
            var neighbors = adjList.get(u);
            color[u] = 'grey';
            for (i=0; i<neighbors.length; i++){
                var w = neighbors[i];
                if(color[w] === 'white'){
                    color[w] = 'grey';
                    d[w] = d[u]+1;    //从头节点到w的距离
                    pred[w] = u;
                    queue.push(w);
                }
            } 
            color[u] = 'black';
        }
        return{
            distance:d,
            predecessers:pred
        }
    }

创建BFS实例

//BFS实例
var shortestPathA = graph.BFS(myVertices[0]);//需要输入头节点myVertices[0]
//console.log(shortestPathA);

//搜索路径BFS
var fromVertex = myVertices[0];
for (var i=1; i<myVertices.length; i++){
    var toVertex = myVertices[i];
    var path = [];    //path用来储存路径
    for (var v=toVertex; v!==fromVertex; v=shortestPathA.predecessers[v]){
        path.push(v);
    }
    path.push(fromVertex);
    var s = path.pop();
    while(!path.length==0){
        s += '-' + path.pop();
    }
    console.log(s)
}

BFS输出结果

A-B
A-C
A-D
A-B-E
A-B-F
A-C-G
A-D-H
A-B-E-I

4.2.深度优先遍历

图片描述
采用栈的方式,先添加节点的先被探索;
由递归实现。

图片描述

思路:

从节点A开始,探索到A的相邻节点B,C,D压入栈中(这里的代码采用for循环,所以没有实质上的栈,但是用栈更容易理解),接着搜索B,探索到B的相邻节点E,F压入栈中,以此递归。

添加dfs方法

this.dfs = function(callback){

var color = initializeColor();
for (var i=0; i<vertices.length; i++){
    if(color[vertices[i]]==='white'){
        dfsVisit(vertices[i], color, callback)//调用递归函数
    }
}

}

var dfsVisit = function(u, color, callback){

color[u] = 'grey';
if(callback){
    callback(u);
}
var neighbors = adjList.get(u);
for(var i=0; i<neighbors.length; i++){
    var w = neighbors[i];
    if(color[w] === 'white'){
        dfsVisit(w, color, callback);
    }
}
color[u] = 'black';

}

创建dfs实例

graph.dfs(printNode);

dfs输出结果

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

关注微信公众号“厦猿”,获取更多前端学习资料!
图片描述

评论

暂无评论