JS实现图的深度优先遍历（DFS）和广度优先遍历（BFS）

分手后的思念是犯贱 2022-04-03 12:37 366阅读 0赞

## 1 建立测试图（邻接矩阵和邻接表存储形式） ##

首先建立一个图用于后续代码的测试，在此以无向图为例，且所有边的权值都为1。存储方式分别为邻接矩阵和邻接表（[见上一篇介绍][Link 1]）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70]  
**邻接矩阵：**

class Graph{ 
    	constructor(v,vr){ 
    		let len = v.length
    		this.vexs = [].slice.apply(v);
    		let arcs = [];
    		for (let i=0;i<len;i++){ 
    			arcs[i] = new Array(len);
    			for (let j=0;j<len;j++){ 
    				arcs[i][j] = i===j ? 0 : 65535;
    			}
    		}
    		for (let arc of vr){ 
    			let v1 = v.indexOf(arc[0]);
    			let v2 = v.indexOf(arc[1]);
    			arcs[v1][v2] = arcs[v2][v1] = arc[2] || 1;
    		}
    		this.arcs = arcs;
    	}
    
    }
    
    let a = new Graph(['A','B','C','D','E','F','G','H','I'],[['A','B',1],['A','F',1],['B','G',1],['F','G',1],['B','C',1],['B','I',1],['G','H',1],['C','I',1],['I','D',1],['H','D',1],['F','E',1],['H','E',1],['C','D',1]]);
    console.log(a);

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 1]  
**邻接表：**

class vex{ 
    	constructor(value){ 
    		this.data = value;
    		this.firstEdge = null;
    	}
    
    }
    
    class adjvex{ 
    	constructor(node,weight){ 
    		this.node = node;
    		this.weight = weight;
    		this.next = null;
    	}
    }
    
    class Graph{ 
    	constructor(v,vr){ 
    		let len = v.length;
    		let vexs = new Array(len);
    		let v1=0,v2=0;
    		let newvex = null;
    		for (let i=0;i<len;i++){ 
    			vexs[i] = new vex(v[i]);
    		}
    		for (let arc of vr){ 
    			v1 = v.indexOf(arc[0]);
    			v2 = v.indexOf(arc[1]);
    
    			newvex = new adjvex(v1,arc[2]);
    			newvex.next = vexs[v2].firstEdge;
    			vexs[v2].firstEdge = newvex;
    
    			newvex = new adjvex(v2,arc[2]);
    			newvex.next = vexs[v1].firstEdge;
    			vexs[v1].firstEdge = newvex;
    		}
    		this.adjList = vexs;
    	}
    }
    
    let a = new Graph(['A','B','C','D','E','F','G','H','I'],[['A','B',1],['A','F',1],['B','G',1],['F','G',1],['B','C',1],['B','I',1],['G','H',1],['C','I',1],['I','D',1],['H','D',1],['F','E',1],['H','E',1],['C','D',1]]);
    console.log(a);

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

## 2 深度优先遍历 ##

**深度优先遍历**是一个递归过程，其从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发，深度优先遍历图，直至图中所有点都被访问到，类似于树的前序遍历。

**邻接矩阵：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 3]  
**邻接表：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 4]

## 3 广度优先遍历 ##

**广度优先遍历**类似于树的层序遍历，其从图中某顶点v出发，访问了v之后一次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，且先被访问的顶点的邻接点先于后被访问的顶点的邻接点，直至图中所有顶点都被访问。  
**邻接矩阵：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 5]  
**邻接表：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 6]

--------------------

如果觉得这篇文章帮助了您，请打赏一个小红包鼓励作者继续创作哦！！！

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70_pic_center]

[Link 1]: https://blog.csdn.net/zjw_python/article/details/85158998
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70]: /images/20220403/6799997476bc4238b93415d7fca1cbcb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 1]: /images/20220403/9a820a1b8cc3497c9de6657160fe3966.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 2]: /images/20220403/7c52c114360f47d798743b373eef80de.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 3]: /images/20220403/31980c95eb94490caa315b42944af93f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 4]: /images/20220403/c730449000b2459ea44d8e2ad27242f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 5]: /images/20220403/2a9b336514234fb8b39a0f8704c4b577.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 6]: /images/20220403/daab798ae0284ff3a480627c5610325d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70_pic_center]: /images/20220403/b7d5915dd13b4640909711e94adb63fe.png