图的主要存储结构都有两种：邻接矩阵和邻接表。根据是否有方向，分为有向图还是无向图；
图的算法难度较大，对于图的不同存储结构，将对程序的效率产生相当大的影响，所以存储结构应适合于求解问题
本系列实现图的算法邻接表，它属于图的链式存储结构

邻接表

邻接表对图中每个顶点都建立一个单链表，第 图graph - 图1 个单链表中的节点表示依附于顶点 图graph - 图2 的边，对于有向图则是以顶点 图graph - 图3 为尾的弧，这个单链表就成为顶点 图graph - 图4 的边表。所以在邻接表中存在两种节点：顶点表节点和边表节点

顶点表节点结构

  1. // 顶点 表节点
  2. class Vertex {
  3.   /**
  4.    * @description:
  5.    * @param {*} data记录顶点节点的数值
  6.    * @return {*}
  7.    */
  8.   constructor(data) {
  9.     this.data = data; // 顶点域
  10.     this.firstEdge = null; // 指向第一个邻接边的指针，指向当前顶点的边表中的第一个节点
  11.     this.outNum = 0; // 在无向图中表示与顶点邻接的边的数量，在有向图中为出度
  12.     this.inNum = 0; // 在有向图中为顶点的入度
  13.   }
  14. }

data记录顶点节点的数值，firstEdge则指向当前顶点的边表中的第一个节点。outNum在无向图中表示的是与顶点邻接的边的数量，在有向图中则是出度。inNum在无向图中没有意义，在有向图中表示顶点的入度。

边表节点结构

  1. // 边表节点
  2. class Edge {
  3.     constructor(data, weight = 0, nextEdge = null) {
  4.         this.data = data; // 邻接点域
  5.         this.nextEdge = nextEdge; // 指向下一条邻接边
  6.         this.weight = weight;  // 权重
  7.     }
  8. }

data为数据域，nextEdge则是指向与顶点 [公式] 相邻的下一个节点。weight表示顶点 [公式] 到当前节点的权重。

无向图展示

图graph - 图5
该图的邻接表表示如下
图graph - 图6

图的重要的操作

  1. insertVertex(x)  // 向图中插入新的顶点
  2. allNeightbors(x)  // 与顶点x邻接的所有节点
  3. addEdge(x, y, w = 0)  // 向图中插入边(x, y)
  4. removeEdge(x, y)  // 在图中删除边(x, y)
  5. deleteVertex(x)  // // 从图中删除顶点x
  6. hasEdge(x, y)  // 判断是否存在边(x,y)或者<x, y>
  7. getAllEdge()  // 获取图中所有的边
  8. getEdgeWeight(x, y)  // 获取边(x, y)或<x, y>对应的权值
  9. getMaxEdgeWeight()  // 获得图中最大的权值
  10. getMinEdgeWeight() // 获得图中最小的权值
  11. setEdgeWeight(x, y, w)  // 设置边(x, y)或<x, y>的权值
  12. BFSTraverse(x)  // 广度优先遍历
  13. DFSTraverse(x)  // 深度优先遍历
  14. isConnected() // 判断当前的图是否是连通图
  15. getMSTree(method)  // 最小生成树
  16. getShortestPath(x)  // 求带权图顶点x到其他顶点的最短路径
  17. getTopoSort()  // 拓扑排序
  18. getCriticalPath()  // 关键路径

代码结构

isDirect为0表示这是一张无向图，为1则表示这是一张有向图。

  1. class Graph {
  2.     constructor(isDirect) {
  3.         this.eNum = 0;  // 边的数目
  4.         this.adj = [];  // 顶点表
  5.         this.isDirect = isDirect; // 是否是有向图
  6.     }
  7.     // 初始化顶点表
  8.     initVertex(verArr) {}
  10.     // 插入新的顶点
  11.     insertVertex(x) {}
  13.     // 找到节点x在adj中所在的位置
  14.     // 前面加上下划线表示不应该在具体实例中调用该方法
  15.     _find(x) {}
  17.     // 判断图中是否存在边(x,y)或者<x, y>。
  18.     hasEdge(x, y)  {}
  20.     // 向图中插入边(x, y)或者边<x, y>
  21.     addEdge(x, y, w = 0) {}
  23.     // 在图中删除边(x, y)或者边<x, y>
  24.     removeEdge(x, y) {}
  26.     // 从图中删除顶点x
  27.     deleteVertex(x) {} 
  29.     // 与顶点x邻接的所有节点
  30.     allNeightbors(x) {}
  31. }

构建过程

初始化顶点表

初始化顶点表的时候可以传入一个数组类型的参数， 将使用传入的值来构建顶点类Vertex，然后将顶点不断的压入当前的顶点数组中。

  1. initVertex(verArr) {
  2.   for (let i = 0; i < verArr.length; i++) {
  3.     let newVer = new Vertex(verArr[i]);
  4.     this.adj[i] = newVer;
  5.   }
  6. }

插入新的顶点

向图中插入新的顶点只要添加到当前的顶点表中

  1. // 插入新的顶点
  2. insertVertex(x) {
  3.   // 创建新顶点
  4.   let newVer = new Vertex(x);
  5.   // 添加到当前的顶点表
  6.   this.adj.push(newVer);
  7. }

在顶点表中查找给定数值的方法

  1. // 找到节点x在adj中所在的位置
  2. // 前面加上下划线表示不应该在具体实例中调用该方法
  3. _find(x) {
  4.   let pos = -1;
  6.   for (let i = 0; i < this.adj.length; i++) {
  7.     if (x == this.adj[i].data) pos = i;
  8.   }
  10.   return pos;
  11. }

两点之间是否有边

在为顶点之间插入边之前，还需要知道顶点之间是否已经有了边，下面的代码判断x和y之间是否具有边，从顶点x的边表第一元素开始遍历，如果发现存在y节点则说明顶点x和顶点y之间已经有一条边

  1. // 判断图中是否存在边(x,y)或者<x, y>。
  2. // 从顶点x的边表第一元素开始遍历，如果发现存在y节点则说明顶点x和顶点y之间已经有了一条边
  3. hasEdge(x, y) {
  4.   let pos = this._find(x);
  6.   if (pos > -1) {
  7.     let curVer = this.adj[pos].firstEdge;
  9.     if (!curVer) {  // 没有与顶点x的邻接点
  10.       return false;
  11.     } else {  // 至少有一个节点与顶点x是相邻的
  12.       // 遍历顶点的所有邻接节点
  13.       while (curVer) {
  14.         if (curVer.data === y) return true;
  16.         curVer = curVer.nextEdge;
  17.       }
  19.       return false;
  20.     }
  21.   }
  22. }

两点之间创建边

