数据结构与算法-图篇（C语言版）

图

邻接矩阵

一个一维数组存放顶点，一个二维数组存放边，以无向图为例

#include <stdio.h>
#include <malloc.h>

typedef char VertexType; // 顶点类型用户可自定义
typedef int EdgeType; // 边上的权值类型用户可自定义
# define MAXVEX 100 // 最大顶点数，可自定义
# define INFINITY 65535 // 用65535表示无穷
// 图的邻接矩阵结构
typedef struct {
    VertexType vex[MAXVEX]; // 一维数组存放顶点集
    EdgeType arc[MAXVEX][MAXVEX]; // 二维数组存放边，邻接矩阵
    int numNodes, numEdges; // 图中当前顶点数和边数
}MGraph;

void createMGraph(MGraph *G) {
    int i, j, k, w;
    printf("输入顶点数和边数：\n");
    scanf("%d,%d", &G->numNodes, &G->numEdges); 
    // 初始化顶点，建立顶点表
    for (i = 0; i < G->numNodes; i++) {
        scanf(&G->vex[i]);
    }
    // 邻接矩阵初始化
    for (i = 0; i < G->numNodes; i++) {
        for(j = 0; j < G->numNodes; j++) {
            // 默认所有均为无穷值
            G->arc[i][j] = INFINITY;
        }
    }
    // 读取边数，建立边表
    for (k = 0; k < G->numEdges; k++) {
        printf("输入边（vi, vj）上的下标i，下标j，和权w\n");
        scanf("%d,%d,%d", &i, &j, &w);
        // 无向图对称
        G->arc[i][j] = w;
        G->arc[j][i] = w;
    }
}

邻接表

一个一维数组存储顶点，再利用一个单链表存储对应的邻接点，同样以无向图为例

typedef char VertexType; // 顶点类型用户可自定义
typedef int EdgeType; // 边上的权值类型用户可自定义

// 边表结点
typedef struct EdgeNode{
    // 邻接点域，存储该顶点对应的下标
    int adjvex;
    // 用于存储权值，对于非网图可不需要
    EdgeType info;
    // 链域，指向下一个邻接点
    struct EdgeNode *next;
}EdgeNode;

// 顶点表结点
typedef struct VertexNode {
    // 顶点域，存储顶点信息
    VertexType data;
    // 边表头指针
    EdgeNode *firstEdge;
}VertexNode, AdjList[MAXVEX];

// 图的邻接表结构
typedef struct {
    AdjList adjList;
    // 当前顶点数和边数
    int numNodes, numEdges;
}GraphAdjList;

void createGraphAdjList(GraphAdjList *G) {
    int i,j,k;
    EdgeNode *e;
    printf("输入顶点数和边数：\n");
    scanf("%d,%d", &G->numNodes, &G->numEdges);
    // 读取顶点信息，建立顶点表
    for (i = 0; i < G->numNodes; i++) {
        // 顶点信息输入
        scanf(&G->adjList[i].data);
        // 边表初始化置为空
        G->adjList[i].firstEdge = NULL;
    }
    // 建立边表
    for (k = 0; k < G->numEdges; k++) {
        printf("输入边（vi,vj）上的顶点序号：\n");
        scanf("%d,%d", &i,&j);
        // 申请内存空间，生成边结点
        e = (EdgeNode *)malloc(sizeof (EdgeNode));
        // 邻接点序号信息
        e->adjvex = j;
        // 将新建结点的指针指向当前顶点指向的结点（类似头插法）
        e->next = G->adjList[i].firstEdge;
        // 将当前顶点指向新建的结点
        G->adjList[i].firstEdge = e;
        // 因为是无向图，所以一条边对应的是两个顶点，故操作与上述基本类似
        e = (EdgeNode *)malloc(sizeof (EdgeNode));
        e->adjvex = i;
        e->next = G->adjList[j].firstEdge;
        G->adjList[j].firstEdge = e;
    }
}

图的遍历

为避免某些结点被访问多次或无人问津，故设置访问数组visited[n]，初始值为0，访问过后设置为1

深度优先遍历

有点类似于树的前序遍历

