javascript数据结构与算法：图的遍历、广度｜深度优先搜索

2.1 图的相关概念

由一条边连接在一起的顶点称为相邻顶点。一个顶点的度是其相邻顶点的数量。如果图中不存在环,则称该图是无环的。

如果图中每两个顶点间都存在路径,则该图是连通的。

图可以是无向的(边没有方向)或是有向的(有向图)。

图还可以是未加权的或是加权的。

图最常见的实现是邻接矩阵。每个节点都和一个整数相关联,该整数将作为数组的索引。我 们用一个二维数组来表示顶点之间的连接。如果索引为i的节点和索引为j的节点相邻,则array[i][j] === 1,否则array[i][j] === 0,邻接矩阵如下图所示:

我们也可以使用一种叫作邻接表的动态数据结构来表示图。邻接表由图中每个顶点的相邻顶点列表所组成。存在好几种方式来表示这种数据结构。我们可以用列表(数组)、链表,甚至是 散列表或是字典来表示相邻顶点列表。下面的示意图展示了邻接表数据结构。

我们还可以用关联矩阵来表示图。在关联矩阵中,矩阵的行表示顶点,列表示边。如下图所示,我们使用二维数组来表示两者之间的连通性,如果顶点v是边e的入射点,则array[v][e] === 1; 否则,array[v][e]===0。关联矩阵通常用于边的数量比顶点多的情况下,以节省空间和内存。

尽管邻接表可能对大多数问题来说都是更好的选择,但以上两种表示法都很有用,且它们有 着不同的性质(例如,要找出顶点v和w是否相邻,使用邻接矩阵会比较快)。在后面示例中, 我们将会使用邻接表表示法。

2.2 图的遍历

和树数据结构类似,我们可以访问图的所有节点。有两种算法可以对图进行遍历:广度优先 搜索(Breadth-First Search,BFS)和深度优先搜索(Depth-First Search,DFS)。图遍历可以用来寻找特定的顶点或寻找两个顶点之间的路径,检查图是否连通,检查图是否含有环等。

图遍历算法的思想是必须追踪每个第一次访问的节点,并且追踪有哪些节点还没有被完全探索。对于两种图遍历算法,都需要明确指出第一个被访问的顶点。

完全探索一个顶点要求我们查看该顶点的每一条边。对于每一条边所连接的没有被访问过的顶点,将其标注为被发现的,并将其加进待访问顶点列表中。

为了保证算法的效率,务必访问每个顶点至多两次。连通图中每条边和顶点都会被访问到。广度优先搜索算法和深度优先搜索算法基本上是相同的,只有一点不同,那就是待访问顶点 列表的数据结构。

2.3 广度优先搜索

广度优先搜索算法会从指定的第一个顶点开始遍历图,先访问其所有的相邻点,就像一次访问图的一层。换句话说,就是先宽后深地访问顶点。

广度优先搜索和深度优先搜索都需要标注被访问过的顶点。为此,我们将使用一个辅助数组color。由于当算法开始执行时,所有的顶点颜色都是白色(行{1}),所以我们可以创建一个辅 助函数initializeColor,为这两个算法执行此初始化操作。

我们会用到一个队列结构。队列的实现。

2.3.1广度优先搜索的基本实现

//广度优先搜索算法 v表示初始节点，callback表示回调。
Graph.prototype.bfs = function(v, callback){
    var color = initializeColor(this.vertices);
    var queue = new Queue();//存储待访问和待探索的节点
    queue.enqueue(v);
    while(!queue.isEmpty()){
        var u = queue.dequeue();
        //获取u的相邻节点列表
        var neighbors = this.adjList.get(u);
        color[u] = 'grey';
        for(var i = 0; i < neighbors.length; i++){
            var w = neighbors[i];
            //如果从没有标记过，则标记为grey，加入队列
            if (color[w] === 'white') {
                color[w] = 'grey';
                queue.enqueue(w);
            }
        }
        //所有相邻节点都被标记了，所以改为黑色
        color[u] = 'black';
        //如果对于标记过得节点有操作，通过callback操作
        if (callback) {
            callback(u);
        }
    }
};