所有的准备工作做完，然后就可以连接任意顶点。此时分为有向图还是无向图

  • 无向图：在插入边(x, y)后还要再插入边(y, x)，因为用邻接表来存储无向图时，顶点x的边表中具有顶点y，那么顶点y的边表中必然也有顶点x。
  • 有向图：只需要插入边就可以

在插入边的时候，首先判断下顶点x和顶点y之间是否已经存在一条边，只有x和y之间没有边时，才可以在顶点x和顶点y之间插入一条边。
需要注意的是，在插入边的过程中，如果是有向图时，也同时更新了每个顶点的入度和出度，而如果是无向图的话，则分别更新了与x和y相邻的节点的数量。
之所以需要顶点的入度和出度，是为了后面求图的拓扑排序和关键路径准备的。

  1. // 向图中插入边(x, y)或者边<x, y>
  2. /**
  3.    1.连接任意顶点，分为有向图还是无向图，
  4.     如果是无向图的话，在插入边(x, y)后还要再插入边(y, x)，因为用邻接表来存储无向图时，顶点x的边表中具有顶点y，那么顶点y的边表中必然也有顶点x。
  5.     如果是有向图中的话，只需要插入边<x, y>就可以
  6.    2.在插入边的时候，首先判断下顶点x和顶点y之间是否已经存在了一条边了，只有x和y之间没有边时，才可以在顶点x和顶点y之间插入一条边
  7.    3.在插入边的过程中，如果是有向图时，同时更新每个顶点的入度和出度，而如果是无向图的话，则分别更新了与x和y相邻的节点的数量。
  8.  */
  9.   addEdge(x, y, w = 0) {
  10.     let posX = this._find(x);
  11.     let posY = this._find(y);
  12.     let newEdgeX = new Edge(x, w);
  13.     let newEdgeY = new Edge(y, w);
  14.     // 如果是无向图，在插入边(x, y)时还要插入边(y, x)
  15.     if (!this.isDirect) {
  16.       // <x, y>或者<y, x>边不存在
  17.       if (!this.hasEdge(x, y) && !this.hasEdge(y, x)) {
  18.         // 如果顶点x在顶点表中
  19.         if (posX > -1) {
  20.           // 取出顶点x的第一条边
  21.           let curVer = this.adj[posX].firstEdge;
  22.           // 如果第一条边不存在
  23.           if (!curVer) {
  24.             // 创建第一条边
  25.             this.adj[posX].firstEdge = newEdgeY;
  26.             // outNum无向图中，表示顶点邻接边的数量
  27.             this.adj[posX].outNum++;
  28.           } else {
  29.             let len = this.adj[posX].outNum - 1;
  30.             // x点的邻接边存在，往所有边之后追加边
  31.             while (len--) {
  32.               curVer = curVer.nextEdge;
  33.             }
  34.             curVer.nextEdge = newEdgeY;
  35.             // 邻接边数量+1
  36.             this.adj[posX].outNum++;
  37.           }
  38.         }
  39.         // 如果顶点y在顶点表中
  40.         if (posY > -1) {
  41.           // 取出顶点y的第一条边
  42.           let curVer = this.adj[posY].firstEdge;
  43.           if (!curVer) {
  44.             this.adj[posY].firstEdge = newEdgeX;
  45.             this.adj[posY].outNum++;
  46.           } else {
  47.             let len = this.adj[posY].outNum - 1;
  48.             while (len--) {
  49.               curVer = curVer.nextEdge;
  50.             }
  51.             curVer.nextEdge = newEdgeX;
  52.             this.adj[posY].outNum++;
  53.           }
  54.         }
  55.         // 边的数量+1
  56.         this.eNum++;
  57.       }
  58.     }
  59.     // 有向图， 只用处理<x, y>方向的边
  60.     else {
  61.       if (!this.hasEdge(x, y)) {
  62.         // 如果顶点x在顶点表中
  63.         if (posX > -1) {
  64.           // x顶点的第一条边
  65.           let curVer = this.adj[posX].firstEdge;
  66.           // 如果当前顶点没有第一个边节点
  67.           if (!curVer) {
  68.             this.adj[posX].firstEdge = newEdgeY;
  69.             // x顶点的出度+1
  70.             this.adj[posX].outNum++;
  71.           } else {
  72.             let len = this.adj[posX].outNum - 1;
  73.             while (len--) {
  74.               curVer = curVer.nextEdge;
  75.             }
  76.             curVer.nextEdge = newEdgeY;
  77.             // 顶点x的出度+1
  78.             this.adj[posX].outNum++;
  79.           }
  80.         }
  81.         // 如果顶点x在顶点表中
  82.         if (posY > -1) {
  83.           let curVer = this.adj[posY];
  84.           // 顶点y的入度增长
  85.           curVer.inNum++;
  86.         }
  87.       }
  88.     }
  89.   }

删除边的操作

在无向图中删除边(x, y)时，同时也需要删除(y, x)，有向图则只需要删除边就可以
需要注意的是，在删除边时，涉及到更新顶点的边表，而顶点类中的firstEdge指针，指向与该顶点边表中的第一个节点，如果需要删除这个节点，还需要更新firstEdge指向。这里的操作和单链表中删除有点类似

  1. // 在图中删除边(x, y)或者边<x, y>
  2.   // 在无向图中删除边(x, y)时，同时也需要删除(y, x)，有向图则只需要删除边<x, y>就可以
  3.   // 由于是由邻接表表示的数据结构，当删除边(x, y)时也需要同时删除边(y, x);
  4.   removeEdge(x, y) {
  5.     //在图中删除边(x, y)
  6.     if (this.hasEdge(x, y)) {
  7.       let posX = this._find(x); //查找x顶点
  8.       let posY = this._find(y); //查找y顶点
  9.       let curVerX = this.adj[posX].firstEdge; // x的第一条边
  10.       let curVerY = this.adj[posY].firstEdge; //y的第一条边
  11.       // 首先是无向图，当删除边(x, y)时也需要同时删除边(y, x)
  12.       if (!this.isDirect) {
  13.         // 删除边(x, y)
  14.         // 如果顶点的第一个节点即是要找的节点
  15.         if (curVerX.data === y) {
  16.           // 删除第一条边，把顶点x的nextEdge作为第一条边
  17.           this.adj[posX].firstEdge = curVerX.nextEdge;
  18.           this.add[posX].outNum--;
  19.           curVerX = null;
  20.         }
  21.         // curVerX如果存在，说明要找的节点不是顶点的第一个节点
  22.         while (curVerX) {
  23.           let preVerX = curVerX;
  24.           // 继续查找下一条边
  25.           curVerX = curVerX.nextEdge;
  26.           if (curVerX && curVerX.data === y) {
  27.             preVerX.nextEdge = curVerX.nextEdge;
  28.             this.adj[posX].outNum--;
  29.             curVerX = null;
  30.           }
  31.         }
  32.         // 删除边(y, x)
  33.         // 如果顶点的第一个节点即是要找的节点
  34.         if (curVerY.data === x) {
  35.           // 把y顶点的下一条边赋值给第一条边
  36.           this.adj[posY].firstEdge = curVerY.nextEdge;
  37.           this.adj[posY].outNum--;
  38.           curVerY = null;
  39.         }
  40.         //curVerY如果存在，说明要找的节点不是顶点的第一个节点
  41.         while (curVerY) {
  42.           let preVerY = curVerY;
  43.           curVerY = curVerY.nextEdge;
  44.           if (curVerY && curVerY.data === x) {
  45.             preVerY.nextEdge = curVerY.nextEdge;
  46.             this.adj[posY].outNum--;
  47.             curVerY = null;
  48.           }
  49.         }
  50.       } else {
  51.         // 删除边<x, y>
  52.         // 如果顶点的第一个节点即是要找的节点
  53.         if (curVerX.data === y) {
  54.           this.adj[posX].firstEdge = curVerX.nextEdge;
  55.           this.adj[posX].outNum--;
  56.           curVerX = null;
  57.         }
  58.         // curVerX如果存在，说明要找的节点不是顶点的第一个节点
  59.         while (curVerX) {
  60.           let preVerX = curVerX;
  61.           curVerX = curVerX.nextEdge;
  63.           if (curVerx && curVerX.data === y) {
  64.             preVerX.nextEdge = curVerX.nextEdge;
  65.             this.adj[posX].outNum--;
  66.             curVerX = null;
  67.           }
  68.         }
  69.         this.adj[posY].inNum--;
  70.       }
  71.       this.eNum--;
  72.     }
  73.   }

