数据结构 - 图（应用）

• 数据结构 - 图（基础概念）
• 数据结构 - 图（遍历）
• 数据结构 - 图（应用）

我们设计图这种数据结构，就是为了解决数据元素多对多问题，通常就是用于解决点对点之间的关系，由于图中每个顶点都可能与其他一个或多个顶点存在联系，因此设计的决策问题常常包含多个起点、多个终点或者多种选择的问题，图的应用大概可以分为如下几类：

• 最小生成树（Minimum Cost Spanning Tree）：即构造连通网的最小代价生成树。

  最小生成树用于解决的问题就是：把连通图中的多个或全部顶点连接起来且路径之和最小。简单来说，就是用 条边连接 个顶点，并且使权值的和最小。

  比如对于下列网图：

  

  假设现在我们的一个决策问题是选择连接 ~ 的所有顶点，且路径最短（权值为路径距离），这其实就是找寻连通网的最小生成树问题。

  用于找寻构建连通网的最小生成树的经典算法有：普里姆算法 和 克鲁斯卡尔算法，具体介绍如下：

  • 普里姆（Prim）算法：其思想是每次都从未选择的顶点中选择代价最小的顶点，并更新剩余顶点的最小代价值。

    普里姆算法的具体构建逻辑如下：

    1. 首先，以起始顶点开始，将其加入到最小生成树
    2. 然后遍历所有非最小生成树顶点，找到距离生成树任意顶点最近的邻接点，将该邻接点加入到最小生成树中
    3. 此时最小生成树已添加新成员，则还需对剩余顶点的最小价值进行更新
    4. 重复步骤2和3，直至最小生成树构造完成（即最小生成树顶点数达成）

    比如对于上图要求，连接顶点 ~ 所有顶点，且路径最短，对其使用普里姆算法构造最小生成树，其具体构建过程如下所示：

    1. 假设我们从顶点开始遍历，则第一步就是将顶点加入到最小生成树中，如下图所示：
    
    2. 然后遍历剩余顶点，即遍历顶点~，找到最短路径，从图中可以知道，距离最小生成树（此时即为顶点）的最短路径邻接点为，所以将顶点也加入到最小生成树中，如下图所示：
    
    3. 重复步骤2，此时最小生成树中的顶点有两个 和 ，剩余顶点距离这两个最小生成树顶点的最短路径为为，所以将顶点也加入到最小生成树中，如下图所示：
    
    4. 重复上述步骤，直至最小生成树包含所有顶点，此时即构造完成最小生成树，最终最小生成树如下图所示：
    

    普里姆算法对应的代码实现如下所示：
    注：下面代码以邻接矩阵表示图结构。

    // 头文件
    #ifndef __MGRAPH_H__
    #define __MGRAPH_H__
    
    
    #define MAX_VEX  100                  // 最大顶点数
    #define WEIGHT_INFINITY 65535         // 无效权值，用 65535 表示正无穷
    
    /*
    * V：表示顶点 Vertext 类型
    * E：表示边权值类型
    */
    template<typename V, typename E>
    struct MGraph {                       // 邻接矩阵
        V vexs[MAX_VEX];                  // 顶点数组（顶点表）
        E arc[MAX_VEX][MAX_VEX];          // 邻接矩阵（边表）
        int numsVertex = 0, numsEdge = 0; // 图中顶点数和边数
    
        void MiniSpanTree_Prim();         // 普里姆算法
    };
    #endif
    
    // 源文件
    #include "MGraph.h"
    #include <iostream>
    
    using namespace std;
    
    template<typename V, typename E>
    void MGraph<V, E>::MiniSpanTree_Prim() {
        // 保存相关顶点下标
        int adjvex[MAX_VEX];
        // 记录顶点间的权值
        // 当lowcost[i] = 0 时，表示顶点Vi加入到最小生成树
        E lowcost[MAX_VEX];
        // 将顶点V0加入到最小生成树
        lowcost[0] = 0;
        // 初始化第一个顶点下标为0
        adjvex[0] = 0;
    
        // 初始化
        for (int i = 1; i < this->numsVertex; ++i) {
            // lowcost 初始值为顶点V0的所有边权值
            lowcost[i] = this->arc[0][i];
            // 初始化都为V0的下标
            adjvex[i] = 0;
        }
    
        // 遍历剩余顶点，找到各个最短路径
        for (int i = 1; i < this->numsVertex; ++i) {
            // 此处模板可能存在类型不匹配问题，这里直接将 E 看出 int 类型
            E min = WEIGHT_INFINITY;
            int k = 0;
            // 遍历非最小生成树顶点，找到最短路径
            for (int j = 1; j < this->numsVertex; ++j) {
                if (lowcost[j] != 0 && lowcost[j] < min) {
                    min = lowcost[j];
                    // 记录最短路径的邻接点下标
                    k = j;
                }
            }
            cout << "第" << i << "轮最短路径的边为：（" << adjvex[k] << "," << k << ")" << endl;
            // 将当前最短路径邻接点加入到最小生成树
            lowcost[k] = 0;
    
            // 更新 lowcost 的值
            for (int j = 1; j < this->numsVertex; ++j) {
                // 当前顶点Vk与邻接点Vj的路径小于之前生成树顶点到Vj的路径，则进行替换
                if (lowcost[j] != 0 && this->arc[k][j] < lowcost[j]) {
                    lowcost[j] = this->arc[k][j];
                    // lowcost[j]被替换了，替换位置的当前顶点为Vk，进行记录
                    // 所以假设 lowcost 剩余路径最小值对应索引为 j,则其边为 (Vk,Vj)
                    adjvex[j] = k;
                }
            }
        }
    }
    

    上述代码采用一个lowcost来存储所有顶点权值，且当权值为0时，即表示当前索引顶点加入到最小生成树中，即：lowcost[0] = 0表示顶点加入到最小生成树，lowcost[i] = xxx，表示顶点没有被加入到最小生成树，其权值为xxx。
    所以，只要遍历lowcost数组一轮，找到非0的最小值，该索引对应的顶点即为此次最短路径邻接点下标，将该邻接点添加到最小生成树中（即lowcost[min] = 0）后，此时还需要更新该顶点的邻接点，添加到lowcost中，且只添加小于之前权值的对应邻接点，并将该替换位置的索引记录到adjvex[j] = k中，即若当前顶点为最新添加到最小生成树的顶点，且顶点的邻接点小于lowcost[j]，则进行替换lowcost[j] = this->arc[k][j]，如果下一轮遍历时，刚好lowcost[j]为最小值，即为最短路径邻接点，则其对应的最短路径边为 。

    最后，普里姆算法的时间复杂度为 。

  • 克鲁斯卡尔（Kruskal）算法：克鲁斯卡尔算法是以边的角度来构造最小生成树，因为权值是边的属性，直接根据边的权值由小到大排序，这样就很容易满足最短路径查询，但是需要注意的是在构造最小生成树时，避免出现环路。

  克鲁斯卡尔算法具体构造逻辑如下：

  1. 由于是对边进行操作，因此使用边集数组结构表示图
  2. 对边集数组按权值到校进行由小到大排序，方便我们在构造最小生成树时，依次查找最短路径
  3. 用一个数组parent表示最小生成树，当parent[i] = 0时，表示顶点不在最小生成树中;而当parent[i] = j时，表示顶点 和 存在于最小生成树中，边是最小生成树的一段最端路径
     注：这里的对最小生成树的构造比较巧妙，通过将数组下标作为一个顶点，该下标对应的值作为另一个顶点，这两个下标就构成了边的关系，且这两个下标对应的顶点就属于最小生成树中的其中两个顶点
     注：由于要避免出现环路，假设此时遍历的边为，则顶点 和

  比如还是对普里姆算法那个例子，连接顶点 ~ 所有顶点，且路径最短，这里对其使用克鲁斯卡尔算法构造最小生成树，其具体构建过程如下所示：

  1. 首先将原始图使用边集数组进行表示，且对边集数组按权值由小到大进行排序，如下图所示：
  

  2. 构造一个最小生成树parent，将其内所有元素初始化为0，表示没有顶点

  3. 遍历边集数组，由于其有序，因此第一个元素（即边）拥有最小权值（即最短路径），该边为，所以将顶点 和 加入到最小生成树中，即parent[4] = 7，如下图所示：

  
  4. 继续往后遍历边集数组，此时的最小权值边为，由于顶点 和 未与最小生成树中的任意顶点形成环，因此直接将其添加进最小生成树，即parent[2] = 8，如下图所示：
  
  5. 继续往后遍历边集数组，当 时，分别将边 ，，， 和 添加到最小生成树中，如下图所示：
  

  6. 继续遍历边集数组，此时 ，该边为，此时如果连接边，可以在图中很明显看到，顶点形成了一个环，因此不能将该边纳入到最小生成树中
     注：此处的重点在于如何判断出现环路，如果出现环路，说明该边的两个顶点都存在与最小生成树中，且在最小生成树中，这两个顶点本身就是连通的，即最小生成树存在一条路径连通这两个顶点或者存在一个连通子图连接这两个顶点。从上图可以看到，对于顶点，最小生成树中存在路径连通这两个顶点，即路径，因此，不能再添加这两个顶点形成的边，否则会构成环路。
     注：在代码中判断是否形成环路，可借助最小生成树数组parent，原理同样是判断边是否连通：parent[5] = 8;表示顶点与顶点连通，此时parent[8] = 6; parent[6] = 0，表示顶点与顶点连通，所以，最小生成树内已存在顶点和顶点的连通路径。

  7. 当 时，与上述一致，边与最小生成树形成了环路：parent[1] = 5; parent[5] = 8; parent[8] = 6; parent[6] = 0，则生成树内，顶点和顶点连通，parent[2] = 8; parent[8] = 6; parent[6] = 0，即顶点和顶点连通，所以顶点和顶点连通。

  8. 当 时，此时的边为，此时parent[6] = 0且parent[7] = 0，两者没有连通，故添加到最小生成树中，即parent[6] = 7，此时所有顶点已全部连接，最小生成树构造完成，如下图所示：

  

  克鲁斯卡尔算法对应的代码实现如下所示：

  // 头文件
  #ifndef __EDGESETGRAPH_H__
  #define __EDGESETGRAPH_H__
  #include <iostream>
  
  #define MAX_VEX  100                                      // 最大顶点数
  // 完全无向图边数：(MAX_VEX * (MAX_VEX - 1)) /2
  // 完全有向图边数：MAX_VEX * (MAX_VEX - 1)
  #define MAX_EDGE (MAX_VEX * (MAX_VEX - 1)) >> 1
  
  template<typename E>
  struct EdgeNode {                                         // 边结点元素
      int begin = -1;                                       // 边起始顶点下标
      int end = -1;                                         // 边终点顶点下标
      E weight;                                             // 权值，对于非网图可省略
      EdgeNode& operator=(const EdgeNode& other) noexcept { // 支持赋值操作
          this->begin = other.begin;
          this->end = other.end;
          this->weight = other.weight;
          return *this;
      }
      // 友元函数，支持比较操作（大于）
      friend inline bool operator> (const EdgeNode<E>& lhs, const EdgeNode<E>& rhs) {
          return lhs.weight > rhs.weight;
      }
  };
  
  /*
  * V：表示顶点元素类型
  * E: 表示边权重元素类型
  */
  
  template<typename V, typename E>
  struct EdgesetGraph {                                 // 边集数组
      V vertex[MAX_VEX];                                // 顶点表
      EdgeNode<E> edge[MAX_EDGE];
      int numsVertex = 0, numsEdge = 0;                 // 图中顶点数和边数
  
      void MiniSpanTree_Kruskal(bool isSorted = false); // 克鲁斯卡尔算法
      int findRoot(int parent[], int vertexIndex);      // 找打 vertexIndex 在最小生成树的根顶点
  };
  #endif
  
  
  #include "EdgesetGraph.h"
  
  using namespace std;
  
  // 冒泡排序
  template<typename E>
  void bubbleSort(EdgeNode<E> arr[], const int length) {
      if (arr == nullptr) {
          return;
      }
      for (int i = 0; i < length - 1; ++i) {
          for (int j = 0; j < length - 1 - i; ++j) {
              if (arr[j] > arr[j + 1]) {
                  EdgeNode<E> temp = arr[j];
                  arr[j] = arr[j + 1];
                  arr[j + 1] = temp;
              }
          }
      }
  }
  
  template<typename V, typename E>
  void EdgesetGraph<V, E>::MiniSpanTree_Kruskal(bool isSorted) {
      if (!isSorted) {
          // 排序
          bubbleSort<E>(this->edge, this->numsEdge);
      }
  
      // 最小生成树
      int parent[MAX_VEX];
  
      // 初始化最小生成树数组为0，表示没有顶点
      std::memset(parent, 0, this->numsVertex);
  
      // 遍历每条边
      for (int i = 0; i < this->numsEdge; ++i) {
          EdgeNode<E> edge = this->edge[i];
          // 边(begin,end)，查找顶点begin在最小生成树中的根
          int vBeginRoot = this->findRoot(parent, edge.begin);
          // 边(begin,end)，查找顶点end在最小生成树中的根
          int vEndRoot = this->findRoot(parent, edge.end);
          // 未形成环路
          if (vBeginRoot != vEndRoot) {
              // 将边(vBeginRoot,vEndRoot)添加到最小生成树中
              parent[vBeginRoot] = vEndRoot;
              cout << "添加边：(" << edge.begin << "," << edge.end << ") = " << edge.weight << endl;
          }
      }
  }
  
  template<typename V, typename E>
  int EdgesetGraph<V, E>::findRoot(int parent[], int vertexIndex) {
      // 当前顶点对应最小生成树值不为0，则追钟该顶点的根
      while (parent[vertexIndex] > 0) {
          vertexIndex = parent[vertexIndex];
      }
      // 当 parent[vertexIndex] = 0 时，此时的 vertexIndex 即为参数顶点的根 
      return vertexIndex;
  }
  

  克鲁斯卡尔算法的时间复杂度为 ，其中， 代表图的边数

