JS实现图的深度优先遍历(DFS)和广度优先遍历(BFS)

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

1 建立测试图(邻接矩阵和邻接表存储形式)

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

  1. class Graph{
  2. constructor(v,vr){
  3. let len = v.length
  4. this.vexs = [].slice.apply(v);
  5. let arcs = [];
  6. for (let i=0;i<len;i++){
  7. arcs[i] = new Array(len);
  8. for (let j=0;j<len;j++){
  9. arcs[i][j] = i===j ? 0 : 65535;
  10. }
  11. }
  12. for (let arc of vr){
  13. let v1 = v.indexOf(arc[0]);
  14. let v2 = v.indexOf(arc[1]);
  15. arcs[v1][v2] = arcs[v2][v1] = arc[2] || 1;
  16. }
  17. this.arcs = arcs;
  18. }
  19. }
  20. 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]]);
  21. console.log(a);

在这里插入图片描述
邻接表:

  1. class vex{
  2. constructor(value){
  3. this.data = value;
  4. this.firstEdge = null;
  5. }
  6. }
  7. class adjvex{
  8. constructor(node,weight){
  9. this.node = node;
  10. this.weight = weight;
  11. this.next = null;
  12. }
  13. }
  14. class Graph{
  15. constructor(v,vr){
  16. let len = v.length;
  17. let vexs = new Array(len);
  18. let v1=0,v2=0;
  19. let newvex = null;
  20. for (let i=0;i<len;i++){
  21. vexs[i] = new vex(v[i]);
  22. }
  23. for (let arc of vr){
  24. v1 = v.indexOf(arc[0]);
  25. v2 = v.indexOf(arc[1]);
  26. newvex = new adjvex(v1,arc[2]);
  27. newvex.next = vexs[v2].firstEdge;
  28. vexs[v2].firstEdge = newvex;
  29. newvex = new adjvex(v2,arc[2]);
  30. newvex.next = vexs[v1].firstEdge;
  31. vexs[v1].firstEdge = newvex;
  32. }
  33. this.adjList = vexs;
  34. }
  35. }
  36. 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]]);
  37. console.log(a);

在这里插入图片描述

2 深度优先遍历

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

邻接矩阵:

  1. function DFSTraverse(G){
  2. let visited = new Array(G.vexs.length); //用于标记顶点是否被访问过
  3. for (let i=0;i<G.vexs.length;i++){ //初始化
  4. visited[i] = false;
  5. }
  6. for (let i=0;i<G.vexs.length;i++){ //从第一个点开始递归访问
  7. if (visited[i] === false){
  8. visited[i] = true;
  9. DFS(i);
  10. }
  11. }
  12. function DFS(i){
  13. console.log(G.vexs[i]);
  14. for (let j=0;j<G.vexs.length;j++){
  15. if (G.arcs[i][j] === 1 && visited[j] === false){ //访问未访问过的邻接点
  16. visited[j] = true;
  17. DFS(j);
  18. }
  19. }
  20. }
  21. }

在这里插入图片描述
邻接表:

  1. function DFSTraverse(G){
  2. let visited = new Array(G.adjList.length); //用于标记顶点是否被访问过
  3. for (let i=0;i<G.adjList.length;i++){ //初始化
  4. visited[i] = false;
  5. }
  6. for (let i=0;i<G.adjList.length;i++){ //从第一个点开始递归访问
  7. if (visited[i] === false){
  8. visited[i] = true;
  9. DFS(i);
  10. }
  11. }
  12. function DFS(i){
  13. console.log(G.adjList[i].data);
  14. let adjvex = G.adjList[i].firstEdge;
  15. while(adjvex){
  16. if (visited[adjvex.node] === false){ //访问未访问过的邻接点
  17. visited[adjvex.node] = true;
  18. DFS(adjvex.node);
  19. }
  20. adjvex = adjvex.next;
  21. }
  22. }
  23. }

在这里插入图片描述

3 广度优先遍历

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

  1. function BFSTraverse(G){
  2. let queue = []; //使用队列进行层序遍历
  3. let visited = new Array(G.vexs.length);
  4. let vexnum = 0;
  5. for (let i=0;i<G.vexs.length;i++){
  6. visited[i] = false;
  7. }
  8. for (let i=0;i<G.vexs.length;i++){
  9. if (visited[i] === false){
  10. visited[i] = true;
  11. queue.push(i);
  12. while(queue.length > 0){
  13. vexnum = queue.shift(); //弹出队列头部序号,并访问节点
  14. console.log(G.vexs[vexnum]);
  15. for (let j=0;j<G.vexs.length;j++){ //将当前节点未访问过的的邻接点序号推入队列
  16. if (G.arcs[vexnum][j] === 1 && visited[j] === false){
  17. visited[j] = true;
  18. queue.push(j);
  19. }
  20. }
  21. }
  22. }
  23. }
  24. }

在这里插入图片描述
邻接表:

  1. function BFSTraverse(G){
  2. let queue = [];
  3. let visited = new Array(G.adjList.length);
  4. let vexnum = 0;
  5. let adjvex = null;
  6. for (let i=0;i<G.adjList.length;i++){
  7. visited[i] = false;
  8. }
  9. for (let i=0;i<G.adjList.length;i++){
  10. if (visited[i] === false){
  11. visited[i] = true;
  12. queue.push(i);
  13. }
  14. while(queue.length > 0){
  15. vexnum = queue.shift(); //弹出队列头部序号,并访问节点
  16. console.log(G.adjList[vexnum].data);
  17. adjvex = G.adjList[vexnum].firstEdge;
  18. while(adjvex){ //将当前节点未访问过的的邻接点序号推入队列
  19. if (visited[adjvex.node] === false){
  20. visited[adjvex.node] = true;
  21. queue.push(adjvex.node);
  22. }
  23. adjvex = adjvex.next;
  24. }
  25. }
  26. }
  27. }

在这里插入图片描述


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

在这里插入图片描述

发表评论

表情:
评论列表 (有 0 条评论,574人围观)

还没有评论,来说两句吧...

相关阅读