删除顶点

与删除边操作不同的是，在删除图中的一个顶点时，与此顶点所有相邻的边都要删除。此时需要分为两步操作，第一步删除所有以x为起点的边，第二步删除所有以x为终点的边。

  1. // 从图中删除顶点x,与删除边操作不同
  2.   //在删除图中的一个顶点时，与此顶点所有相邻的边都要删除。
  3.   //   两步操作，第一步删除所有以x为起点的边，第二步删除所有以x为终点的边
  4.   deleteVertex(x) {
  5.     let pos = this._find(x);
  6.     if (pos > -1) {
  7.       // 删除从x出发的边
  8.       let curVer = this.adj[pos].firstEdge;
  9.       while (curVer) {
  10.         this.removeEdge(x, curVer.data);
  11.         curVer = curVer.nextEdge;
  12.       }
  13.       // 删除终点是x的边
  14.       for (let i = 0; i < this.adj.length; i++) {
  15.         let temVer = this.adj[i].firstEdge;
  17.         while (temVer) {
  18.           if (temVer.data === x) {
  19.             this.removeEdge(this.adj[i].data, temVer.data);
  20.           }
  21.           temVer = temVer.nextEdge;
  22.         }
  23.       }
  24.       // 删除顶点x
  25.       this.adj.splice(pos, 1);
  26.     }
  27.   }

所有相邻节点

  1. // 与顶点x邻接的所有节点
  2.   //   不断的遍历每个顶点的边
  3. allNeightbors(x) {
  4.   let pos = this._find(x);
  6.   if (pos > -1) {
  7.     let result = `${x}`;
  8.     let curVer = this.adj[pos].firstEdge;
  10.     while (curVer) {
  11.       result += `=>${curVer.data}`;
  12.       curVer = curVer.nextEdge;
  13.     }
  15.     console.log(result);
  16.   }
  17. }

测试邻接表结构

  1. let arr = ["A", "B", "C", "D", "E"];
  2. let myGraph = new Graph(0);
  3. myGraph.initVertex(arr);
  4. myGraph.addEdge("A", "B");
  5. myGraph.addEdge("A", "C");
  6. myGraph.addEdge("A", "E");
  7. myGraph.addEdge("B", "E");
  8. myGraph.addEdge("C", "E");
  9. myGraph.addEdge("D", "B");
  10. myGraph.addEdge("D", "C");
  11. myGraph.addEdge("D", "E");
  12. for (let i = 0; i < arr.length; i++) {
  13.   myGraph.allNeightbors(arr[i]);
  14. }
  15. // 断开c和、e的连接
  16. myGraph.removeEdge("C", "E");
  17. for (let i = 0; i < arr.length; i++) {
  18.   myGraph.allNeightbors(arr[i]);
  19. }

输出为：

  1. A=>B=>C=>E
  2. B=>A=>E=>D
  3. C=>A=>E=>D
  4. D=>B=>C=>E
  5. E=>A=>B=>C=>D

将C和E之间断开测试

  1. myGraph.removeEdge('C', 'E');
  2. for(let i=0; i<arr.length; i++) {
  3.     myGraph.allNeightbors(arr[i]);
  4. }
  5. // 输出为
  6. A=>B=>C=>E
  7. B=>A=>E=>D
  8. C=>A=>D
  9. D=>B=>C=>E
  10. E=>A=>B=>D

图的深度遍历和广度遍历

代码结构：

  1. class Graph {
  2.     // 广度优先求出图中所有的连通分量，从给定的顶点x开始
  3.     BFSTraverse(x) {}
  5.     // 实际进行广度遍历的函数，每次遍历都是得到一个以顶点x为起点的连通分量
  6.     _BFS(x, visited) {}
  8.     // 深度优先求出图中所有的连通分量，从给定的顶点x开始
  9.     DFSTraverse(x) {}
  11.     // 实际进行深度遍历的函数，每次遍历都是得到一个以顶点x为起点的连通分量
  12.     _DFS(x, visited) {}
  13. }

广度优先遍历

BFS breath first search | BFSTraverse(x)函数每次从顶点x出发，使用_BFS()函数遍历图中以x为起点的一个连通分量。如果从x开始不能遍历到图中的所有顶点，则BFSTraverse(x)会尝试从另一个没有被访问过的顶点开始求其连通分量，直到图中所有的顶点都被访问过
首先访问起始顶点v，接着由v出发，依次访问v的各个未访问过的邻接顶点w1，w2，……，然后再依次访问w1，w2，……，wi的所有未被访问过的邻接顶点。
再从访问过的顶点出发，再访问所有未被访问过的邻接顶点，依次类推，直到所有的顶点都被访问过。完成广度优先遍历

  • 如果无向图是连通的，则从给定的顶点出发，仅需一次遍历就能够访问图中所有的顶点；如果无向图是非连通的，则给定的顶点出发，一次遍历只能访问到该顶点所在的连通分量的所有顶点，而对于图中其他连通分量的顶点，则无法通过这次遍历访问。
  • 有向图，如果从初始点到图中的每个顶点都有路径，则能访问到图中所有的顶点，否则不能访问到所有的顶点。