2.3.2 广度优先实现最短路径查找

给定一个图G和源顶点v,找出对每个顶点u,u和v之间最短路径的距离。

	//用BFS实现最短路径
	Graph.prototype.BFS = function(v, callback) {
	    var color = initializeColor(this.vertices);
	    var queue = new Queue(); //存储待访问和待探索的节点
	    var d = [];
	    var pred = [];
	    queue.enqueue(v);
	    for (var i = 0; i < this.vertices.length; i++) {
	        d[this.vertices[i]] = 0;
	        pred[this.vertices[i]] = null;
	    }
	    while (!queue.isEmpty()) {
	        var u = queue.dequeue();
	        //获取u的相邻节点列表
	        var neighbors = this.adjList.get(u);
	        color[u] = 'grey';
	        for (var i = 0; i < neighbors.length; i++) {
	            var w = neighbors[i];
	            //如果从没有标记过，则标记为grey，加入队列
	            if (color[w] === 'white') {
	                color[w] = 'grey';
	                d[w] = d[u] + 1;
	                pred[w] = u;
	                queue.enqueue(w);
	            }
	        }
	        //所有相邻节点都被标记了，所以改为黑色
	        color[u] = 'black';
	        //如果对于标记过得节点有操作，通过callback操作
	        if (callback) {
	            callback(u);
	        }
	    }
	    return {
	        distances: d,
	        predecessors: pred
	    }
	};

2.3.3 深度优先搜索基本实现

	//深度优先基本实现
	Graph.prototype.dfs = function(callback) {
	    var self = this;
	    function dfsVisit(u, color, callback) {
	        color[u] = 'grey';
	        if (callback) {
	            callback(u);
	        }
	        var neighbors = self.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';
	    }
	    var color = initializeColor(this.vertices);
	    for (var i = 0; i < this.vertices.length; i++) {
	        if (color[this.vertices[i]] === 'white') {
	            dfsVisit(this.vertices[i], color, callback);
	        }
	    }
	};

2.3.4 深度优先搜索实现拓扑排序

当我们需要编排一些任务或步骤的执行顺序时,这称为拓扑排序。

	//DFS可以实现输出被访问顶点的顺序，可以用于拓扑排序实现。
	Graph.prototype.DFS = function(){
	    var time = 0;
	    var self = this;
	    function DFSVisit(u,color,d,f,p){
	        //console.log('discovered ' + u);
	        color[u] = 'grey';
	        d[u] = ++time;
	        var neighbors = self.adjList.get(u);
	        for(var i = 0; i < neighbors.length; i++){
	            var w = neighbors[i];
	            if (color[w] === 'white') {
	                p[w] = u;
	                DFSVisit(w,color,d,f,p);
	            }
	        }
	        color[u] = 'black';
	        f[u] = ++time;
	        //console.log('explored ' + u);
	    }
	    var color = initializeColor(this.vertices);
	    var d = [];
	    var f = [];
	    var p = [];
	    var time = 0;
	    for(var i = 0; i < this.vertices.length; i++){
	        f[this.vertices[i]] = 0;
	        d[this.vertices[i]] = 0;
	        p[this.vertices[i]] = null;
	    }
	    for(var i = 0; i< this.vertices.length; i++){
	        if (color[this.vertices[i]] === 'white') {
	            DFSVisit(this.vertices[i], color, d, f, p);
	        }
	    }
	    return {
	        discovery:d,
	        finished:f,
	        predecessors:p
	    }
	};

2.4 图的实现

