JS实现图结构使用邻接表实现(广度优先搜索,深度优先搜索)

2020-10-5 17:28:30
学习记录
454

JS实现图结构使用邻接表实现(广度优先搜索,深度优先搜索)

1.获取到的知识

  • 层序遍历
    • 实现原理:先对每层做标记,如果标记一次进行遍历,遇到已经遍历过的,跳过
  • 巧妙之处:对于图结构的表示中有一种邻接表,类似于哈希表中的链地址法,可以方便的把顶点和每个每条边对应起来,每个边也对应的是一个顶点,这样就可以把图机构抽象成程序储存起来,下图的邻接表可以用链表或者数组都可以实现

邻接表结构图

2. 广度优先搜索和深度优先搜索

2.1 广度优先搜索的巧妙之处 (BFS)

1.广度优先搜索原理主要是利用队列来实现,先把所有的内容都给搜索到,然后再依次的去处理每一个搜索到的内容

2.利用一个对象或者Map来储存是否是已经遍历或者探测过的对象,来避免重复查询

bfs() { //0 首先需要一个标识符来确定每个顶点是否已经进入过队列 let queue = []; let vertexesMap = this.isExpload(); //1. 拿到第一个顶点,加入队列中 vertexesMap.set(this.vertexes[0], true); queue.push(this.vertexes[0]); //2. 根据队列不为空循环处理队列的内容 while (queue.length != 0) { //3. 执行队列中的第一个顶点 //4. 拿到顶点之后,弹出顶点 let vertexe = queue.shift(); //5. 对这个顶点执行相应的操作,实际可是传递一个回调函数来进行处理 console.log(vertexe); //6. 循环探测该顶点的边连接的其他的所有顶点。 let otherVertexes = this.edges.get(vertexe); for (let i = 0; i < otherVertexes.length; i++) { //7. 对探测的顶点进行判断 //7.1 如果顶点没有加入,则把该顶点加入队列 if (!vertexesMap.get(otherVertexes[i])) { vertexesMap.set(otherVertexes[i],true); queue.push(otherVertexes[i]); } //7.2 如果顶点已经被加入过队列,则不再加入. } } }

2.2 深度优先搜索

​ 深度优先搜索算法和哈希表的先序、中序、后序、遍历思想差不多一致,只不过多了一个用于储存顶点是否发生改变的状态。

通过储存每个顶点是否已经被探测过,来觉得是否对该顶点进行遍历处理

//深度优先搜索 DeepFirstSearch dfs(){ //深度搜索原理是通过递归,先把一个分支上的所有内容都遍历完成,然后再去遍历其他的分支 //1.获取所有状态 let vertexesMap = this.isExpload(); this.dfsNode(this.vertexes[0],vertexesMap); } //遍历处理每个顶点 dfsNode(vertexe,vertexesMap){ //1. 需要标识符来判断是否已经处理过。 //1.1 处理传入的顶点,并把顶点切换为已经处理 console.log(vertexe); vertexesMap.set(vertexe,true); //2.获取传入顶点的边所对应的顶点; let vertexes = this.edges.get(vertexe); //3.根据循环遍历获得的顶点 for(let i=0;i<vertexes.length;i++){ //4.判断顶点是否已经处理过 //4.1 如果没有处理过,继续调用该函数,进行处理遍历 if( !vertexesMap.get(vertexes[i]) ){ this.dfsNode(vertexes[i],vertexesMap); } //4.2 如果处理过则不用管了, } }

3.完整图结构封装代码

/* 图结构封装 */ class Graph { constructor() { //需要的属性,图结构表示方法使用:邻接表 //1.顶点 this.vertexes = []; //2.边 this.edges = new Map(); } //插入一个顶点 insertVertexes(v) { this.vertexes.push(v); this.edges.set(v, []); } //插入一条边 insertEdge(v1, v2) { this.edges.get(v1).push(v2); this.edges.get(v2).push(v1); } //返回一个Map,包含一个 key(元素) 和 一个val (是否已经被探测过) isExpload() { let vertexesMap = new Map(); let vertexes = this.vertexes; for (let i = 0; i < vertexes.length; i++) { vertexesMap.set(vertexes[i], false); let edges = this.edges.get(vertexes[i]); for (let j = 0; j < edges.length; j++) { vertexesMap.set(edges[j], false); } } return vertexesMap; } //广度优先搜索 BFS BroundFirstSearch bfs() { //广度优先搜索原理主要是利用队列来实现,先把所有的内容都给搜索到,然后再依次的去处理每一个搜索到的内容 //0 首先需要一个标识符来确定每个顶点是否已经进入过队列 let queue = []; let vertexesMap = this.isExpload(); //1. 拿到第一个顶点,加入队列中 vertexesMap.set(this.vertexes[0], true); queue.push(this.vertexes[0]); //2. 根据队列不为空循环处理队列的内容 while (queue.length != 0) { //3. 执行队列中的第一个顶点 //4. 拿到顶点之后,弹出顶点 let vertexe = queue.shift(); //5. 对这个顶点执行相应的操作,实际可是传递一个回调函数来进行处理 console.log(vertexe); //6. 循环探测该顶点的边连接的其他的所有顶点。 let otherVertexes = this.edges.get(vertexe); for (let i = 0; i < otherVertexes.length; i++) { //7. 对探测的顶点进行判断 //7.1 如果顶点没有加入,则把该顶点加入队列 if (!vertexesMap.get(otherVertexes[i])) { vertexesMap.set(otherVertexes[i],true); queue.push(otherVertexes[i]); } //7.2 如果顶点已经被加入过队列,则不再加入. } } } //深度优先搜索 DeepFirstSearch dfs(){ //深度搜索原理是通过递归,先把一个分支上的所有内容都遍历完成,然后再去遍历其他的分支 //1.获取所有状态 let vertexesMap = this.isExpload(); this.dfsNode(this.vertexes[0],vertexesMap); } //遍历处理每个顶点 dfsNode(vertexe,vertexesMap){ //1. 需要标识符来判断是否已经处理过。 //1.1 处理传入的顶点,并把顶点切换为已经处理 console.log(vertexe); vertexesMap.set(vertexe,true); //2.获取传入顶点的边所对应的顶点; let vertexes = this.edges.get(vertexe); //3.根据循环遍历获得的顶点 for(let i=0;i<vertexes.length;i++){ //4.判断顶点是否已经处理过 //4.1 如果没有处理过,继续调用该函数,进行处理遍历 if( !vertexesMap.get(vertexes[i]) ){ this.dfsNode(vertexes[i],vertexesMap); } //4.2 如果处理过则不用管了, } } } let graph = new Graph(); graph.insertVertexes('a'); graph.insertVertexes('b'); graph.insertVertexes('c'); graph.insertVertexes('d'); graph.insertEdge("a",'b'); graph.insertEdge("a",'c'); graph.insertEdge("a",'d'); graph.insertEdge("b",'c'); graph.insertEdge("b",'d'); // graph.bfs(); graph.dfs();
avatar

Sky(小新)

个人签名: 提升能力,创造价值!

江苏-南京
skylpz@qq.com