对比构造最小生成树的两个算法，其中克鲁斯卡尔算法主要是针对边进行展开的，边数少时效率会非常高；而普里姆算法对于稠密图，即边数非常多的情况会更好一些。

• 最短路径：对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点为源点，最后一个顶点为终点。
  注：对于非网图来说，由于其边上没有权值，因此最短路径求的是两顶点之间的边数最少的路径，其实也可以将非网图看作所有边权值都为 1 的网。

  最小生成树与最短路径的区别为：

  • 最小生成树是用最小的代价遍历整个图中所有顶点，即构建一个 条边的树，且路径之和最小。
  • 最短路径是一个点（源点）到另一个点（终点）的路径权值之和最小，它不一定经过所有顶点。

  用于寻找两顶点之间最短路径的经典算法有如下两个：

  • 迪杰斯特拉（Dijkstra）算法：迪杰斯特拉算法的思路是从源点开始，依次寻找中间顶点的最近邻接点，渐渐逼近直到到达终点。

    迪杰斯特拉算法的具体构建过程如下所示：

    1. 首先以源点作为起始点，找寻源点的最近邻接点（假设为），则此时源点与两个顶点构成最短路径。
    2. 以为起始点，找到其最近邻接点（假设为），则此时源点与两个顶点构成最短路径。
    3. 重复上述步骤，直至逼近并找到终点，最短路径构建完成。

    比如，对于下图示例，要求源点到终点之间的最短路径：

    

    对上图采用迪杰斯特拉算法寻找顶点到顶点的最短路径具体过程如下：

    1. 首先从源点开始，寻找它最近距离的邻接点，的邻接点有两个： 和 。
       其中：，，所以源点的最近邻接点为顶点，也即在上图中，顶点和顶点满足最短路径，其值为。如下图所示：
    

    注：首先要明确的是，从任意顶点到任意顶点的最短路径有两种可能：一种是直连，即，另一种是以开始，经过若干其他顶点到达。

    2. 此时我们已经找到最短路径，下面还可以到达的顶点为：、 和 。其中：

       • 我们先求顶点 和 这两个顶点的最短路径：从上图中可以知道， 到 存在两条较近路径： 和 ，所以顶点 和 的最短路径为： -> -> ，总路径为 。

       • 然后再来求此轮顶点 到 的距离，由于我们此轮遍历只知道 和 的最短路径， 和 等其他顶点未涉及，因此这里从 已知顶点 到 只有一条路径：。

       • 再来求顶点 和 ，其路径为：。

    综上，，所以下一个最短路径为：，其值为 。如下图所示：

    
    3. 此时已遍历到顶点，它有两个邻接点 和 ，则：

       • 对于顶点，由目前已知的顶点（即， 和 ），存在两条路径到达，分别为： 和 。

       • 而对于顶点，只存在路径：。

    所以此时的最短路径为：，如下图所示：

    
    4. 此时顶点的邻接点有：，， 和 ，其到下一个顶点的最短路径为：，如下图所示：
    
    5. 依此类推，最终可以得到的结果如下图所示：
    

    迪杰斯特拉算法的代码实现如下所示：
    注：以下代码使用邻接矩阵表示图的结构

    // 头文件
    #ifndef __MGRAPH_H__
    #define __MGRAPH_H__
    
    
    #define MAX_VEX  100                              // 最大顶点数
    #define WEIGHT_INFINITY 65535                     // 无效权值，用 65535 表示正无穷
    
    /*
    * V：表示顶点 Vertext 类型
    * E：表示边权值类型
    */
    template<typename V, typename E>
    struct MGraph {                                   // 邻接矩阵
        V vexs[MAX_VEX];                              // 顶点数组（顶点表）
        E arc[MAX_VEX][MAX_VEX];                      // 邻接矩阵（边表）
        int numsVertex = 0, numsEdge = 0;             // 图中顶点数和边数
    
        void shortestPath_Dijkstra(int sourceVertex); // 迪杰斯特拉算法
    };
    #endif
    
    // 源文件
    #include "MGraph.h"
    #include <iostream>
    
    using namespace std;
    
    template<typename V, typename E>
    void MGraph<V, E>::shortestPath_Dijkstra(int sourceVertex) {
        // 最短路径顶点下标
        int pathVertex[MAX_VEX];
        // 当前顶点到各点的最短路径权值和
        E pathWeight[MAX_VEX];
        // inShortestPath[i] = true，表示 Vi 是最短路径顶点之一
        bool inShortestPath[MAX_VEX];
    
        // 初始化
        for (int i = 0; i < this->numsVertex; ++i) {
            // 全部顶点初始化为非最短路径顶点
            inShortestPath[i] = false;
            // 不含最短路径顶点
            pathVertex[i] = 0;
            // 存储源点到其他各顶点的权值
            pathWeight[i] = this->arc[sourceVertex][i];
        }
    
        // 源点到源点的权值为 0
        pathWeight[sourceVertex] = 0;
        // 将源点添加进最短路径集合
        inShortestPath[sourceVertex] = true;
    
        // 遍历全部顶点（除源点外），总共执行 numsVertex-1 次
        for (int i = 1; i < this->numsVertex; ++i) {
            int min = WEIGHT_INFINITY;
            // 最短邻接点下标
            int adjVex = 0;
            // 寻找源点的最短路径邻接点
            for (int j = 0; j < this->numsVertex; ++j) {
                // 顶点Vj不在最短路径内，则进行比较
                if (!inShortestPath[j] && pathWeight[j] < min) {
                    // 记录最短邻接点下标
                    adjVex = j;
                    min = pathWeight[j];
                }
            }
    
            // 标记找到源点最短邻接点
            inShortestPath[adjVex] = true;
    
            // 将最短邻接点作为新源点，遍历其邻接点，将权值数组更新为当前最短邻接点的权值和
            for (int j = 0; j < this->numsVertex; ++j) {
                // 顶点Vj不属于最短路径，则比较当前最短邻接点和初始源点到顶点Vj的距离
                if (!inShortestPath[j] && (min + this->arc[adjVex][j] < pathWeight[j])) {
                    // 最短邻接点到Vj路径更短，则更新权值数组
                    pathWeight[j] = min + this->arc[adjVex][j];
                    // 将顶点 adjVex 添加到最短路径中
                    pathVertex[j] = adjVex;
                }
            }
        }
        //  return pathVertex;
    }
    

    使用上述代码执行完上述例子后，可以得到：

    • pathWeight = [0, 1, 4, 7, 5, 8, 10, 12, 16]，数组中每个元素的值表示源点到各个顶点的最短路径权值，比如pathWeight[8] = 1 + 3 + 1 + 2 + 3 + 2 + 4 = 16；
    • pathVertex = [0, 0, 1, 4, 2, 4, 3, 6, 7]，该数组元素下标表示顶点下标，值表示当前下标的顶点的最短路径的前驱顶点，比如pathVertex[8] = 7，表示顶点的前驱顶点是，而pathVertex[7] = 6，则表示顶点的前驱顶点为，因此，此时的pathVertex的值即可以表示为最短路径为： <- <- <- <- <- <- <- 。

    最后，迪杰斯特拉算法的时间复杂度为 。

  • 弗洛伊德（Floyd）算法：弗洛伊德算法构建了两个辅助二维数组，分别表示存储任意两顶点间最短路径前驱矩阵的及其最短路径权值，其基本思路是比较任意两顶点间的直接路径（即v_kv_iv_jD[v_i][v_j]P[v_i][v_j]P[v_i][v_j] = kv_iv_jD[v_i][v_j]v_iv_jP[v_i][v_j]$的值就是最短路径所经过的中转顶点。

  弗洛伊德算法的具体构建过程如下所示：

  1. 首先定义两个辅助二维数组：\
     • 最短路径权值矩阵：d[MAX_VEX][MAX_VEX]，d的初始状态其实就是网图的邻接矩阵。我们将d的初始状态记为。
     • 最短路径前驱矩阵：p[MAX_VEX][MAX_VEX]，将p的初始状态设置为终点顶点下标，即p[i][j] = j。我们将p的初始状态记为。
  2. 遍历所有顶点，以当前遍历到的顶点（假设为）作为中转顶点，分别比较图中任意两顶点 和 的直接路径和经过中转顶点路径之和，如果此时中转路径更小，则更新矩阵d和p：d[i][j] = min(d[i][j],d[i][k] + d[k][j])，p[i][j] = k。
  3. 上述一轮比较完毕后，顶点 和 之间的最短路径就找到了。

  仍然以上文迪杰斯特拉算法示例图，介绍下弗洛伊德算法的构建过程：

  1. 首先创建两个辅助二维数组，如下图所示：
  
  2. 遍历所有顶点，首次遍历到的顶点为，则将作为中转顶点，计算图中所有任意两个顶点的直接路径与中转路径之和，并更新二维矩阵d和p。比如：
     • 对于顶点 和 ， 和 的直接路径为：d[1][2] = 3，中转路径为：d[1][0] + d[0][2] = 1 + 5 = 6，由于d[1][2] < d[1]][0] + d[0][2]，直接路径小于中转路径，因此不需要更新矩阵d和p。
     • 此时图中剩余顶点都不邻接当前中转顶点，所以无需进行比较。
       因此此次操作后，以顶点作为中转顶点并未改变任何数据，即矩阵数据不变，但是矩阵状态会由 更新为 ，如下图所示：
  
  3. 继续遍历下一个中转顶点，此时为，也就是所有顶点都经过中转。此时：
     • 对于顶点 和 ，其直接路径为：d[0][2] = 5，中转路径为：d[0][1] + d[1][2] = 1 + 3 = 4，由于中转路径小于直接路径，所以此时需要更新矩阵d和p：d[0][2] = 4，p[0][2] = 1。
     • 对于顶点 和 ，由于 和 不是邻接点，它们没有直接距离，因此，它们的最短路径就是：d[0][3] = d[0][1] + d[1][3] = 1 + 7 = 8，此时p[0][3] = 1。
     • 对于顶点 和 ，同理可得，它们的最短路径为：d[0][4] = d[0][1] + d[1][4] = 1 + 5 = 6，此时p[0][4] = 1。
     • 对于顶点 和 ，同理可得，他们的最短路径为：d[2][3] = d[2][1] + d[1][3] = 3 + 7 = 10，此时`p[2][3] = 1。
     • 对于顶点 和 ，它们是邻接点，因此其直接路径为：d[2][4] = 1，中转路径为：d[2][1] + d[1][4] = 3 + 5 = 8，直接路径小于中转路径，d和p无需更改。
     • 对于顶点 和 ，其直接路径为：d[3][4] = 2，中转路径为：d[3][1] + d[1][4] = 7 + 5 = 12，由于直接路径小于中转路径，d和p无需更改。

  注：上述的分析中，比如顶点 和 ，我们都把它看出是有向图分析，其实示例图是一个无向图，所有这里省略了矩阵对称的代码，即d[0][2] = d[2][0] = 4，p[0][3] = p[3][0] = 1，请知悉。

  到此，图中经过中转顶点的任意两个顶点的最短路径已求出，此时的d和p状态如下图所示：

  
  3. 继续遍历剩余顶点，直到顶点作为中转顶点结束。至此，图的最短路径就已经完成了，最终结果如下图所示：
  

  其实这里可以看到，比如对于顶点 和 的最短路径，就是d[0][8] = 16，矩阵的第行的数值其实与迪杰斯特拉算法求得pathWeight数组数值是一样的，都表示图中各顶点到的最短路径，同理，第二行都表示图中各顶点到顶点的最短路径...
  矩阵可以直到任意两顶点间的最短路径值，而矩阵则可以求出任意两顶点间的具体路径。比如，对于 和 的最短具体路径：由于p[0][8] = 1，所以最短路径经过顶点，继而由p[1][8] = 2，说明顶点和最短路径经过顶点，继而p[2][8] = 4，说明经过顶点，继而p[4][8] = 3，说明经过顶点，继而p[3][8] = 6，说明经过顶点，继而p[6][8] = 7，经过顶点，继而p[7][8] = 8，终于到达顶点了，所以顶点 和 的最短路径具体为： -> -> -> -> -> -> -> 。

  弗洛伊德算法的代码实现如下所示：

  // 头文件
  #ifndef __MGRAPH_H__
  #define __MGRAPH_H__
  
  #include <iostream>
  #include <vector>
  
  
  #define MAX_VEX  100                                             // 最大顶点数
  #define WEIGHT_INFINITY 65535                                    // 无效权值，用 65535 表示正无穷
  
  /*
  * V：表示顶点 Vertext 类型
  * E：表示边权值类型
  */
  template<typename V, typename E>
  struct MGraph {                                                  // 邻接矩阵
      V vexs[MAX_VEX];                                             // 顶点数组（顶点表）
      E arc[MAX_VEX][MAX_VEX];                                     // 邻接矩阵（边表）
      int numsVertex = 0, numsEdge = 0;                            // 图中顶点数和边数
  
      typedef std::vector<std::vector<E>> D;
      typedef std::vector<std::vector<int>> P;
      std::pair<D, P> shortestPath_Floyd();                        // 弗洛伊德算法
      void show_path(D& d, P& p, int sourceVertex, int endVertex); // 弗洛伊德算法 - 显示具体路径
  };
  #endif
  
  // 源文件
  #include "MGraph.h"
  
  using namespace std;
  
  template<typename V, typename E>
  std::pair<typename MGraph<V, E>::D, typename MGraph<V, E>::P> MGraph<V, E>::shortestPath_Floyd() {
      // 最短路径权值矩阵
      D d(this->numsVertex, std::vector<E>(this->numsVertex));
      // 最短路径前驱矩阵
      P p(this->numsVertex, std::vector<int>(this->numsVertex));
  
      // 初始化
      for (int i = 0; i < this->numsVertex; ++i) {
          for (int j = 0; j < this->numsVertex; ++j) {
              d[i][j] = this->arc[i][j];
              p[i][j] = j;
          }
      }
  
      // k 表示中转结点
      for (int k = 0; k < this->numsVertex; ++k) {
          // i 表示源点
          for (int i = 0; i < this->numsVertex; ++i) {
              // j 表示终点
              for (int j = 0; j < this->numsVertex; ++j) {
                  if (d[i][k] != WEIGHT_INFINITY // 非邻接点无需进行比较
                      && d[k][j] != WEIGHT_INFINITY // 非邻接点
                      && d[i][j] > d[i][k] + d[k][j]) {
                      // 将当前两权值设置为更小的一个
                      d[i][j] = d[i][k] + d[k][j];
                      // 经过中转顶点 k
                      p[i][j] = p[i][k];
                  }
              }
          }
      }
      return std::make_pair(d, p);
  }
  
  template<typename V, typename E>
  void MGraph<V, E>::show_path(D& d, P& p, int sourceVertex, int endVertex) {
      cout << "v" << sourceVertex << " - v" << endVertex << ": weight = " << d[sourceVertex][endVertex] << endl;
      // 获得第一个中转顶点
      int k = p[sourceVertex][endVertex];
      // 打印源点
      cout << "path: " << sourceVertex;
      // 中转顶点不是终端顶点
      while (k != endVertex) {
          cout << " -> " << k;
          k = p[k][endVertex];
      }
      // 打印终点
      cout << " -> " << endVertex << endl;
  }
  

  弗洛伊德算法很巧妙，且其代码实现非常优雅和简洁，唯一的缺点应该就是由于代码中使用了三层嵌套循环，使得其时间复杂度为。

  弗洛伊德算法适用于需求所有顶点到所有顶点的最短路径问题。

• 拓扑排序：设图是一个具有个顶点的有向图，中的顶点序列满足若从顶点到顶点有一条路径，则在顶点序列中顶点必在顶点之前。则我们称这样的顶点序列为一个 拓扑序列。而所谓的 拓扑排序，其实就是对一个有向图构造拓扑序列的过程。

  拓扑排序常用于对 AOV 网进行拓扑序列构造。AOV 网 指的是在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称之为 AOV 网（Activity On Vertex Network）。

  AOV 网的一个特性就是不能存在环（回路），因为 AOV 网中的弧代表活动（即顶点）之间存在某种制约关系，后续的活动依赖于前面的活动，所以顶点间不能形成回路。

  也因此，当对网图进行拓扑排序时，可能会产生以下两种构造结果：

  • 如果此网的全部顶点都被输出，则说明它是不存在环（回路）的 AOV 网；
  • 如果输出的顶点数少了，即使只少了一个，也说明这个网存在环（回路），因此它不是 AOV 网。

  前面图的应用中，最小生成树和最短路径可以解决无序问题，即适用于对顶点访问顺序无要求的场景。而对于顶点间存在顺序关系时，则拓扑排序就可派上用场了。比如，对于一个不存在回路的 AOV 网进行拓扑排序，对于各种工程或项目的流程图的分析就很有价值了。

  对 AOV 网进行拓扑排序的基本思路是：从 AOV 网中选择一个入度为 0 的顶点输出，然后删除此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直至输出全部顶点或者 AOV 网中不存在入度为 0 的顶点为止。

  拓扑排序的思路很简单清晰，主要涉及到对图的入度与弧尾进行判断，对这两种信息的获取比较合适的数据结构是 邻接表。对于入度信息，逆邻接表 结构可以很容易进行获取，但是对于删除以顶点为尾的弧，则 邻接表 更简单，因此，理论上，AOV 网进行拓扑排序比较适合的数据结构是 十字链表，但其实，入度只是一个信息，我们可以之间为 邻接表 顶点表添加一个字段in来表示该顶点的入度即可，不必构造虽全面但复杂的 十字链表。

  举个例子，比如对于以下示例中的有向图进行拓扑排序：

  

  其步骤如下所示：

  1. 首先，将上述有向图以邻接表的结构进行表示，如下图所示：
  
  2. 构建完成邻接表后，遍历该邻接表，将入度为0的顶点添加到一个栈中vexsStack（该栈结构只是起存储作用，使用队列或数组等其他结构同样可以），此时的结构如下图所示：
  

  3. 弹出栈顶元素，此时获取一个入度为0的顶点，打印该顶点，并记录输出一个顶点数++count，然后遍历以该顶点为弧尾的顶点（即遍历该顶点的邻接点），将其邻接点入度减1，若此时其邻接点减1后的入度为0，则将该邻接点添加到栈vexsStack中。

  4. 重复步骤3，直至栈清空，此时比较count和图的顶点数，若相等，则说明此图是一个 AOV 网，反之，若count小于图的顶点数，则说明此图存在环（回路），不是一个 AOV 网。

  拓扑排序的代码实现如下所示：

  // 头文件
  #ifndef __GRAPHADJLIST_H__
  #define __GRAPHADJLIST_H__
  
  #define MAX_VEX  100                           // 最大顶点数
  
  template<typename E>
  struct EdgeNode {                              // 边表结点
      int adjvex;                                // 邻接点域，存储邻接点索引
      E weight;                                  // 权值，对于非网图可省略
      struct EdgeNode* next;                     // 下一个邻接点的边表结点
  
      EdgeNode() :adjvex(-1), next(nullptr) {}
  };
  
  template<typename V, typename E>
  struct VertexNode {                            // 顶点表结点
      int  in;                                   // 顶点入度
      V data;                                    // 顶点数据域
      struct EdgeNode<E>* firstedge;             // 第一个邻接点边表结点
  
      VertexNode() :firstedge(nullptr), in(0) {}
  };
  
  template<typename V, typename E>
  struct GraphAdjList {                          // 邻接表
      VertexNode<V, E> vertex[MAX_VEX];          // 顶点表
      int numsVertex = 0, numsEdge = 0;          // 图中顶点数和边数
  
      bool topologicalSort();                    // 拓扑排序
  };
  
  #endif
  
  // 源文件
  #include "GraphAdjList.h"
  #include <iostream>
  #include <stack>
  
  using namespace std;
  
  template<typename V, typename E>
  bool GraphAdjList<V, E>::topologicalSort() {
      // 统计输出顶点数
      int count = 0;
      // 创建一个辅助栈，存储入度为 0 的顶点
      stack<int> vexsStack;
  
      // 遍历顶点表
      for (int i = 0; i < this->numsVertex; ++i) {
          // 将入度为 0 的顶点入栈
          if (this->vertex[i].in == 0) {
              vexsStack.push(i);
          }
      }
  
      // 遍历栈
      while (!vexsStack.empty()) {
          // 弹出栈顶元素
          int top = vexsStack.top();
          vexsStack.pop();
          // 打印栈顶元素
          cout << this->vertex[top].data << " ->";
          // 计数加1
          ++count;
          // 遍历栈顶元素邻接点
          for (EdgeNode<E>* adjvertex = this->vertex[top].firstedge;
              adjvertex != nullptr;
              adjvertex = adjvertex->next) {
              // 当前邻接点顶点索引
              int curAdj = adjvertex->adjvex;
              // 入度减1
              if ((--this->vertex[curAdj].in) == 0) {
                  // 入度为 0 则添加到栈中
                  vexsStack.push(curAdj);
              }
          }
      }
      return count == this->numsVertex;
  }
  

• 关键路径：把路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫 关键路径，在关键路径上的活动叫 关键活动。

  要理解上述 关键路径 的定义，还需要了解以下几个概念：

  • AOE 网（Activity On Edge Network）：在一个表示工程的带权有向图中，用顶点表示事件（事件说明某些活动或某一项活动的完成），用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为 AOE 网。

  • 源点/始点：把 AOE 网中没有入边的顶点称为 始点 或 源点。

  • 汇点/终点：把 AOE 网中没有出边的顶点称为 终点 或 汇点。

  拓扑排序主要是用于解决一个工程能否顺序进行的问题，所以我们只关心活动（顶点）之间是否存在环（回路），而关键路径解决的是工程完成所需要的最短时间问题（即最短工期）。

  举个例子，比如说汽车组装，我们知道，汽车组装需要将各种各样的零部件拼接到一起，各种零部件的生产周期都不相同，比如生产一个轮子需要 0.5 天，生产一个发动机需要 3 天时间，造一个底盘需要 2 天时间，其余部件生产总共使用 2 天时间，将全部零件集中到一起需要 0.5 天，最总组装成车需要 2 天时间。由于汽车组装的各个活动之间是可以同时进行的，比如可以同时在不同的流水线上生产轮子、发动机、底盘等零部件，因此，组装一辆车的最短时间实际是受控于生产周期最长的零部件，以及其余那些无法避免的活动，所以汽车组装的最短时间为：发动机 3 天（生产周期最长）+ 零部件集中 0.5 天（不可避免的活动）+ 组装 2 天（不可避免的活动）= 3 + 0.5 + 2 = 5.5 天。

  像这些完成周期最长的活动（即权值最大的弧）以及不可避免的活动就是关键活动，这些关键活动连接起来的路径称为关键路径。

  AOV 网和 AOE 网都是用来对工程建模的，但 AOV 网的顶点表示活动，更加侧重对活动之间关系的制约描述，而 AOE 网是用边表示活动，边上的权值表示活动持续的时间。AOE 网通常需要建立在 AOV 网的基础上进行研究，因为只有在各活动之间制约关系不存在矛盾的前提下，才能更好地对整个工程进行分析，比如分析工程所需的最短时间或者缩短某些关键活动以减少工程周期...下图是 AOV 网和 AOE 网之间的对比（基于车辆组装工程）：

  

  综上，AOE 网其实就是对工程建模，主要是为了找到工程活动中的关键路径，因为得到了关键路径，就可以知道完成工程的最短时间周期，以及对最短路径上的关键活动进行分析优化，可以起到缩短工程周期等问题...

  应用于实际问题时，只需将工程中的各个活动及其生产周期用网图中的顶点和边权值进行表示，抽象为网图结构即可。比如下图就是用网图对工程的建模：

  工程建模

  注：通常而言，一个工程总是有一个开始，且只有一个结束。因此，对工程建模而成的 AOE 网一般只有一个源点和一个汇点。

  上图中，AOE 网是对实际工程的一个建模表示，其中， 是源点，表示工程开始事件， 是汇点，表示工程完成事件。其余顶点各自表示工程中的各个事件，弧都表示一个活动，用表示，弧的值表示完成活动持续的时间。

  实际上，最短路径求取的是两点之间的最短的那条路径（不必涉及图中所有顶点），而关键路径求的是源点到汇点之间最长的那条路径（该路径涉及到 AOE 网中所有的事件（顶点）），最长的路径代表工程周期最短。

  • 关键路径算法原理：要求取关键路径，就需要求取关键活动，关键活动连接起来的路径就是关键路径。而判断一个活动是否是关键活动的原理为：当该活动的最早开始时间和最晚开始时间相等时（相当于该活动没有空闲时间），就表示当前活动是关键活动。

  所以最终问题转化为对活动的最早开始时间和最晚开始时间的计算。

  这里对上述工程建模网图作为样例，具体描述下活动最早开始时间和最晚开始时间的具体计算过程：

  1. 首先构造对应邻接表表示工程网图，如下图所示：
  
  2. 对上述示例图各活动构造最早开始时间，一个活动的最早开始时间其实就是起始事件的最早时间，比如，对于活动，其最早开始时间是事件开始之时，因为 AOE 网基于 AOV 网，所以事件开始，说明其前面的所有活动已完成，所以的最早时间（最小值）最起码为前面的关键路径之和（即权值最大的路径）。简单来说，最早时间就是对网图构造拓扑序列，然后从源点向汇点顺推获取所有事件的最大路径，其具体过程如下：
     1）由于 是源点，因此其最早开始时间为0。
     2） 和 的最早开始时间分别为3和4。
     3）事件有两条路径： -> -> = a_0 + a_2 = 3 + 5 = 8v_0v_2v_3 = a_1 + a_4 = 4 + 8 = 12v_3v_3a_2a_4v_1v_3a_4v_3v_3v_4v_0v_1v_4 = a_0 + a_3 = 3 + 6 = 9max(v_3) + <v_3,v_4> = max(v_3) + a_6 = 12 + 3 = 15v_4v_5v_0v_2v_5 = a_1 + a_5 = 4 + 7 = 11v_5v_6max(v_4) + <v_4,v_6> = max(v_4) + a_7 = 15 + 9 = 24v_7max(v_4) + <v_4,v_7> = max(v_4) + a_8 = 15 + 4 = 19max(v_5) + <v_5,v_7> = max(v_5) + a_9 = 11 + 6 = 17v_7v_8max(v_7) + <v_7,v_8> = max(v_7) + a_11 = 19 + 5 = 24v_9max(v_6) + <v_6,v_9> = max(v_6) + a_10 = 24 + 2 = 26max(v_8) + <v_8,v_9> = max(v_8) + a_12 = 24 + 3 = 27v_9$ 的最早时间为27。

  综上，我们就得到了网图各个活动的最早时间，假设用变量etv（earliest time of vertext）表示事件的最早时间，则其内容如下表所示：

  事件	最早时间
  	0
  	3
  	4
  	12
  	15
  	11
  	24
  	19
  	24
  	27

  3. 对上述示例图各活动构造最晚开始时间，一个活动的最晚时间其实就是终点事件最晚开始时间。我们借助一个变量ltv（lastest time of vertex）来表示各活动的最晚时间，且将该变量数组中各个值初始化为项目最早完成时间，即ltv[i] = etv[9] = 27。
     事件的最晚开始时间是由汇点往源点进行逆推。比如：
     1）对于事件 ，其最晚开始时间与其最早开始时间一致，为：。
     2）对于事件 ，其最晚开始时间为：。也即如果要确保整个工程在 27 个时间单位内完成，则事件 最晚只能在 24 开始，否则时间会超过 27，造成工期延误。
     3）同理可得，对于事件 ，其最晚开始时间为：。
     4）同理，对于事件 ，其最晚开始时间为：。
     5）同理，对于事件 ，其最晚开始时间为：。
     6）对于事件 ，可以从 和 两个点往前逆推，即：，也即，事件 最晚开始时间为15。
     7）对于事件 ，其最晚开始时间为：。
     8）对于事件 ，它有两个邻接点，所以同样可以从其邻接点 和 进行逆推：。
     9）对于事件 ，同理可得：。
     10）对于事件 ，同理可得：。

  综上，我们就得到了网图各个活动的最晚时间ltv，其内容如下表所示：

  事件	最晚时间
  	0
  	7
  	4
  	12
  	15
  	13
  	25
  	19
  	24
  	27

  4. 到此，只要拼接最早时间表etv和最晚时间表ltv，当事件的最早时间与最晚时间相等时，说明该活动是关键活动。如下表所示：

  事件	最早时间	最晚时间
  	0	0
  	3	7
  	4	4
  	12	12
  	15	15
  	11	13
  	24	25
  	19	19
  	24	24
  	27	27

    从上表可以看出，关键活动的事件有：$v_0, v_2, v_3, v_4, v_7, v_8, v_9$，连接这些关键事件就可以得到关键路径。如下图所示：
  
    ![](https://img.haomeiwen.com/i2222997/2f26a06c58811b32.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
  

  关键路径的代码实现如下所示：

  // 头文件
  #ifndef __GRAPHADJLIST_H__
  #define __GRAPHADJLIST_H__
  
  #include <stack>
  
  #define MAX_VEX  100                                          // 最大顶点数
  
  template<typename E>
  struct EdgeNode {                                             // 边表结点
      int adjvex;                                               // 邻接点域，存储邻接点索引
      E weight;                                                 // 权值，对于非网图可省略
      struct EdgeNode* next;                                    // 下一个邻接点的边表结点
  
      EdgeNode() :adjvex(-1), next(nullptr) {}
  };
  
  template<typename V, typename E>
  struct VertexNode {                                           // 顶点表结点
      int  in;                                                  // 顶点入度
      V data;                                                   // 顶点数据域
      struct EdgeNode<E>* firstedge;                            // 第一个邻接点边表结点
  
      VertexNode() :firstedge(nullptr), in(0) {}
  };
  
  template<typename V, typename E>
  struct GraphAdjList {                                         // 邻接表
      VertexNode<V, E> vertex[MAX_VEX];                         // 顶点表
      int numsVertex = 0, numsEdge = 0;                         // 图中顶点数和边数
  
      bool topologicalSort(int etv[], std::stack<int>& result); // 拓扑排序
      void criticalPath();                                      // 关键路径
  };
  
  #endif
  
  // 源文件
  #include "GraphAdjList.h"
  #include <iostream>
  
  using namespace std;
  
  template<typename V, typename E>
  bool GraphAdjList<V, E>::topologicalSort(int etv[], std::stack<int>& result) {
      int count = 0;
      stack<int> vexsStack;
  
      for (int i = 0; i < this->numsVertex; ++i) {
          if (this->vertex[i].in == 0) {
              vexsStack.push(i);
          }
      }
  
      while (!vexsStack.empty()) {
          int top = vexsStack.top();
          vexsStack.pop();
  
          // 保存拓扑序列
          result.push(top);
  
          ++count;
  
          for (EdgeNode<E>* adjvertex = this->vertex[top].firstedge;
              adjvertex != nullptr;
              adjvertex = adjvertex->next) {
              int curAdj = adjvertex->adjvex;
              if ((--this->vertex[curAdj].in) == 0) {
                  vexsStack.push(curAdj);
              }
              // 保存各顶点最早时间
              if (etv[top] + adjvertex->weight > etv[curAdj]) {
                  etv[curAdj] = etv[top] + adjvertex->weight;
              }
          }
      }
      return count == this->numsVertex;
  }
  
  template<typename V, typename E>
  void GraphAdjList<V, E>::criticalPath() {
      // 最早时间表，初始化为 0
      int* etv = new int[this->numsVertex]{ 0 };
      // 最晚时间表
      int* ltv = new int[this->numsVertex]{ 0 };
      stack<int> topoStack;
  
      // 拓扑排序
      this->topologicalSort(etv, topoStack);
  
      // 初始化 ltv
      for (int i = 0; i < this->numsVertex; ++i) {
          // 最晚时间初始化为最长时间
          ltv[i] = etv[this->numsVertex - 1];
      }
  
      // 遍历拓扑序列
      while (!topoStack.empty()) {
          // 弹出栈顶元素
          int top = topoStack.top();
          topoStack.pop();
  
          // 遍历栈顶元素邻接点
          for (EdgeNode<E>* adjvertex = this->vertex[top].firstedge;
              adjvertex != nullptr;
              adjvertex = adjvertex->next) {
              // 当前邻接点索引
              int curAdj = adjvertex->adjvex;
              // 获取邻接点最晚时间
              if (ltv[curAdj] - adjvertex->weight < ltv[top]) {
                  ltv[top] = ltv[curAdj] - adjvertex->weight;
              }
          }
      }
  
      // 比较 etv 和 ltv，求取关键活动，获得关键路径
      for (int i = 0; i < this->numsVertex; ++i) {
          // 遍历邻接点
          for (EdgeNode<E>* adjvertex = this->vertex[i].firstedge;
              adjvertex != nullptr;
              adjvertex = adjvertex->next) {
              // 当前邻接点
              int curAdj = adjvertex->adjvex;
              // 当前活动最早发生时间
              int ete = etv[i];
              // 当前活动最晚发生时间
              int lte = ltv[curAdj] - adjvertex->weight;
              // 最早时间 == 最晚时间，则为关键活动
              if (ete == lte) {
                  cout << "<" << this->vertex[i].data << ", "
                      << this->vertex[curAdj].data
                      << "> length: " << adjvertex->weight << endl;
              }
          }
      }
      delete[]etv;
      delete[] ltv;
  }
  

参考

• 大话数据结构
• 数据结构与算法概述
• 关键路径算法演示（AOE网）