使用visted数组表示顶点是否被访问过。

  2. // 广度优先求出图中所有的连通分量，从给定的顶点x开始
  3. BFSTraverse(x = this.adj[0].data) {
  4.   // 访问过的标记数组，标记数组和顶点表 相关联的是下标
  5.   let visited = [];
  6.   let result = "";
  7.   for (let i = 0; i < this.adj.length; i++) {
  8.     // 设置一个visited数组，将其全部赋值为false表示所有的节点都没有被访问过
  9.     visited[i] = false;
  10.   }
  11.   // 使用_BFS()函数来求以顶点x为起点的连通分量，并将visited数组作为参数传入
  12.   // 求以x为起始点的连通分量, 第一次A
  13.   result = this._BFS(x, visited);
  14.   // 求出以顶点x为起点的连通分量后，BFSTraverse()函数则再次遍历visited数组，查看是否还有未被访问过的节点。
  15.   for (let i = 0; i < visited.length; i++) {
  16.     // 如果有还未被访问过的顶点，则从该顶点继续遍历
  17.     if (!visited[i]) {
  18.       let x = this.adj[i].data;
  19.       // 再次调用_BFS()函数，并传入未被访问过的顶点和visited数组。
  20.       result += `&${this._BFS(x, visited)}`; // 其他的连通分量
  21.     }
  22.   }
  23.   return result;
  24. }
  26. //两个循环，外层循环每次从队列中取出一个顶点，使用内层循环依次访问该顶点的边表中的所有节点。
  27. // 实际进行广度遍历的函数，每次遍历都是 获得一个以顶点x为起点的所有连通分量
  28. _BFS(x, visited) {
  29.   let result = "";
  30.   let queue = [];
  31.   let pos = this._find(x);
  32.   if (pos > -1) {
  33.     result += `${x}`;
  34.     visited[pos] = true;
  35.     // 获取到当前顶点
  36.     let curVer = this.adj[pos];
  37.     // 顶点x入队列
  38.     queue.push(curVer);
  39.     while (queue.length) {
  40.       // 取出队列的第一个值，取出一个顶点
  41.       curVer = queue.shift();
  42.       // 回到顶点的表中，再次计算
  43.       pos = this._find(curVer.data);
  44.       curVer = this.adj[pos].firstEdge; // 第一次是 A - B
  45.       //检测顶点的所有邻接点，内层循环依次访问该顶点边表中所有节点
  46.       while (curVer) {
  47.         pos = this._find(curVer.data); // B
  48.         // 如果当前顶点未被访问过
  49.         if (!visited[pos]) {
  50.           result += `->${curVer.data}`;
  51.           // 标记未已经访问过
  52.           visited[pos] = true;
  53.           // 内层循环不断的将当前起始节点的所有未访问过的边表节点加入队列
  54.           queue.push(curVer);
  55.         }
  56.         curVer = curVer.nextEdge;
  57.       }
  58.     }
  59.   }
  60.   return result;
  61. }

简而言之，_BFS()函数就是从顶点x出发，依次遍历与x相邻的节点，再从这些相邻的节点出发再访问各自的相邻节点。为了不重复访问同一个节点，使用visited数组做访问标识，如果发现要访问的节点已经被访问过了就跳过这个节点。
广度优先遍历下图

图graph - 图7
构建图结构

  1. let arr = ['V0', 'V1', 'V2', 'V3', 'V4', 'V5', 'V6', 'V7', 'V8'];
  2. let myGraph = new Graph(0);  // 0表示无向图
  3. myGraph.initVertex(arr);
  4. // 插入边
  5. myGraph.addEdge('V0', 'V1');
  6. myGraph.addEdge('V0', 'V5');
  7. myGraph.addEdge('V1', 'V2');
  8. myGraph.addEdge('V1', 'V6');
  9. myGraph.addEdge('V1', 'V8');
  10. myGraph.addEdge('V2', 'V3');
  11. myGraph.addEdge('V2', 'V8');
  12. myGraph.addEdge('V3', 'V4');
  13. myGraph.addEdge('V3', 'V6');
  14. myGraph.addEdge('V3', 'V7');
  15. myGraph.addEdge('V3', 'V8');
  16. myGraph.addEdge('V4', 'V5');
  17. myGraph.addEdge('V4', 'V7');
  18. myGraph.addEdge('V5', 'V6');
  19. myGraph.addEdge('V6', 'V7');
  20. // 输出图的邻接表
  21. for(let i=0; i<arr.length; i++) {
  22.     myGraph.allNeightbors(arr[i]);
  23. }
  24. /*
  25. V0=>V1=>V5
  26. V1=>V0=>V2=>V6=>V8
  27. V2=>V1=>V3=>V8
  28. V3=>V2=>V4=>V6=>V7=>V8
  29. V4=>V3=>V5=>V7
  30. V5=>V0=>V4=>V6
  31. V6=>V1=>V3=>V5=>V7
  32. V7=>V3=>V4=>V6
  33. V8=>V1=>V2=>V3
  34. */
  36. // 从顶点V0到V8依次广度优先遍历
  37. /*
  38. V0->V1->V5->V2->V6->V8->V4->V3->V7
  39. V1->V0->V2->V6->V8->V5->V3->V7->V4
  40. V2->V1->V3->V8->V0->V6->V4->V7->V5
  41. V3->V2->V4->V6->V7->V8->V1->V5->V0
  42. V4->V3->V5->V7->V2->V6->V8->V0->V1
  43. V5->V0->V4->V6->V1->V3->V7->V2->V8
  44. V6->V1->V3->V5->V7->V0->V2->V8->V4
  45. V7->V3->V4->V6->V2->V8->V5->V1->V0
  46. V8->V1->V2->V3->V0->V6->V4->V7->V5
  47. */

如果断开V0和V1，V5的连接， 且还是从V0开始遍历会发生什么呢？
图graph - 图8

  1. myGraph.removeEdge('V0', 'V1');
  2. myGraph.removeEdge('V0', 'V5');
  4. for(let i=0; i<arr.length; i++) {
  5.     console.log(myGraph.BFSTraverse(arr[i]));
  6. }
  7. // V0成单独的连通分量
  8. /*
  9. V0&V1->V2->V6->V8->V3->V5->V7->V4
  10. V1->V2->V6->V8->V3->V5->V7->V4&V0
  11. V2->V1->V3->V8->V6->V4->V7->V5&V0
  12. V3->V2->V4->V6->V7->V8->V1->V5&V0
  13. V4->V3->V5->V7->V2->V6->V8->V1&V0
  14. V5->V4->V6->V3->V7->V1->V2->V8&V0
  15. V6->V1->V3->V5->V7->V2->V8->V4&V0
  16. V7->V3->V4->V6->V2->V8->V5->V1&V0
  17. V8->V1->V2->V3->V6->V4->V7->V5&V0
  18. */