我们会实现一个邻接表的图结构。我们使用一个数组来存储图中所有顶点的名字,以及一个字典 字典实现来存储邻接表字典将会使用顶点的名字作为键,邻接顶点列表作为值。vertices数组和adjList字典两者都是我们Graph类的私有属性。

	function Graph() {
	    this.vertices = []; //点数组
	    this.adjList = new Dictionary();
	    if ((typeof this.addVertex !== 'function') && (typeof this.addVertex !== 'string')) {
	        //私有方法，标记节点颜色 未被访问过是white 被发现是grey 已被探索black。
	        function initializeColor(vertices) {
	            var color = [];
	            for (var i = 0; i < vertices.length; i++) {
	                color[vertices[i]] = 'white';
	            }
	            return color;
	        }
	        //添加节点
	        Graph.prototype.addVertex = function(v) {
	            this.vertices.push(v);
	            this.adjList.set(v, []); //给节点v设置一个空数组作为值。
	        };
	        //添加边
	        Graph.prototype.addEdge = function(v, w) {
	            this.adjList.get(v).push(w); //先获取v节点对应的数组，然后把w推入数组中，这样就表示一条v到w的线
	            this.adjList.get(w).push(v);
	        };
	        //广度优先d
	        //搜索算法 v表示初始节点，callback表示回调。
	        Graph.prototype.bfs = function(v, callback) {
	            var color = initializeColor(this.vertices);
	            var queue = new Queue(); //存储待访问和待探索的节点
	            queue.enqueue(v);
	            while (!queue.isEmpty()) {
	                var u = queue.dequeue();
	                //获取u的相邻节点列表
	                var neighbors = this.adjList.get(u);
	                color[u] = 'grey';
	                for (var i = 0; i < neighbors.length; i++) {
	                    var w = neighbors[i];
	                    //如果从没有标记过，则标记为grey，加入队列
	                    if (color[w] === 'white') {
	                        color[w] = 'grey';
	                        queue.enqueue(w);
	                    }
	                }
	                //所有相邻节点都被标记了，所以改为黑色
	                color[u] = 'black';
	                //如果对于标记过得节点有操作，通过callback操作
	                if (callback) {
	                    callback(u);
	                }
	            }
	        };
	        //用BFS实现最短路径
	        Graph.prototype.BFS = function(v, callback) {
	            var color = initializeColor(this.vertices);
	            var queue = new Queue(); //存储待访问和待探索的节点
	            var d = [];
	            var pred = [];
	            queue.enqueue(v);
	            for (var i = 0; i < this.vertices.length; i++) {
	                d[this.vertices[i]] = 0;
	                pred[this.vertices[i]] = null;
	            }
	            while (!queue.isEmpty()) {
	                var u = queue.dequeue();
	                //获取u的相邻节点列表
	                var neighbors = this.adjList.get(u);
	                color[u] = 'grey';
	                for (var i = 0; i < neighbors.length; i++) {
	                    var w = neighbors[i];
	                    //如果从没有标记过，则标记为grey，加入队列
	                    if (color[w] === 'white') {
	                        color[w] = 'grey';
	                        d[w] = d[u] + 1;
	                        pred[w] = u;
	                        queue.enqueue(w);
	                    }
	                }
	                //所有相邻节点都被标记了，所以改为黑色
	                color[u] = 'black';
	                //如果对于标记过得节点有操作，通过callback操作
	                if (callback) {
	                    callback(u);
	                }
	            }
	            return {
	                distances: d,
	                predecessors: pred
	            }
	        };
	        //深度优先基本实现
	        Graph.prototype.dfs = function(callback) {
	            var self = this;
	            function dfsVisit(u, color, callback) {
	                color[u] = 'grey';
	                if (callback) {
	                    callback(u);
	                }
	                var neighbors = self.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';
	            }
	            var color = initializeColor(this.vertices);
	            for (var i = 0; i < this.vertices.length; i++) {
	                if (color[this.vertices[i]] === 'white') {
	                    dfsVisit(this.vertices[i], color, callback);
	                }
	            }
	        };
	        //DFS可以实现输出被访问顶点的顺序
	        Graph.prototype.DFS = function(){
	            var time = 0;
	            var self = this;
	            function DFSVisit(u,color,d,f,p){
	                //console.log('discovered ' + u);
	                color[u] = 'grey';
	                d[u] = ++time;
	                var neighbors = self.adjList.get(u);
	                for(var i = 0; i < neighbors.length; i++){
	                    var w = neighbors[i];
	                    if (color[w] === 'white') {
	                        p[w] = u;
	                        DFSVisit(w,color,d,f,p);
	                    }
	                }
	                color[u] = 'black';
	                f[u] = ++time;
	                //console.log('explored ' + u);
	            }
	            var color = initializeColor(this.vertices);
	            var d = [];
	            var f = [];
	            var p = [];
	            var time = 0;
	            for(var i = 0; i < this.vertices.length; i++){
	                f[this.vertices[i]] = 0;
	                d[this.vertices[i]] = 0;
	                p[this.vertices[i]] = null;
	            }
	            for(var i = 0; i< this.vertices.length; i++){
	                if (color[this.vertices[i]] === 'white') {
	                    DFSVisit(this.vertices[i], color, d, f, p);
	                }
	            }
	            return {
	                discovery:d,
	                finished:f,
	                predecessors:p
	            }
	        };
	        Graph.prototype.toString = function() {
	            var s = '';
	            for (var i = 0; i < this.vertices.length; i++) {
	                s += this.vertices[i] + ' -> ';
	                var neighbors = this.adjList.get(this.vertices[i]);
	                for (var j = 0; j < neighbors.length; j++) {
	                    s += neighbors[j] + ' ';
	                }
	                s += ',';
	            }
	            return s;
	        };
	    }
	}