• 邻接矩阵

  #include <stdio.h>
  #include <malloc.h>
  #include <mqoai.h>
  
  typedef char VertexType; // 顶点类型用户可自定义
  typedef int EdgeType; // 边上的权值类型用户可自定义
  # define MAXVEX 9 // 最大顶点数，可自定义
  # define INFINITY 65535 // 用65535表示无穷
  Boolean visited[MAXVEX]; // 访问标志的数组
  
  // 邻接矩阵的定义
  typedef struct Vertex{
      VertexType vex[MAXVEX];
      EdgeType arc[MAXVEX][MAXVEX];
      int numNodes, numEdges;
  }MGragh;
  
  void DFS(MGragh G, int i) {
      int j;
      visited[i] = TRUE; // 访问过的设置为 TRUE
      printf("%c", G.vex[i]); // 打印出来，表示访问到了
      for(j = 0; j < G.numNodes; j++) {
          // 对未访问过的邻接点递归调用
          if(G.arc[i][j] == 1 && !visited[i]) {
              DFS(G, i);
          }
      }
  }
  
  // 深度遍历
  void DFSTraverse(MGragh G) {
      int i;
      // 初始化访问数组，默认均为FALSE，即未被访问过
      for (i = 0; i < G.numNodes; i++) {
          visited[i] = FALSE;
      }
      // 未访问过的顶点就调用DFS，若为连通图仅执行一次
      for(i = 0; i < G.numNodes; i++) {
          if(!visited[i]) {
              DFS(G, i);
          }
      }
  }

• 邻接表

  #include <stdio.h>
  #include <malloc.h>
  #include <mqoai.h>
  
  typedef char VertexType; // 顶点类型用户可自定义
  typedef int EdgeType; // 边上的权值类型用户可自定义
  #define MAXVEX 9
  
  Boolean visited[MAXVEX];
  
  typedef struct EdgeNode {
      int adjVex;
      EdgeType info;
      struct EdgeNode *next;
  }EdgeNode;
  
  typedef struct VertexNode{
      VertexType data;
      struct EdgeNode *firstEdge;
  }VertexNode, AdjList[MAXVEX];
  
  typedef struct {
      AdjList adjList;
      int numNodes, numEdges;
  }GraphAdjList;
  
  void DFS(GraphAdjList GL, int i) {
      // 用于遍历边表结点的指针
      EdgeNode *p;
      visited[i] = TRUE;
      printf("%c", GL.adjList[i].data);
      // p指向当前顶点指向的下一个结点
      p = GL.adjList[i].firstEdge;
      while (p) {
          // 对未被访问过的结点递归调用
          if(!visited[p->adjVex]) {
              DFS(GL, p->adjVex);
          }
          // 访问过的就沿边表往后走
          p = p->next;
      }
  }
  
  void DFSTraverse(GraphAdjList GL) {
      int i;
      for (i = 0; i < GL.numNodes; i++) {
          visited[i] = FALSE;
      }
      for (i = 0; i < GL.numNodes ; i++) {
          if(!visited[i]) {
              DFS(GL, i);
          }
      }
  }

广度优先遍历

有点类似树的层序遍历，利用到辅助队列

• 邻接矩阵

  #include "stdio.h"
  #include <mqoai.h>
  
  typedef char VertexType;
  typedef int EdgeType;
  
  #define MAXVEX 9
  
  Boolean visited[MAXVEX];
  
  typedef struct VerTex{
      VertexType vertex[MAXVEX];
      EdgeType arc[MAXVEX][MAXVEX];
      int numVexs, numEdges;
  }MGraph;
  
  // 队列的结构（顺序表和链表的实现不一样，可查看之前线性结构部分）
  typedef struct Queue{}*Queue;
  
  void initQueue(Queue *Q){}
  void EnQueue(Queue *Q, int i){}
  void DeQueue(Queue *Q, int i){}
  Boolean QueueEmpty(Queue *Q){}
  
  void BFSTraverse(MGraph G){
      int i, j;
      Queue Q;
      for (i = 0; i < G.numVexs; i++) {
          visited[i] = FALSE;
      }
      // 初始化辅助队列
      initQueue(&Q);
      for (i = 0; i < G.numVexs; i++) {
          // 未被访问过的先访问后入队
          if(!visited[i]) {
              visited[i] = TRUE;
              printf("%c", G.vertex[i]);
              EnQueue(&Q, i);
              // 队列非空则出队，然后寻找出队结点的邻接点
              while (!QueueEmpty(&Q)) {
                  DeQueue(&Q, i);
                  // 邻接点边存在且未被访问过，则也访问后入队（必须判断边存在，若只判断visited数组可能会判断错误）
                  for (j = 0; j < G.numVexs; j++) {
                      if(G.arc[i][j] == 1 && !visited[j]) {
                          visited[j] = TRUE;
                          printf("%c", G.vertex[j]);
                          EnQueue(&Q, j);
                      }
                  }
              }
          }
      }
  }