深度优先遍历

首先访问图中某一个起始顶点x，然后由x出发，访问与x邻接且未被访问的任一个顶点w1，再访问与w1邻接的未被访问的任一个顶点w2，重复这个过程，当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直到图中所有的顶点都被访问过为止。
与广度优先遍历一样，从某个给定顶点开始，如果无向图是连通的，则这个给定的顶点出发，仅需一次遍历就能够访问图中所有的顶点；如果无向图是非连通的，则从这个顶点出发，一次遍历只能访问到该顶点所在的连通分量的所有顶点，而对于图中其他连通分量的顶点，则无法通过这次遍历访问。
对于有向图来说，如果从初始点到图中的每个顶点都有路径，则能够访问到图中所有的顶点，否则不能访问到所有的顶点。
代码如下：

  1. // 深度优先求出图中所有的连通分量，从给定的顶点x开始
  2. DFSTraverse(x) {
  3.   let result = "";
  4.   //设置一个visited数组，
  5.   let visited = [];
  6.   for (let i = 0; i < this.adj.length; i++) {
  7.     //将其全部赋值为false，表示所有的节点都没有被访问过。
  8.     visited[i] = false;
  9.   }
  10.   //使用_DFS()函数来求以顶点x为起点的连通分量，并将visited数组作为参数传入
  11.   result = this._DFS(x, visited);
  12.   //当_DFS()函数求出以顶点x为起点的连通分量后，DFSTraverse()函数再次遍历visited数组，
  13.   //查看是否还有未被访问过的节点。
  14.   // 如果还有未被访问过的顶点，则以该顶点再次出发，
  15.   for (let i = 0; i < visited.length; i++) {
  16.     if (!visited[i]) {
  17.       let x = this.adj[i].data;
  18.       //再次调用_DFS()函数，并传入未被访问过的顶点和visited数组。
  19.       result += `&${this._DFS(x, visited)}`;
  20.     }
  21.   }
  22.   return result;
  23. }
  25. // 实际进行深度遍历的函数，每次遍历都是得到 以顶点x为起点的连通分量
  26. _DFS(x, visited) {
  27.   let result = "";
  28.   let stack = []; // 辅助堆栈
  29.   let pos = this._find(x);
  30.   let curVer = this.adj[pos]; // 根据给的x值找到具体的顶点
  31.   if (pos > -1) {
  32.     stack.push(curVer); // 顶点x入栈
  33.     result += `${x}`;
  34.     // 访问过的顶点，做标记
  35.     visited[pos] = true;
  36.     while (stack.length) {
  37.       // 获取栈顶元素,不能使用pop，pop会把节点删除
  38.       curVer = stack[stack.length - 1];
  39.       // 获取栈顶元素在顶点表中的位置
  40.       pos = this._find(curVer.data);
  41.       // 获取顶点的第一个邻接点
  42.       curVer = this.adj[pos].firstEdge;
  43.       // 邻接点存在
  44.       while (curVer) {
  45.         pos = this._find(curVer.data);
  47.         if (visited[pos]) {
  48.           // 如果该节点已经访问过了,则访问该节点的下一个相邻的节点
  49.           curVer = curVer.nextEdge;
  50.         } else {
  51.           stack.push(curVer);
  52.           result += `->${curVer.data}`;
  53.           visited[pos] = true;
  54.           break;
  55.         }
  56.       }
  57.       // 如果顶点的所有邻接点都访问过
  58.       if (!curVer) stack.pop();
  59.     }
  60.   }
  61.   return result;
  62. }

与广度优先遍历一样，也使用visited标记数组，作用是相同的。
_DFS()函数：

当不能再继续向下访问时，依次退回到最近被访问的顶点，使用一个堆栈来辅助完成遍历。每次遇到一个节点，就将其压入堆栈，做已访问标识后访问其一个相邻的节点：

  • 如果发现这个节点的相邻节点中有未被访问过的，则访问这个节点，并将其压入堆栈，做已访问标识，再访问这个节点的一个相邻节点
  • 如果这个节点的所有相邻节点都被访问过了，而此时堆栈还不为空，就将其弹出去。再取堆栈的栈顶元素重复步骤1的操作，如果这个节点的所有相邻节点又全被访问过了，就再将其弹出去…，依此往复，直到堆栈为空结束。

从顶点V0到V8对其进行深度优先遍历：
图graph - 图9

  1. for(let i=0; i<arr.length; i++) {
  2.     console.log(myGraph.DFSTraverse(arr[i]));
  3. }
  5. /*
  6. V0->V1->V2->V3->V4->V5->V6->V7->V8
  7. V1->V0->V5->V4->V3->V2->V8->V6->V7
  8. V2->V1->V0->V5->V4->V3->V6->V7->V8
  9. V3->V2->V1->V0->V5->V4->V7->V6->V8
  10. V4->V3->V2->V1->V0->V5->V6->V7->V8
  11. V5->V0->V1->V2->V3->V4->V7->V6->V8
  12. V6->V1->V0->V5->V4->V3->V2->V8->V7
  13. V7->V3->V2->V1->V0->V5->V4->V6->V8
  14. V8->V1->V0->V5->V4->V3->V2->V6->V7
  15. */

图graph - 图10

  1. for(let i=0; i<arr.length; i++) {
  2.     console.log(myGraph.DFSTraverse(arr[i]));
  3. }
  5. /*
  6. V0&V1->V2->V3->V4->V5->V6->V7->V8
  7. V1->V2->V3->V4->V5->V6->V7->V8&V0
  8. V2->V1->V6->V3->V4->V5->V7->V8&V0
  9. V3->V2->V1->V6->V5->V4->V7->V8&V0
  10. V4->V3->V2->V1->V6->V5->V7->V8&V0
  11. V5->V4->V3->V2->V1->V6->V7->V8&V0
  12. V6->V1->V2->V3->V4->V5->V7->V8&V0
  13. V7->V3->V2->V1->V6->V5->V4->V8&V0
  14. V8->V1->V2->V3->V4->V5->V6->V7&V0
  15. */

最小生成树

最小生成树具有某些特定的性质：

  • 最小生成树的边数总是比其顶点数少一个。
  • 最小生成树可能不是唯一的，但是不同的最小生成树的权值之和总是相同的。

求最小生成树有两种非常经典的方法——普里姆算法和克鲁斯卡尔算法， 在本篇中会详细介绍如何使用JS实现这两种经典算法。