2.5 图的基本使用

	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', '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());//A -> B C D ,B -> A E F ,C -> A D G ,D -> A C G H ,E -> B I ,F -> B ,G -> C D ,H -> D ,I -> E 
	function printNode(value) {
	    console.log('Visited vertex: ' + value);
	}

	//广度搜索算法
	//graph.bfs(myVertices[0],printNode);
	//上行输出结果，节点的访问顺序
	// 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

	//广度优先搜索的使用:最短路径算法
	var shortestPathA = graph.BFS(myVertices[0]);
	//console.log(shortestPathA);
	//上行输出结果：
	// { distances: [ A: 0, B: 1, C: 1, D: 1, E: 2, F: 2, G: 2, H: 2, I: 3 ],
	//   predecessors: 
	//    [ A: null,
	//      B: 'A',
	//      C: 'A',
	//      D: 'A',
	//      E: 'B',
	//      F: 'B',
	//      G: 'C',
	//      H: 'D',
	//      I: 'E' ]

	//深入优先搜索算法
	//graph.dfs(printNode);
	//上一行运行结果，节点的访问顺序
	// Visited vertex: A
	// Visited vertex: B
	// Visited vertex: E
	// Visited vertex: I
	// Visited vertex: F
	// Visited vertex: C
	// Visited vertex: D
	// Visited vertex: G
	// Visited vertex: H

	//深度优先搜索查找访问过程：
	graph = new Graph();
	myVertices = ['A','B','C','D','E','F'];
	for (i=0; i<myVertices.length; i++){
	    graph.addVertex(myVertices[i]);
	}
	graph.addEdge('A', 'C');
	graph.addEdge('A', 'D');
	graph.addEdge('B', 'D');
	graph.addEdge('B', 'E');
	graph.addEdge('C', 'F');
	graph.addEdge('F', 'E');
	var result = graph.DFS();
	// 上面运行输出：
	// discovered A
	// discovered C
	// discovered F
	// discovered E
	// discovered B
	// discovered D
	// explored D
	// explored B
	// explored E
	// explored F
	// explored C
	// explored A