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

蔚落 2022-02-14 12:15 708阅读 0赞

### 文章目录 ###

*  1.图的相关术语
 *  2.图的表示
 *   *  2.1.邻接矩阵
     *  2.2.邻接表
     *  2.3.关联矩阵
 *  3.创建图类
 *   *  3.1.创建字典类
     *  3.2.创建图类
     *  3.3.创建实例
     *  输出的结果为：
 *  4.图的遍历
 *   *  4.1.广度优先遍历
     *  思路：
     *  添加bfs方法
     *  创建bfs实例
     *  bfs输出结果
     *  使用BFS寻找最短路径
     *  创建BFS实例
     *  BFS输出结果
     *  4.2.深度优先遍历
     *  思路：
     *  添加dfs方法
     *  创建dfs实例
     *  dfs输出结果

# 1.图的相关术语 #

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

# 2.图的表示 #

## 2.1.邻接矩阵 ##

![在这里插入图片描述][5.jpg]  
array\[i\]\[j\] ===1代表i节点和j节点相邻，否则不相邻

## 2.2.邻接表 ##

![在这里插入图片描述][4.jpg]  
相当于把每个节点的相邻节点一一列举出来。

## 2.3.关联矩阵 ##

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

# 3.创建图类 #

![在这里插入图片描述][3.jpg]  
接下来就采用邻接表的方式创建上面的图并且采用字典来表示：

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

![在这里插入图片描述][6.jpg]  
采用队列的方式，先添加节点的先被探索；  
采用三种颜色来反应节点的状态：  
**白色**：还没被访问；  
**灰色**：被访问但未被探索；  
**黑色**：被访问且探索过；

## 思路： ##

首先搜索节点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.深度优先遍历 ##

![在这里插入图片描述][1.jpg]  
采用栈的方式，先添加节点的先被探索；  
由递归实现。

![在这里插入图片描述][2.jpg]

## 思路： ##

从节点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

*原文链接：\[重拾数据结构-图的基础\]*([https://www.cqz21.top/DetailTemp/5cc06374104d4d67d2482999/NMR][https_www.cqz21.top_DetailTemp_5cc06374104d4d67d2482999_NMR])

*微信扫一扫，关注“厦猿”，获取更多前端学习资料*  
![厦猿公众号][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNjQzMQ_size_16_color_FFFFFF_t_70]

[5.jpg]: /images/20220214/16a0c79ad7bd426b9e18db2582431633.png
[4.jpg]: /images/20220214/82d1466128814921953d5e98fa59649d.png
[3.jpg]: /images/20220214/ed5d5a31930e495488508446b8451c9f.png
[6.jpg]: /images/20220214/0d3cee63eca54ae9a1bbd6be0f53bb38.png
[1.jpg]: /images/20220214/bb7f3f9afad8468bb99c86a0b815bb6f.png
[2.jpg]: /images/20220214/b09dfdbe52c648a5abba065490b11aa9.png
[https_www.cqz21.top_DetailTemp_5cc06374104d4d67d2482999_NMR]: https://www.cqz21.top/DetailTemp/5cc06374104d4d67d2482999/NMR
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNjQzMQ_size_16_color_FFFFFF_t_70]: /images/20220214/eda9d2fd7e0d448cbf1d0831b94acb10.png