代码结构

  1. class Graph {
  2.     // ...以上实现的代码，省略
  4.     // 获取边(x, y)或<x, y>对应的权值
  5.     getEdgeWeight(x, y) {}
  7.     // 获得图中权重之和
  8.     getSumOfWeight() {}
  10.     // 判断当前的图是否是连通图
  11.     isConnected(x = this.adj[0].data) {}
  13.     // 普里姆算法
  14.     getPrimMST(){}
  16.     // 获取图中所有的边
  17.     getAllEdges() {}
  19.     // 克鲁斯卡尔算法
  20.     getKruskalMST(){}
  21. }

在求最小生成树之前，还有一些准备工作要做:

  • 获取图中边的权值
  • 判断给定的图是否是一幅连通图
  • 获取图中的权值之和
  • 获取图中所有的边

首先是获取图中边上的权值，不管是普里姆算法还是克鲁斯卡尔算法都要用到这个方法，该方法获取边(x, y)或对应的权值，如果顶点x和y构不成边的话，就返回0。

  1. // 获取边(x, y)或<x, y>对应的权值
  2. getEdgeWeight(x, y) {
  3.   let pos = this._find(x);
  4.   if (pos > -1) {
  5.     let curVer = this.adj[pos].firstEdge;
  6.     while (curVer) {
  7.       if (curVer.data === y) return curVer.weight;
  8.       curVer = curVer.nextEdge;
  9.     }
  10.     return 0;
  11.   }
  12. }

判断给定的图是否是一幅连通图

然后要知道所求最小生成树的图是不是连通图，如果不是连通图，那么对其求最小生成树就没有意义。

该方法使用到了上文提到的_BFS方法，或_DFS方法来遍历一幅图，若其在遍历完一次之后仍有顶点未被访问到，那么说明这张图不是一幅连通图。

  1. // 判断当前的图是否是连通图
  2. isConnected(x = this.adj[0].data) {
  3.   // 任选一个点作为顶点
  4.   let len = this.adj.length;
  5.   let visited = new Array(len); // 把所有点都有进行记录，后边判断是否还有未被访问的点时使用
  6.   for (let i = 0; i < len; i++) {
  7.     visited[i] = false;
  8.   }
  9.   this._BFS(x, visited);
  10.   // 如果遍历一边之后仍有顶点未被访问，则该图不是连通的
  11.   for (let i = 0; i < len; i++) {
  12.     if (!visited[i]) return false;
  13.   }
  14.   return true;
  15. }

普里姆算法

图graph - 图11
按照上图查找下一步的过程，可以得出最小生成树的结果。接下来用代码实现。
尝试使用文字来描述这个过程：

假设 N={V, E} 是连通网，V是图中所有顶点的集合，E是图中所有边的结合，ET是N上最小生成树边的集合，初始时ET={}，VT={V0}。 算法在u∈VT，v∈V-VT中选择一条权值最小的边（u，v）加入ET集合中，同时将v加入VT中，重复这个过程，一直到VT等于V为止。

换上一种更容易懂的说法：假设V是图中所有所有顶点的集合，VT初始时在V中任选一个顶点（算法实现里假设总是选择第一个顶点），找出VT与V-VT中所有能构成的边的组合，选择其中权重最小的组合，然后取出这个组合在V-VT的中顶点放入VT中，直到VT=V。

  1. // 普里姆算法
  2. getPrimMSTree() {
  3.   // 不是连通图时求最小生成树没有意义
  4.   if (!this.isConnected) return;
  5.   let V = this.adj; // 顶点集V
  6.   let Vt = [V[0]]; // 添加任意一个顶点
  7.   let VVt = V.filter((x) => Vt.indexOf(x) === -1); // VVt = V - Vt, 出去Vt点的其他点集合
  8.   //初始化空图
  9.   let MinTree = new Graph(this.isDirect);
  10.   // 将点集合，插入到树中
  11.   V.forEach((x) => MinTree.insertVertex(x.data));
  12.   // 若树中不含全部顶点
  13.   while (Vt.length !== V.length) {
  14.     //当找到权值最小的边时，m VT是边的一个顶点
  15.     let mVt = null;
  16.     //当找到权值最小的边时，m V_VT是边的另一个顶点
  17.     let mVVt = null;
  18.     // 最小权重值，先将minW赋个极大的数值
  19.     let minW = Number.MAX_SAFE_INTEGER;
  20.     // 在VT和V_VT中找到边中的最小权值
  21.     // 从VT中取出一个顶点
  22.     for (let i = 0; i < Vt.length; i++) {
  23.       // 从VVt中取出一个顶点
  24.       for (let j = 0; j < VVt.length; j++) {
  25.         // 获取Vt-VVt之间的权重值
  26.         let weight = this.getEdgeWeight(Vt[i].data, VVt[j].data);
  27.         // 权重值weight小于最小值
  28.         if (weight && minW > weight) {
  29.           // 更新最小值
  30.           minW = weight;
  31.           mVt = Vt[i];
  32.           mVVt = VVt[j];
  33.         }
  34.       }
  35.     }
  36.     Vt.push(mVVt);
  37.     MinTree.addEdge(mVt.data, mVVt.data, minW);
  38.     VVt = V.filter((x) => Vt.indexOf(x) === -1);
  39.   }
  40.   return MinTree;
  41. }

算法在u∈VT，v∈V-VT中选择一条权值最小的边（u，v）加入ET集合中，同时将v加入VT中

其在算法中的实现过程是在新建的空树中添加一条连接顶点u和v的一条边（u，v），并赋予相同的权值。重复这个过程，随着VT和V相等之后，这个新建的图就变成最小生成树
实现一个获取权重之和的函数，来判断最小生成树是否正确生成

  1. // 获得图中权重之和
  2. getSumOfWeight() {
  3.   // 当图不是连通的时候，获取权重之和没有意义
  4.   if (!this.isConnected()) return;
  5.   let sum = 0;
  6.   let vertex = this.adj;
  7.   if (!this.isDirect) {
  8.     // 如果是无向图
  9.     for (let i = 0; i < vertex.length - 1; i++) {
  10.       for (let j = i; j < vertex.length; j++) {
  11.         let weight = this.getEdgeWeight(vertex[i].data, vertex[j].data);
  13.         if (weight) sum += weight;
  14.       }
  15.     }
  16.   } else {
  17.     for (let i = 0; i < vertex.length; i++) {
  18.       for (let j = 0; j < vertex.length; j++) {
  19.         let weight = this.getEdgeWeight(vertex[i].data, vertex[j].data);
  21.         if (weight) sum += weight;
  22.       }
  23.     }
  24.   }
  25.   return sum;
  26. }

