JS实现数据结构--无向图

邻接表

图的定义： 一个图包含很多顶点, 包含顶点和顶点之间的连线(边)

看下面这个图

顶点A B C D...我们很容易想到可以使用一个数组来存储起来

那么他们之间的边怎么表示？

这里使用邻接表的方式来表示，左边列是每个顶点，右边列是每个顶点的相邻顶点

如何存储

代码上可以使用Map来存储这种邻接表

function Graph(){
    //顶点属性
    this.vertexes = [];
    //边属性
    this.edges = new Map();

	/*
	将添加的顶点放入到数组中.
	给该顶点创建一个数组[], 该数组用于存储顶点连接的顶点
	*/
    Graph.prototype.addVertex = function(v){
        this.vertexes.push(v);
        this.edges.set(v,[]);
    }

	/*
	添加边需要传入两个顶点, 因为边是两个顶点之间的边
	根据顶点v1取出其相邻顶点数组, 将v2加入
	根据顶点v2取出其相邻顶点数组, 将v1加入
	*/
    Graph.prototype.addEdge = function(v1,v2){
        this.edges.get(v1).push(v2);
        this.edges.get(v2).push(v1);
    }
}

为了测试代码，重写一下toString方法

    //toString方法
    Graph.prototype.toString = function(){
        let str = '';
        this.edges.forEach((edges,vertex)=>
            str += vertex + '->' + edges + '\n'
        )
        return str;
    }

测试代码

//测试代码
let graph = new Graph();

//添加顶点
let myVertexes = ["A", "B", "C", "D", "E", "F", "G", "H", "I"];
/*
	为什么不直接赋值
 	graph.vertexes = myVertexes;
	直接赋值没有建立顶点和边的一个对应集合，所以最好是遍历顶点调用addVertex
*/
for (let i = 0; i < myVertexes.length; i++) {
    graph.addVertex(myVertexes[i]);
}

//添加边
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I');

console.log(graph.toString())

<——邻接表

图的遍历

图的遍历必须访问每个第一次访问的节点, 并且追踪有哪些顶点还没有被访问到。

怎么追踪？

我们设置三种颜色标记顶点的状态

以下代码也是写在Graph这个构造函数内

    //白色-未访问过的顶点
    //灰色-访问过但未探索的顶点（这里的探索指去查看该顶点的相邻顶点）
    //黑色-被探索过的顶点

    //初始化所有顶点的颜色-白色
    //内部用，静态方法，不用写在prototype上
    this.initializeColor = function(){
        //用对象来存,顶点为属性，值为白色
        let color = {};
        for(let i = 0;i<this.vertexes.length;i++){
            color[this.vertexes[i]] = 'white';
        }
        return color;
    }

广度遍历BFS

广度优先搜索(Breadth-First Search, 简称BFS)，代码用队列实现

这里我导入了之前封装的队列构造函数

JavaScript实现数据结构--队列、优先队列

    //广度遍历图 bfs方法
    Graph.prototype.bfs = function(v,handler){
        //初始化颜色
        let color =  this.initializeColor();

        //使用队列来实现
        let queue = new Queue();
        //把顶点放入队列
        queue.enqueue(v);

        //判断队列是否为空
        while(!queue.isEmpty()){
            //取出前端顶点
            let queueV = queue.dequeue();

            //获取该顶点的相邻顶点
            let neighborV = this.edges.get(queueV);
            //访问该顶点的相邻顶点(指加入到队列中)
            for(let i = 0;i < neighborV.length;i++){
                //判断是否重复访问
                if(color[neighborV[i]] === 'white'){
                    queue.enqueue(neighborV[i]);
                    //标记访问过
                    color[neighborV[i]] = 'grey';
                }
            }

            if(handler){
                handler(queueV);
            }
            //该顶点被探索完了，标记黑色
            color[queueV] = 'black';
        }
    }

   

测试代码

//测试bfs遍历图
/*
我在学习的过程看见弹幕有人问：
为什么遍历图不直接遍历数组，而要用深度广度方法遍历呢？

虽然是用数组存储的，但是数组存储是没有顶点间的关系的。
0~N遍历完数组，结果是什么关系都没体现出来（图顶点间关系）。
我们要根据图顶点间的关系进行遍历，结果是不一样的。
也就是说
bfs和dfs遍历的结果是不一样的。
*/
let res = '';
graph.bfs(graph.vertexes[0],function(v){
    res += v + ' ';
})
console.log(res);

深度遍历DFS

深度优先搜索(Depth-First Search, 简称DFS)，类似与二叉树的先序搜索，代码用递归实现

 //深度遍历图 dfs方法
    Graph.prototype.dfs =  function(v,handler){
        //初始化颜色
        let color = this.initializeColor();
        //使用递归实现
        this.dfsVist(v,color,handler);
    }
    this.dfsVist = function(v,color,handler){
        //访问该顶点
        color[v] = 'grey';
        //处理顶点
        if(handler){
            handler(v);
        }

        //获取顶点的相邻顶点
        let neighborV = this.edges.get(v);

        for(let i=0;i< neighborV.length;i++){
            if(color[neighborV[i]] === 'white'){
                this.dfsVist(neighborV[i],color,handler);
            }
        }

        //探索完成，标记为黑色
        color[v] = 'black';
    }

测试代码

//测试dfs遍历图
let res1 = '';
graph.dfs(graph.vertexes[0],function(v){
    res1 += v + ' ';
})
console.log(res1);