• 邻接表

  // 队列的结构（顺序表和链表的实现不一样，可查看之前线性结构部分）
  typedef struct Queue{}*Queue;
  
  void initQueue(Queue *Q){}
  void EnQueue(Queue *Q, int i){}
  void DeQueue(Queue *Q, int i){}
  Boolean QueueEmpty(Queue *Q){}
  
  void BFSTraverse(GraphAdjList GL) {
      int i;
      EdgeNode *p;
      Queue Q;
      for(i  = 0; i < GL.numNodes; i++) {
          visited[i] = FALSE;
      }
      // 初始化辅助队列
      initQueue(&Q);
      for(i = 0; i < GL.numNodes; i++) {
          // 访问结点
          visited[i] = TRUE;
          printf("%c", GL.adjList[i].data);
          // 访问过后的就入队
          EnQueue(&Q, i);
          // 当队列非空时，就出队
          while (!QueueEmpty(&Q)) {
              DeQueue(&Q, i);
              // 寻找出队节点的邻接节点
              p = GL.adjList[i].firstEdge;
              // 当邻接点未被访问过就访问后入队
              while (p) {
                  if(!visited[p->adjVex]) {
                      visited[p->adjVex] =  TRUE;
                      printf("%c", GL.adjList[p->adjVex].data);
                      EnQueue(&Q, p->adjVex);
                  }
                  p = p->next;
              }
          }
      }
  }

最小生成树

构成连通网的最小代价生成树成为最小生成树

普利姆（Prim）算法

从顶点触发，挑选两个顶点之间权值最小的边

#include "stdio.h"

typedef char VerTexType;
typedef int EdgeType;
#define MAXVEX 9
#define INFINITY 65535

typedef struct VerTex{
    VerTexType vex[MAXVEX];
    EdgeType arc[MAXVEX][MAXVEX];
    int numNodes, numEdges;
}MGraph;

void MiniSpanTree_Prim(MGraph G) {
    int min, i, j, k;
    // 保存相关顶点间边的权值点下标
    int adjvex[MAXVEX];
    // 保存相关顶点边的权值
    int lowcost[MAXVEX];
    // 此处初始化权值为0，即从v0开始
    lowcost[0] = 0;
    // v0顶点下标为0
    adjvex[0] = 0;

    //循环除下标0之外的所有顶点，即v1,v2...
    for(i = 1; i < G.numNodes; i++) {
        // 所有与v0相关的边的权值存入数组
        lowcost[i] = G.arc[0][i];
        // 初始化为全都是v0的下标
        adjvex[i] = 0;
    }
    // 最小生成树操作
    for (i = 1; i < G.numNodes; i++) {
        // 初始化最小权值为65535
        min = INFINITY;
        // 顶点下标循环变量
        j = 1;
        // 存储最小权值的顶点下标
        k = 0;
        // 循环全部顶点
        while (j < G.numNodes) {
            // 权值不为0且权值小于min，则当前的就是最小权值，赋给min（类似寻找最小值操作）
            if(lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                // 存储最小权值的顶点下标
                k = j;
            }
            j++;
        }
        // 打印当前顶点边中权值最小的边
        printf("(%d,%d)\n", adjvex[k], k);
        // 将当前顶点的权值更改为0，表示此顶点已加入最小生成树，该顶点的任务完成
        lowcost[k] = 0;
        // 循环所有顶点
        for (j = 1; j < G.numNodes; j++) {
            // 若下标为k的顶点各边权值小于此前这些未被加入生成树的顶点的权值
            if(lowcost[j] != 0 && G.arc[k][j] < lowcost[j]) {
                // 将较小的权值存入lowcost对应的下标位置
                lowcost[j] = G.arc[k][j];
                // 将下标为k的顶点存入adjvex
                adjvex[j] = k;
            }
        }
    }
}

克鲁斯卡尔（Kruskal）算法

从边出发，从上帝视觉挑选边权值最小的组成最小生成树，注意不要成环

#include "stdio.h"

#define MAXVEX 9
#define MAXEDGE 15

typedef char VerTexType;
typedef int EdgeType;

typedef struct VerTex{
    VerTexType vex[MAXVEX];
    EdgeType arc[MAXVEX][MAXVEX];
    int numNodes, numEdges;
}MGraph;

// 对边集数组Edge结构的定义
typedef struct {
    int begin;
    int end;
    int weight;
}Edge;