使用Prim算法求得最小生成树，并用这个方法来测试下上图：

  1. let arr = ['A', 'B', 'C', 'D', 'E'];
  2. let myGraph = new Graph(0);  // 0表示无向图
  3. myGraph.initVertex(arr);
  5. myGraph.addEdge('A', 'B', 5);
  6. myGraph.addEdge('A', 'C', 7);
  7. myGraph.addEdge('A', 'E', 6);
  8. myGraph.addEdge('B', 'D', 2);
  9. myGraph.addEdge('B', 'E', 4);
  10. myGraph.addEdge('C', 'D', 4);
  11. myGraph.addEdge('C', 'E', 2);
  12. myGraph.addEdge('D', 'E', 3);
  14. let MSTree = myGraph.getPrimMSTree();  
  16. console.log(MSTree.BFSTraverse());  // 广度优先遍历下看看
  17. // 输出A->B->D->E->C
  18. console.log(MSTree.DFSTraverse());  // 深度优先遍历下看看
  19. // 输出A->B->D->E->C
  20. console.log(MSTree.getSumOfWeight());
  21. // 输出12

克鲁斯卡尔算法

使用图片来描述克鲁斯卡尔算法
图graph - 图12
克鲁斯卡尔算法比较好理解一些，它是一种按照权值递增次序选择合适的边来构造最小生成树的方法。
假设在一个给定的带权连通无向图 N=(V, E) 中，其对应的最小生成树是 T=(VT, ET)，克鲁斯卡尔算法的过程为：
初始时有VT=V，ET=Ø。可以把每个顶点都看作是一颗独立的树，T此时是一个仅含有顶点的森林，在E-ET中按照权值递增的顺序依次选择一条边，如果将这条边加入T后不构成回路，则将其加入ET中，否则舍弃，直到ET中边的个数比T中的顶点的个数少一个。
算法的基本思想是先找权重最小的边，再找权重次小的边…，如果找到的边加入最小生成树中不构成回路就保留，否则舍弃。
为了在所有的边中按照权值递增的次序选择边，在实现克鲁斯卡尔算法前首先要实现一个方法用来获取图中的所有的边。这个方法叫getAllEdges

  1. // 获取图中所有的边
  2. getAllEdges() {
  3.   let vertex = this.adj; // 图中的所有顶点
  4.   let edges = []; // 在edges中存放图中所有的边
  6.   // 如果是无向图
  7.   if (!this.isDirect) {
  8.     for (let i = 0; i < vertex.length - 1; i++) {
  9.       for (let j = i; j < vertex.length; j++) {
  10.         // 判断2个点之间是否有边
  11.         if (this.hasEdge(vertex[i].data, vertex[j].data)) {
  12.           let weight = this.getEdgeWeight(vertex[i].data, vertex[j].data);
  13.           edges.push([vertex[i].data, vertex[j].data, weight]);
  14.         }
  15.       }
  16.     }
  17.   }
  18.   // 如果有向图
  19.   else {
  20.     for (let i = 0; i < vertex.length; i++) {
  21.       for (let j = 0; j < vertex.length; j++) {
  22.         if (this.hasEdge(vertex[i].data, vertex[j].data)) {
  23.           let weight = this.getEdgeWeight(vertex[i].data, vertex[j].data);
  24.           edges.push([vertex[i].data, vertex[j].data, weight]);
  25.         }
  26.       }
  27.     }
  28.   }
  29.   // 在edges数组中，每一个元素都是一个数组，该数组一共三个元素
  30.   // 顶点x的值，顶点y的值，和顶点x和y构成的边上的权值
  31.   return edges;
  32. }

这个方法返回一个二维数组，在edges数组中，每一个元素都是一个数组，该数组一共三个元素，分别是顶点x的值，顶点y的值，和顶点x和y构成的边上的权值。

在算法中，新建一颗空树，并用给定的连通图中的顶点来初始化这颗树。一开始的时候，由于这个空树中只有顶点，所以在这棵空树中的连通分量就是顶点的数目，每次找到一条符合条件的权值最小的边加入这颗空树中后，该空树的连通分量就会减一，如果循环一直继续的话，随着边的不断加入，如果不加以控制的话，该最小生成树最后就会形成回路，需要在其形成回路前终止循环，也就是随着边的不断加入，该最小生成树中的连通分量在等于1之前结束循环。

在找到权值最小的边之后，假设这条边叫做(u, v)，从顶点u开始对该尚未形成的最小生成树进行一次广度或者深度优先遍历，因为之前的遍历算法中，如果一张图中具有多个连通分量，那么对这张图进行遍历后的结果就会以 ‘&’ 将每个连通分量隔开，因为是从顶点u开始遍历的，那么在遍历后的结果中，顶点u所在的连通分量一定在第一个 ‘&’ 分隔符之前，所以算法中在遍历的结果中只取第一个 ‘&’ 前面的字符串，如果发现顶点v不在该字符串当中，那就说明u和v属于树中不同的连通分量，可以放心大胆的将边(u，v)加入要生成的最小生成树当中而不必担心产生回路。而如果顶点u和顶点v属于同一个连通分量的话，就说明顶点u和顶点v之间已经具有路径了，此时如果再直接连接顶点u和顶点v则必然会产生回路，所以就应该舍弃这条边

  1. // 克鲁斯卡尔算法
  2.   //   算法的基本思想是先找权重最小的边，再找权重次小的边
  3.   getKruskalMSTree() {
  4.     // 不是连通图时求最小生成树没有意义
  5.     if (!this.isConnected()) return;
  6.     let V = this.adj; // 顶点集V
  7.     let numS = V.length; // 树中的连通分量
  8.     let E = this.getAllEdges(); // 在E中存放图中所有的边
  9.     let mEdge = null;
  10.     let MSTree = new Graph(this.isDirect); // 初始化空树
  11.     V.forEach((x) => MSTree.insertVertex(x.data)); // 树中只有顶点
  12.     while (numS > 1) {
  13.       let minWeight = Number.MAX_SAFE_INTEGER;
  14.       // 从图中取出权值最小的边<u, v>
  15.       for (let i = 0; i < E.length; i++) {
  16.         if (E[i][2] < minWeight) {
  17.           mEdge = E[i];
  18.           minWeight = E[i][2];
  19.         }
  20.       }
  21.       //广度优先遍历
  22.       let result = MSTree.BFSTraverse(mEdge[0]);
  23.       //只取&前面的字符串
  24.       result = result.split("&")[0];
  25.       let pos = result.indexOf(mEdge[1]);
  26.       // 如果u和v属于树中不同的连通分量，就将此边加入生成树中
  27.       // 从顶点mEdge[0]遍历一遍发现没有mEdge[1]，说明两个顶点不在一个连通分量之中
  28.       if (pos === -1) {
  29.         MSTree.addEdge(mEdge[0], mEdge[1], mEdge[2]);
  30.         numS--;
  31.       }
  32.       // 去掉E中权值最小的边
  33.       E = E.filter((x) => x !== mEdge);
  34.     }
  35.     return MSTree;
  36.   }

测试下克鲁斯卡尔算法

  1. let MSTree = myGraph.getKruskalMST();
  2. console.log(MSTree.BFSTraverse());  // 广度优先遍历下看看
  3. // 输出A->B->D->E->C
  4. console.log(MSTree.DFSTraverse());  // 深度优先遍历下看看
  5. // 输出A->B->D->E->C
  6. console.log(MSTree.getSumOfWeight());
  7. // 输出12

最短路径

在带权图中，把从一个顶点到图中任一个顶点的一条路径（可能有多条路径）上所经过边上的权值之和定义为该路径的带权路径长度，其中权值之和最小的那条路径叫做最短路径。【在有向图中】
求最短路径还可以分为求单源最短路径和各个顶点之间的最短路径问题。本篇中只会介绍使用Dijkstra算法求单源最短路径。

Dijkstra算法

求带权有向图中某个源点到其余各顶点的最短路径，最常用的是Dijkstra算法。该算法设置一个集合S（可用数组实现）用来记录已求得的最短路径的顶点。该集合初始时将源点放入其中，此后每求出源点到某个顶点的最短路径，就将该顶点放入集合中来。
除此之外，实现该算法时用到了两个辅助数组：

  • dist：记录了从源点到其他各顶点当前的最短路径长度。
  • path：表示从源点到顶点 i 之间的最短路径。

假设从顶点0出发，集合S最初只包含顶点0，邻接矩阵arcs表示带权有向图， arcs[i][j]表示有向边的权值，如果不存在有向边，则arcs[i][j]记为无穷大，那么算法的步骤如下：

  1. 集合S初始时为{V0}，dist的初始值dist[i] = arcs[0][i]，i 表示顶点Vi。0表示顶点V0。
  2. 从顶点集合V-S中选出一个顶点，假设为Vj，其满足dist[j] = Min {dist[i] | Vi∈V-S}，Vj就是当前求得的V0到Vj的最短路径的终点，并令S = S ∪ { Vj }。
  3. 修改从V0出发到集合V-S上任意一个顶点Vk可到达的最短路径，V0初始时可能并不能直接到达顶点Vk，这时可以通过顶点 Vj 作为中转看看是否能够到达，或者通过Vj作为中转后到达的路径权值之后小于之前已有的数值，那么就可以做出一些修改了：如果dist[j] + arcs[j][k] < dist[k]，则令dist[k] = dist[j] + arcs[j][k]。

  4. 重复步骤2和3，直到所有的顶点都包含在集合S中。

    1. /**
    2. * 求带权图顶点x到其他顶点的最短路径
    3. * 从x到y可能有多条路径，把带权路径长度最短的那条路径称为最短路径
    4. * 求解最短路径的算法通常都依懒于一种性质，
    5. * 也就是两点之间的最短路径也包含了路径上的其他顶点间的最短路径
    6. * @param {*} x
    7. */
    8. // x点到其他各个点最短路径
    9. getShortestPath(x) {
    10. // 使用Dijkstra算法，
    11. // 如果是无向图或者边有负的权值时退出
    12. // 如果x不存在于图中时退出
    13. // 如果从顶点x到不了图中任意一个顶点则退出
    14. if (
    15.  !this.isDirect ||
    16.  this.getMinEdgeWeight() < 0 ||
    17.  this._find(x) === -1 ||
    18.  !this.isConnected(x)
    19. ) {
    20.  return -1;
    21. }
    23. var MAX = Number.MAX_SAFE_INTEGER;
    25. // 初始化
    26. var len = this.adj.length;
    28. // 在dist数组中，dist[i]的初值为顶点x到顶点i之间的权值，
    29. // x到i没有路径时，dist[i]记为无穷大
    30. var dist = [];
    31. var path = []; // path[i]表示顶点x到i的最短路径
    32. var vers = []; // 顶点集
    33. var exts = [x]; // 已找到最短路径的点的集合
    35. // 初始化path和dist数组
    36. for (let i = 0; i < len; i++) {
    37.  vers[i] = this.adj[i].data;
    38.  dist[i] = this.getEdgeWeight(x, vers[i]) || MAX;
    39.  if (dist[i] !== MAX) {
    40.    path[i] = `${x}->${vers[i]}`;
    41.  } else {
    42.    path[i] = "";
    43.  }
    44. }
    46. var rem = vers.filter((x) => exts.indexOf(x) === -1); // 剩余的顶点
    47. var n = 1;
    49. while (n < len) {
    50.  // 在dist中寻找最小值
    51.  var min = MAX;
    52.  var idx = -1;
    54.  for (let i = 0; i < len; i++) {
    55.    if (min > dist[i]) {
    56.      min = dist[i];
    57.      idx = i;
    58.    }
    59.  }
    61.  var Vj = vers[idx]; // 直接找到Vj
    62.  dist[idx] = MAX;
    63.  exts.push(Vj);
    64.  rem = vers.filter((x) => exts.indexOf(x) === -1);
    66.  console.log(path[idx]); // 输出最短路径
    68.  // 松弛工作
    69.  for (let i = 0; i < rem.length; i++) {
    70.    // Vj到其他节点的距离
    71.    var w = this.getEdgeWeight(Vj, rem[i]) || MAX;
    72.    var k = vers.indexOf(rem[i]);
    74.    if (w + min < dist[k]) {
    75.      dist[k] = w + min;
    76.      path[k] = `${path[idx]}->${rem[i]}`;
    77.    }
    78.  }
    80.  n++;
    81. }
    82. }

图graph - 图13

  1. var arr = ['A', 'B', 'C', 'D', 'E'];
  2. var myGraph = new Graph(1);  // 1表示有向图
  3. myGraph.initVertex(arr);
  5. myGraph.addEdge('A', 'B', 10);
  6. myGraph.addEdge('A', 'C', 3);
  7. myGraph.addEdge('B', 'C', 1);
  8. myGraph.addEdge('B', 'D', 2);
  9. myGraph.addEdge('C', 'B', 4);
  10. myGraph.addEdge('C', 'D', 8);
  11. myGraph.addEdge('C', 'E', 2);
  12. myGraph.addEdge('D', 'E', 7);
  13. myGraph.addEdge('E', 'D', 9);
  15. // 查看邻接表
  16. for(let i=0; i<arr.length; i++) {
  17.   myGraph.allNeightbors(arr[i]);
  18. }
  20. // 输出：
  21. // A=>B=>C   
  22. // B=>C=>D   
  23. // C=>B=>D=>E
  24. // D=>E
  25. // E=>D
  27. // 用上面写的代码求顶点A到其他顶点的最短路径
  28. myGraph.getShortestPath('A');
  29. // 输出：
  30. // A->C
  31. // A->C->E
  32. // A->C->B
  33. // A->C->B->D

从输出中可以看到最短路径中有一个很重要的性质：两点之间最短路径包含路径上其他顶点间的最短路径。

完整代码
文档参考