// 查找连线顶点的尾部下标
int Find(int *parent, int f) {
    while (parent[f] > 0) {
        f = parent[f];
    }
    return f;
}

void MiniSpanTree_Kruskal(MGraph G) {
    int i,n,m;
    // 定义边集数组，edge的结构为begin，end和weight
    Edge edges[MAXEDGE];
    // 用于判断边与边是否形成了环路（此处太妙了）
    int parent[MAXVEX];

    // 此处省略将邻接矩阵G转化为边集数组Edges并按权由小到大排序的代码（形成的边表如上图）

    // 初始化数组值为0
    for(i = 0; i < G.numNodes; i++) {
        parent[i] = 0;
    }
    // 循环每一条边
    for(i = 0; i < G.numEdges; i++) {
        n = Find(parent, edges[i].begin);
        m = Find(parent, edges[i].end);
        // 若n!=m说明此此边没有与现有的生成树形成环路
        if(n != m) {
            // 将此边的结尾顶点放入以起点为下标的parent中，表示此顶点已经在生成树的集合中
            parent[n] = m;
            printf("(%d,%d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
        }
    }
}

最短路径

迪杰斯塔拉（Dijkstra）算法

一步步求出顶点之间的最短路径，每一步都是基于前面已求出的最短路径基础上进行的，最终求得最远顶点的最短路径（以下算法只能实现无孤立点的图）

#include "stdio.h"

#define MAXVEX 20
#define MAXEDGE 20
#define INFINITY 65535

typedef struct {
    int vexs[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numNodes, numEdges;
}MGraph;

// 用于存储最短路径下标的数组
typedef int Patharc[MAXVEX];
// 用于存储到各点最短路径的权值和
typedef int ShortPathTable[MAXVEX];

// P[v]的值为前驱顶点v的下标，D[v]表示v0到v的最短路径权值和
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D) {
    int v,w,k,min;
    // final数组的作用类似最小生成树中的lowcost，当值为0时表示顶点还没加入最短路径，当值为1时表明顶点已经加入最短路径
    int final[MAXVEX];
    // 初始化数据
    for(v=0;v<G.numNodes;v++) {
        // 默认都未加入最短路径
        final[v] = 0;
        // 从顶点v0开始，将与v0有连线的顶点权值存入数组
        (*D)[v] = G.arc[v0][v];
        // 默认全为-1，即目前还没有路径
        (*P)[v] = -1;
    }
    // 从v0开始，故v0到v0自身权值为0
    (*D)[v0] = 0;
    // v0默认加入最短路径
    final[v0] = 1;
    // 开始求最短路径，每次求得v0到某个顶点v的最短路径
    for (v = 1; v < G.numNodes; v++) {
        min = INFINITY;
        // 寻找离v0顶点最近的顶点
        for(w = 0; w < G.numNodes; w++) {
            // 未加入最短路径且其离v0最近（即权值最小），就交换并记录
            if(!final[w] && (*D)[w] < min) {
                k = w;
                min = (*D)[w];
            }
        }
        // 找到后加入最短路径
        final[k] = 1;
        // 从找到的顶点再次出发，继续寻找权值和最小的顶点
        for (w = 0; w < G.numNodes; w++) {
            // 未加入最短路径且从上面已加入最短路径的顶点再出发，找权值和最小的顶点
            if(!final[w] && min + G.arc[k][w] < (*D)[w]) {
                // 若有更小的，更新数组里的权值
                (*D)[w] = min + G.arc[k][w];
                // 记录顶点vw的前驱顶点的下标k
                (*P)[w] = k;
            }
        }
    }
}

弗洛伊德（Floyd）算法

所有顶点到所有顶点的最短路径

#include "stdio.h"

#define MAXVEX 20
#define MAXEDGE 20
#define INFINITY 65535

typedef struct {
    int vexs[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numNodes, numEdges;
}MGraph;

// 用于存储最短路径下标的数组
typedef int Patharc[MAXVEX][MAXVEX];
// 用于存储到各点最短路径的权值和
typedef int ShortPathTable[MAXVEX][MAXVEX];

// Floyd算法，求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]
void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D) {
    int v, w, k;
    // 初始化
    for(v = 0; v < G.numNodes; v++) {
        // 将邻接矩阵中的权值赋给D数组，初始化P数组
        for (w = 0; w < G.numNodes; w++) {
            (*D)[v][w] = G.arc[v][w];
            (*P)[v][w] = w;
        }
    }
    // 核心算法，k代表的是中转顶点的下标, v为起始顶点, w为终止顶点
    for (k = 0; k < G.numNodes; k++) {
        for (v = 0; v < G.numNodes; v++) {
            for(w = 0; w < G.numNodes; w++) {
                // 若通过中转顶点k到达的路径长度要比直接到达的要小，则将当前的权值设置为更小的一个
                if((*D)[v][w] > (*D)[v][k] + (*D)[k][w]) {
                    (*D)[v][w] = (*D)[v][k] + (*D)[k][w];
                    // 路径设置为经过下标为k的顶点
                    (*P)[v][w] = (*P)[v][k];
                }
            }
        }
    }
}

通过P数组得出最短路径（此段代码还没有弄懂…）：

printf("各顶点间最短路径如下：\n");
    for (v = 0; v < G.numNodes; v++) {
        for(w = v+1; w < G.numNodes; w++) {
            printf("v%d-v%d  weight:%d", v, w, (*D)[v][w]);
            // 获得第一个路径顶点下标
            k = (*P)[v][w];
            // 打印源点
            printf("path:%d", v);
            // 若路径顶点下标不是终点
            while (k!=w) {
                // 打印路径顶点
                printf("-> %d", k);
                // 获得下一个路径顶点下标
                k = (*P)[k][w];
            }
            // 打印终点
            printf("%d\n", w);
        }
        printf("\n");
    }

拓扑排序

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网

若有满足从顶点vi到顶点vj有一条路径，则在顶点序列中顶点vi必在vj之前，我们称这样的顶点序列为一个拓扑序列

所谓的拓扑排序，其实就是对一个有向图构造拓扑序列的过程

基本思路：从AOV网中选择一个入度为0的顶点输出，然后删去此顶点及以此顶点为尾的弧，重复上述步骤直至输出全部顶点或AOV网中不再存在入度为0的顶点

利用栈进行操作：

//
// Created by zhou on 2023/6/4.
// 拓扑排序

#include "stdio.h"
#include "stdlib.h"

#define MAXVEX 20
#define ERROR 0
#define OK 1

// 边表节点
typedef struct EdgeNode{
    // 邻接点域，存储该顶点对应的下标
    int adjvex;
    // 权值
    int weight;
    // 链域，指向下一个邻接点
    struct EdgeNode *next;
}EdgeNode;

// 顶点表结点
typedef struct VertexNode{
    // 入度
    int in;
    // 顶点信息
    int data;
    // 边表头指针
    struct EdgeNode *firstEdge;
}VertexNode, AdjList[MAXVEX];

typedef struct {
    AdjList adjList;
    int numNodes, numEdges;
}graphAdjList, *GraphAdjList;

/**
 * 拓扑排序
 * @param GL 邻接表
 * @return 若GL无回路，返回1，否则返回0
 */
int TopologicalSort(GraphAdjList GL) {
    // 用于遍历邻接表的指针
    EdgeNode *e;
    int i,k,gettop;
    // 栈指针域下标
    int top = 0;
    // 统计输出的顶点个数
    int count = 0;
    // 建栈用于将入度为0的顶点入栈
    int *stack;
    // 分配栈空间
    stack = (int*)malloc(GL->numNodes * sizeof (int));
    // 遍历所有顶点，将顶点入度为0的入栈
    for(i = 0; i < GL->numNodes; i++) {
        if(0 == GL->adjList[i].in) {
            stack[++top] = i;
        }
    }
    // 当栈指针下标不为0时，代表栈中有顶点
    while (top != 0) {
        // 栈顶的顶点出栈
        gettop = stack[top--];
        printf("%d->", GL->adjList[gettop].data);
        // 记录下出栈的顶点数
        count++;
        // 遍历此顶点的所有邻接点
        for (e = GL->adjList[gettop].firstEdge; e; e = e->next) {
            // 将这些邻接点的入度减1（实际上就是断掉边）
            k = e->adjvex;
            // 若入度减少后刚好为0，则再将该顶点入栈
            if(!(--GL->adjList[k].in)) {
                stack[++top] = k;
            }
        }
    }
    // 输出顶点数与总顶点数不一致，说明有环
    if(count < GL->numNodes) return ERROR;
    else return OK;
}

关键路径

在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这样的有向图边表示活动的网，我们称为AOE网

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

相关术语：

• 事件最早发生时间etv
• 事件最晚发生时间ltv
• 活动最早开工时间ete
• 活动最晚开工时间lte

技巧：

• 对顶点事件：从前往后取较大，从后往前取较小
• 对弧活动：早头(头顶点的最早发生时间)晚尾(晚尾减权值)

//
// Created by zhou on 2023/6/6.
// 关键路径
#include "stdlib.h"
#include "stdio.h"


#define MAXVEX 20
#define ERROR 0
#define OK 1

// 边表节点
typedef struct EdgeNode{
    // 邻接点域，存储该顶点对应的下标
    int adjvex;
    // 权值
    int weight;
    // 链域，指向下一个邻接点
    struct EdgeNode *next;
}EdgeNode;

// 顶点表结点
typedef struct VertexNode{
    // 入度
    int in;
    // 顶点信息
    int data;
    // 边表头指针
    struct EdgeNode *firstEdge;
}VertexNode, AdjList[MAXVEX];

typedef struct {
    AdjList adjList;
    int numNodes, numEdges;
}graphAdjList, *GraphAdjList;

// 顶点事件最早和最晚发生时间数组
int *etv, *ltv;
// 拓扑序列栈
int *stack2;
// 遍历拓扑序列栈指针
int top2;

int TopologicalSort(GraphAdjList GL) {
    // 用于遍历邻接表的指针
    EdgeNode *e;
    int i,k,gettop;
    // 栈指针域下标
    int top = 0;
    // 统计输出的顶点个数
    int count = 0;
    // 建栈用于将入度为0的顶点入栈
    int *stack;
    // 分配栈空间
    stack = (int *)malloc(GL->numNodes * sizeof (int));
    // 遍历所有顶点，将顶点入度为0的入栈
    for(i = 0; i < GL->numNodes; i++) {
        if(0 == GL->adjList[i].in) {
            stack[++top] = i;
        }
    }
    // 初始化
    top2 = 0;
    etv = (int *) malloc(GL->numNodes * sizeof(int));
    for(i = 0; i < GL->numNodes; i++) {
        etv[i] = 0;
    }
    stack2 = (int*)malloc(GL->numNodes * sizeof (int));
    // 出栈
    while (top != 0) {
        gettop = stack[top--];
        count++;
        // 拓扑序列入栈
        stack2[top2++] = gettop;
        // 遍历此顶点的所有邻接点
        for (e = GL->adjList[gettop].firstEdge; e; e = e->next) {
            // 将这些邻接点的入度减1（实际上就是断掉边）
            k = e->adjvex;
            // 若入度减少后刚好为0，则再将该顶点入栈
            if(!(--GL->adjList[k].in)) {
                stack[++top] = k;
            }
            // 从前往后找较大值
            if((etv[gettop] + e->weight) > etv[k]) {
                etv[k] = etv[gettop] + e->weight;
            }
        }
    }
    // 输出顶点数与总顶点数不一致，说明有环
    if(count < GL->numNodes) return ERROR;
    else return OK;
}

/**
 * 求关键路径
 * @param GL
 */
void CriticalPath(GraphAdjList GL) {
    EdgeNode *e;
    int i, gettop, k, j;
    // 边活动的最早和最迟发生时间
    int ete, lte;
    // 利用拓扑序列求出数组etv和拓扑排序后的栈
    TopologicalSort(GL);
    // 初始化，分配内存给顶点事件最迟发生时间数组
    ltv = (int*)malloc(GL->numNodes * sizeof (int));
    for(i = 0; i < GL->numNodes; i++) {
        // 初始化，最迟事件发生时间数组初始默认值均为最早事件发生时间数组中的最后一个值
        ltv[i] = etv[GL->numNodes - 1];
    }
    while (top2 != 0) {
        gettop = stack2[top2--];
        for (e = GL->adjList[gettop].firstEdge; e; e = e->next) {
            k = e->adjvex;
            // 求各顶点事件最晚发生时间ltv（从后往前找较小值）
            if(ltv[k] - e->weight < ltv[gettop]) {
                ltv[gettop] = ltv[k] - e->weight;
            }
        }
    }
    // 求 ete,lte,和关键路径
    for(j = 0; j < GL->numNodes; j++) {
        k = e->adjvex;
        // 活动最早发生时间 = 弧头顶点的最早事件发生时间
        ete = etv[j];
        // 活动最迟发生时间 = 弧尾顶点的最迟事件发生时间 - 边上的权值
        lte = ltv[k] - e->weight;
        // 若两者相等则在关键路径上
        if(ete == lte) {
            printf("<v%d - v%d> length: %d\n",
                   GL->adjList[j].data, GL->adjList[k].data, e->weight);
        }
    }
}