数据结构——图详解

9、回路或环

如果一条路径上的开始点与结束点为同一个顶点，则称此路为回路或者为环。开始点和结束点相同的简单路径被称为简单回路或者简单环。如果经过图中各边一次且恰好一次的环路，称之为欧拉环路，也就是其长度恰好等于图中边的总数，{ C，A，B，A，D，C，D，B，C}就是一条欧拉环路。如果是经过图中的各顶点一次且恰好一次的环路，其称作哈密尔顿环路，其长度等于构成环路的边数。{C ，A，D，B，C}就是一条哈密尔顿环路。

10、连通、连通图和连通分量

在无向图 G 中，若从顶点 i 到顶点 j 有路径，则称这两个顶点时连通的。如果图 G 中任意两个顶点都连通，则称 G 为连通图，否则称为非连通图。**无向图 G 中的极大连通子图称为 G 的连通分量。对于连通图只有一个极大连通子图，就是它本身（是唯一的）。**非连通图有多个极大连通子图。（非连通图的极大连通子图叫做连通分量，每个分量都是一个连通图）。之所以称为极大是因为如果此时加入一个不在图的点集中的点都会导致它不再连通。

至于极小连通子图，首先只有连通图才有极小连通子图这个概念。就像一个四边形，四个节点四条边，其实三条边就能连通了，所以四个节点三条边，就 OK 了，就是在能连通的前提下，把多余的边去掉。

11、强连通图和强连通分量

在有向图 G 中，若从顶点 i 到顶点 j 有路径，则称从顶点 i 到顶点 j 是连通的。**若图 G 中的任意两个顶点 i 和顶点 j 都连通，即从顶点 i 到顶点 j 和从顶点 j 到顶点 i 都存在路径，则称图 G 是强连通图。**有向图 G 中的极大强连通子图称为 G 的强连通分量。显然，强连通图只有一个强连通分量，即自身，非强连通图有多个强连通分量。

12、稠密图、稀疏图

当一个图接近完全图的时候，称之为疏密图；相反，当一个图含有较少的边数，则称之为稀疏图。

一般对于这个边的个数，说法比较多，通常认为边小于 nlogn（n 是顶点的个数）的图称之为稀疏图，反之称为稠密图。

13、权和网

图中的每一条边都可以附有一个对应的数，这种与边相关的数称为权。权可以表示从一个顶点到 另一个顶点的距离或者花费的代价。边上带有权的图称为带权图，也称之为网。

14、连通图的生成树

所谓连通图的生成树是⼀个极小的连通子图，它含有图中全部的 n 个结点，但是只有构成树的 n - 1 条边。

图的存储结构

在开讲之前，我想让各位想想在存储结构中，我们的顶点怎么存，边怎么存。

**顶点：**因为我们的顶点是一一对应的，故我们选择用数组来进行存储。

**边：**考虑到我们的边是两两节点之间的数据，故我们需要有源点和终点，故我们采用二维数组去对应到源点和终点。

一、邻接矩阵

图的邻接矩阵是用两个数组来表示，一个一位数组存储图中的顶点信息，一个二维数组（我们将 这个数组称之为邻接矩阵）存储图中的边的信息。

无向图邻接矩阵：

我们可以设置两个数组，顶点数组为 vertex[4]={V0, V1, V2, V3}，边数组 arc[4][4] 为对称矩阵 (0 表 示不存在顶点间的边，1 表示顶点间存在边)。

我们可以发现，此时的邻接矩阵是对称的，因为是无向图，故两个顶点当然是相互对应的。

有了这个⼆维数组组成的对称矩阵，我们就可以很容易地知道图中的信息：

判定任意两顶点是否有边无边；

可以轻松知道某个顶点的度，其实就是这个顶点 Vi 在邻接矩阵中第 i 行 (或第 i 列) 的元素之和；

求顶点 Vi 的所有邻接点就是将矩阵中第 i 行元素扫描⼀遍，arc[i][j] 为 1 就是邻接点喽。

有向图邻接矩阵：

我们发现无向图的边构成了⼀个对称矩阵，貌似浪费了⼀半的空间，那如果是有向图来存放，会不会把资 源都利用得很好呢？

可见顶点数组 vertex[4]={V0,V1,V2,V3}，弧数组 arc[4][4] 也是一个矩阵，但因为是有向图，所以这个矩阵并不对称，例如由 V0 到 V3 有弧，得到 arc[0][3]=1，而 V3 到 V0 没有弧，因此 arc[3][0]=0。

另外有向图是有讲究的，要考虑入度和出度，顶点 V1 的入度为 1，正好是第 V1 列的各数之和，顶 点 V1 的出度为 2，正好是第 V1 行的各数之和。

带权图的邻接矩阵：

带权图中的每一条边上带有权值，邻接矩阵中的值则为权值，当两个顶点之间没有弧时，则用无穷大表示。

这里'∞'表示一个计算机允许的、大于所有边上权值的值。

这个时候我们会发现一个问题，就是空间浪费问题。尤其是面对边数相对比较少的稀疏图来说，这种结构无疑是存在对存储空间的极大浪费。

因此我们可以考虑另外一种存储结构方式，例如把数组与链表结合在一起来存储，这种方式在图结构也适用，我们称为邻接表 (Adjacency List)。

二、邻接表

邻接表的处理方法是这样：

图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。

图中每个顶点 Vi 的所有邻接点构成一个线性表，由于邻接点的个数不确定，所以我们选择用单链表来存储。

无向邻接表：

有向邻接表：

若是有向图，邻接表结构也是类似的，我们先来看下把顶点当弧尾建立的邻接表，这样很容易就 可以得到每个顶点的出度：

但也有时为了便于确定顶点的⼊度或以顶点为弧头的弧，我们可以建立一个有向图的逆邻接表：

带权网络的邻接表：

邻接表固然优秀，但也有不足，例如对有向图的处理上，有时候需要再建立一个逆邻接表。

这个时候，我们可以试着想⼀下，我们是否可以把邻接表和逆邻接表结合起来呢？答案显而易见，这个就是⼗字链表。

三、十字链表

其中的 tail 表示该弧的弧尾顶点在顶点数组中的位置，head 表示该弧的弧头顶点在顶点数 组中的位置。tNext 则表示指向弧头相同的下⼀条弧，hNext 则表示指向弧尾相同的下⼀条弧。

注意：对于弧，有箭头的那一边才是弧头，没有的则是弧尾。

十字链表的好处就是因为把邻接表和逆邻接表整合在了一起，这样既容易找到以 Vi 为尾的弧，也 容易找到以 Vi 为头的弧，因而容易求得顶点的出度和入度。

十字链表除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此，在有向 图的应用中，十字链表也是非常好的数据结构模型。

这个时候，还有一个问题，如果使用邻接表存储结构，但是对边的操作比较频繁，怎么办？如 果我们在无向图的应用中，关注的重点是顶点的话，那么邻接表是不错的选择，但如果我们更关注的是边的操作，比如对已经访问过的边做标记，或者删除某一条边等操作，邻接表的确显得不那么 方便了。

四、邻接多重表

邻接表对边的操作显然很不方便，因此，我们可以仿照十字链表的方式，对边表结构进行改装，重新定义的边表结构如下：

其中 iVex 和 jVex 是与某条边依附的两个顶点在顶点表中的下标。iLink 指向依附顶点 iVex 的下一条边，jLink 指向依附顶点 jVex 的下一条边。

五、边集数组

边集数组是由两个一维数组构成，一个是存储顶点的信息，另一个是存储边的信息，这个边数组 每个数据元素由一条边的起点下标 (begin)、终点下标 (end) 和权 (weight) 组成。

图的遍历

一、DFS（深度优先算法）

1、邻接矩阵的 DFS

此处用到了递归，我们的思路主要是，从源点开始，从 0 遍历到最后一个顶点，每次查看当前顶点并对其出度进行遍历，然后用 visit 数组判断出度顶点是否被遍历过了，若没有则递到该顶点，重复上述操作

void DFSGraph(MGraph* graph, int v) {
    visitMGraphNode(&graph->vex[v]);
    MGraphVisited[v] = 1;
    for (int i = 0; i < graph->nodeNum; i++) {
        if (isEdge(graph->edges[v][i]) && MGraphVisited[i] == 0) {
            DFSGraph(graph, i);
        }
    }
}

2、邻接表的 DFS

跟前者逻辑一样，只是介于结构的不同，我们此处会用到 p 去取对于任意顶点的出度，运用递归，直到后面没顶点了再返回再探之前没探完的顶点。

void DFSAGraph(const AGraph* graph, int v) {
    ArcEdge* p;
    graph->visited[v] = 1;
    visitAGraphNode(&graph->nodes[v]);
    p = graph->nodes[v].firstEdge;
    while (p) {
        if (graph->visited[p->no] == 0) {
            DFSAGraph(graph, p->no);
        }
        p = p->next;
    }
}

二、BFS（广度优先算法）

1、邻接矩阵的 BFS

此处我们跟以前的所讲树的 BFS 一样，引入队列来进行广搜，此处的逻辑为，对一个节点的所有出度探完后再进行下一个节点的探查。

void BFSGraph(MGraph* graph, int v) {
    int queue[MaxNodeNum];
    int rear = 0, front = 0;
    int cur;
    rear = (rear + 1) % MaxNodeNum;
    queue[rear] = v;
    MGraphVisited[v] = 1;
    while (front != rear) {
        front = (front + 1) % MaxNodeNum;
        cur = queue[front];
        visitMGraphNode(&graph->vex[cur]);
        for (int i = 0; i < graph->nodeNum; i++) {
            if (isEdge(graph->edges[cur][i]) && !MGraphVisited[i]) // 两点右边且没 vis 过
            {
                rear = (rear + 1) % MaxNodeNum;
                queue[rear] = i;
                MGraphVisited[i] = 1;
            }
        }
    }
}

2、邻接表的 BFS

此处不多讲，原理跟上述一样

void BFSAGraph(const AGraph* graph, int v) {
    int* que = malloc(sizeof(int) * graph->nodeNum);
    int front = 0, rear = 0;
    ArcEdge* p;
    int cur;
    rear = (rear + 1) % graph->nodeNum;
    que[rear] = v;
    graph->visited[v] = 1;
    while (front != rear) {
        front = (front + 1) % graph->nodeNum;
        cur = que[front];
        visitAGraphNode(&graph->nodes[cur]);
        p = graph->nodes[cur].firstEdge;
        while (p) {
            if (graph->visited[p->no] == 0) {
                rear = (rear + 1) % graph->nodeNum;
                que[rear] = p->no;
                graph->visited[p->no] = 1;
            }
            p = p->next;
        }
    }
    free(que);
}

最小生成树

一、Kruskal（克鲁斯卡尔）算法

算法思路： a.将所有的边按权值大小进行升序排序，从小到大依次提取边，满足条件。 b.一旦加入这条边，和之前已经选中的边不能组成环，如果不能，这条边就归入生成树的结果部分。 c.如果能，舍去，再找下一条，直到筛选出 n-1 条边。

此处用到了一种贪心的思想，关于这个算法在后面的最短路径中我们也会用到，其思想是从最值下手。

判断是否会成环我们用的是并查集查看是否一条边的终点和起点的最源点是否为同一个点

void initEdgeSet(MGraph* graph, EdgeSet* edges) // 将邻接矩阵交给 edge 统计
{
    int k = 0;
    for (int i = 0; i < graph->nodeNum; i++) // 遍历每个顶点
    {
        for (int j = i + 1; j < graph->nodeNum; j++) // 遍历上三角
        {
            if (graph->edges[i][j] > 0)
            {
                edges[k].begin = i;
                edges[k].end = j;
                edges[k].w = graph->edges[i][j];
                k++;
            }
        }
    }
}

void sortEdgeSet(EdgeSet* edges, int num) // 排序
{
    EdgeSet tmp;
    for (int i = 0; i < num; i++) // 遍历每个顶点
    {
        for (int j = i + 1; j < num; j++) // 遍历上三角
        {
            if (edges[j].w < edges[i].w)
            {
                memcpy(&tmp, &edges[i], sizeof(EdgeSet));
                memcpy(&edges[i], &edges[j], sizeof(EdgeSet));
                memcpy(&edges[j], &tmp, sizeof(EdgeSet));
            }
        }
    }
}

static int getRoot(const int* uSet, int a)
{
    while (uSet[a] != a)
    {
        a = uSet[a];
    }
    return a;
}

int KruskalMGraph(const EdgeSet* edge, int num, int node_num, EdgeSet* res)
{
    int* uSet;
    int cnt = 0;
    int sum = 0;
    // 1.初始化并查集
    uSet = malloc(sizeof(int) * node_num);
    if (uSet == NULL)
    {
        return -1;
    }
    for (int i = 0; i < node_num; i++)
    {
        uSet[i] = i;
    }
    // 2、从已经排序好的边集中，找到最小的边，且不构成环
    for (int i = 0; i < num; i++)
    {
        int a = getRoot(uSet, edge[i].begin);
        int b = getRoot(uSet, edge[i].end);
        if (a != b)
        {
            // 不构成环
            uSet[a] = b;
            res[cnt].begin = edge[i].begin;
            res[cnt].end = edge[i].end;
            res[cnt].w = edge[i].w;
            sum += edge[i].w;
            cnt++;
            if (cnt == node_num - 1)
            {
                break;
            }
        }
    }
    free(uSet);
    return sum;
}

二、Prim（普里姆）算法

算法思路：

a.动态维护一个所有待激活的顶点数组

b.从图中任选一个顶点，激活它，然后发现新的边（一般来说起始值为 0）

c.找到权值数组里最小的边，激活另外一个顶点

d.更新权值数组，找最小的边，激活另外的顶点

e.直到所有顶点都被激活

int PrimMGraph(const MGraph* graph, int start, EdgeSet* res)
{
    int* cost = malloc(sizeof(int) * graph->nodeNum); // 图中各顶点的权值数组
    int* mark = malloc(sizeof(int) * graph->nodeNum); // 图中顶点激活的状态
    int* visited = malloc(sizeof(int) * graph->nodeNum); // 从哪个顶点开始访问，-1 表示没有被访问
    int sum = 0;
    int mini;
    // 1.更新第一个结点激活的状态
    for (int i = 0; i < graph->nodeNum; i++)
    {
        cost[i] = graph->edges[start][i];
        mark[i] = 0;
        //1.1 更新 visited 数组，是从哪个结点访问的
        if (cost[i] < INF)
        {
            visited[i] = start;
        }
        else
        {
            visited[i] = -1;
        }
    }
    mark[start] = 1;
    int k = 0;
    // 2、动态激活结点，找最小值
    for (int i = 0; i < graph->nodeNum;++i)
    {
        int min = INF;
        k = 0;
        for (int j = 0; j < graph->nodeNum; j++)
        {
            if (mark[j] == 0 && cost[j] < min)
            {
                min = cost[j];
                k = j;
            }
        }
        mark[k] = 1;
        res[i].begin = visited[k];
        res[i].end = k;
        res[i].w = min;
        sum += min;
        // 每激活一个顶点，需要更新 cost 数组
        for (int j = 0; j < graph->nodeNum; j++)
        {
            if (mark[j] == 0 && graph->edges[k][j] < cost[j])
            {
                cost[j] = graph->edges[k][j];
                visited[j] = k;
            }
        }
    }
    free(cost);
    free(mark);
    free(visited);
    return sum;
}

最短路径

一、Dijkstra（迪杰斯特拉）算法

  **Dijkstra 算法是求单源点到其他结点的最短路径的方法，故其他任何节点，都是依赖于源点出发的。**

  这样，肯定是先找源点能到节点的最短路径，在这个基础上，通过确定的最短点再次发散到其他节点，继续找最小，以此类推，直到找完所有点。

  找的过程，记得要标记已经找到过的结点，这样能避免环路出现。

#include "Dijkstra.h"
#include<stdlib.h>
#include<stdio.h>

void DijkstraMGraph(const MGraph* graph, int start, int dist[], int path[])
{
    int* mark; // 节点的访问记录
    mark = malloc(sizeof(int) * graph->nodeNum);
    // 1、激活 start 后，节点距离表 dist 更新、paths 数组的初始化，根节点对应 -1
    for (int i = 0; i < graph->nodeNum; i++)
    {
        dist[i] = graph->edges[start][i];
        mark[i] = 0;
        if (dist[i] < INF)
        {
            path[i] = start;
        }
        else
        {
            path[i] = -1;
        }
    }
    mark[start] = 1;
    path[start] = -1;
    dist[start] = 0;
    // 2、从 dist 里找最小值
    int mini;
    int tmpIndex = 0;
    for (int i = 0; i < graph->nodeNum - 1; i++)
    {
        mini = INF;
        // 从未激活的节点中，找到一个源点的最短路径
        for (int j = 0; j < graph->nodeNum; ++j)
        {
            if (mark[j] == 0 && dist[j] < mini)
            {
                mini = dist[j];
                tmpIndex = j;
            }
        }
        mark[tmpIndex] = 1;
        // 以刚激活的节点，更新源点到其他结点的路径
        for (int j = 0; j < graph->nodeNum; j++)
        {
            if (mark[j] == 0 && dist[tmpIndex] + graph->edges[tmpIndex][j] < dist[j])
            {
                dist[j] = dist[tmpIndex] + graph->edges[tmpIndex][j];
                path[j] = tmpIndex;
            }
        }
    }
    free(mark);
}

// 满递增栈
void showShortPath(int path[], int num, int pos)
{
    int* stack;
    int top = -1;
    stack = malloc(num * sizeof(int));
    if (stack == NULL)
    {
        return;
    }
    // 1、将上一个状态压入栈
    while (path[pos] != -1)
    {
        stack[++top] = pos;
        pos = path[pos];
    }
    stack[++top] = pos;
    //2、弹栈打印 pos 到源点路径
    while (top != -1)
    {
        printf("\t%d", stack[top--]);
    }
    printf("\n");
    free(stack);
}

二、Floyd（弗洛伊德）算法

我们的 Floyd 算法其实是根据于 dp，也就是动态规划思想来写的，也是我们最短路径中最简单的算法，可以计算多源点图中任意两点的最短路径。

  **其本质思想为：两点之间的中转点有可能会使这两个点更短，其实我们 Dijkstra 的本质思想是不是也是这个？**也就是不断的进行一种**松弛（relax）**操作，而我们 Dijkstra 不过是在松弛的基础上又加上了贪心，那么我们就来看看我们的代码吧

#include"MatrixGraph.h"
#include<stdio.h>
#define Max_Size 10

static int dist[Max_Size][Max_Size];
static int path[Max_Size][Max_Size];

void initMatG(MGraph* graph)
{
    char* nodenames[] = { "V0", "V1", "V2", "V3" };
    initMGraph(graph, nodenames, sizeof(nodenames) / sizeof(nodenames[0]), 1, INF);
    for (int i = 0; i < graph->nodeNum; i++)
    {
        graph->edges[i][i] = 0;
    }
    addMGraphEdge(graph, 0, 1, 1);
    addMGraphEdge(graph, 0, 3, 4);
    addMGraphEdge(graph, 1, 2, 9);
    addMGraphEdge(graph, 1, 3, 2);
    addMGraphEdge(graph, 2, 0, 3);
    addMGraphEdge(graph, 2, 1, 5);
    addMGraphEdge(graph, 2, 3, 8);
    addMGraphEdge(graph, 3, 2, 6);
}

void shortPathFloyd(const MGraph* graph)
{
    // 初始化
    for (int i = 0; i < graph->nodeNum; i++)
    {
        for (int j = 0; j < graph->nodeNum; ++j)
        {
            dist[i][j] = graph->edges[i][j];
            if (dist[i][j] < INF && i != j)
            {
                path[i][j] = i;
            }
            else
            {
                path[i][j] = -1;
            }
        }
    }
    // floyd
    for (int k = 0; k < graph->nodeNum; k++)
    {
        for (int i = 0; i < graph->nodeNum; i++)
        {
            for (int j = 0; j < graph->nodeNum; j++)
            {
                if (dist[i][k] < INF && dist[k][j] < INF && dist[i][j] > dist[i][k] + dist[k][j])
                {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = path[k][j];
                }
            }
        }
    }
}

void printPath(int i, int j)
{
    if (i == j)
    {
        printf("%d ", i);
        return;
    }
    int k = path[i][j];
    printPath(i, k);
    printf("%d ", j);
}

int main()
{
    MGraph graph;
    initMatG(&graph);
    shortPathFloyd(&graph);
    for (int i = 0; i < graph.nodeNum; i++)
    {
        for (int j = 0; j < graph.nodeNum; j++)
        {
            printf("%2d ", dist[i][j]);
        }
        printf("\n");
    }
    printf("========================\n");
    for (int i = 0; i < graph.nodeNum; i++)
    {
        for (int j = 0; j < graph.nodeNum; j++)
        {
            printf("%2d ", path[i][j]);
        }
        printf("\n");
    }
    printf("========================\n");
    printPath(1, 0);
    return 0;
}

拓扑排序

一、定义

1、什么是 AOV 网

在一个表示工程的的有向图中，用顶点表示活动，用弧表示活动，用弧表示活动之间的优先关系的有向图均为顶点表示活动的网（Activiy On Vertex Network）简称AOV 网。

在日常生活中，一项大的工程可以看作是由若干个子工程组成的集合，这些子工程之间必定存在一定的先后顺序，即某些子工程必须在其他一些子工程完成后才能开始。

2、什么是拓扑序列

设 G = {V，E} 是一个具有 n 个顶点的有向图，V 中的顶点序列 V1, V2, V3......Vn 满足若从顶点 Vi 到 Vj 有一条路径，则在顶点序列中，顶点 Vi 必须在 Vj 之前，则我们称这样的顶点序列为一个拓扑序列。

3、什么是拓扑排序

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

在拓扑排序中，如果存在一条从顶点 A 到顶点 B 的路径，那么在排序结果中 B 出现在 A 的后面。

二、算法实现

算法思路：

a.在图中选择一个没有前驱的顶点 V。

b.从图中删除顶点 V 和所有以该节点为尾的弧

#include "TopoSort.h"
#include<stdlib.h>
#include<string.h>

int TopologicSortAGraph(AGraph* graph)
{
    int cnt = 0;
    // 定义一个入度记录表，便于发现入度为 0 时，放入缓存区
    int* inDegree;
    inDegree = malloc(sizeof(int) * graph->nodeNum);
    if (inDegree == NULL)
    {
        return -1;
    }
    memset(inDegree, 0, sizeof(int) * graph->nodeNum);
    // 初始化入度记录表
    for (int i = 0; i < graph->nodeNum; i++)
    {
        if (graph->nodes[i].firstEdge)
        {
            // 说明 i 结点开始有边
            ArcEdge* edge = graph->nodes[i].firstEdge;
            while (edge)
            {
                // 此处回顾一下之前的邻接表的边的定义
                // inDegree 记录的是后一个结点的入度情况，那么我们此时就用 edge->no 刚好对应着后续的入度
                ++inDegree[edge->no];
                edge = edge->next;
            }
        }
    }
    // 查找入度记录表，度为 0 的点，设计一个链式栈的缓存区，更新入度记录表时，发现 0 就立刻放入栈
    int* stack = malloc(sizeof(int) * graph->nodeNum);
    if (stack == NULL)
    {
        return -1;
    }
    int top = -1;
    for (int i = 0; i < graph->nodeNum; i++)
    {
        if (inDegree[i] == 0)
        {
            stack[++top] = i;
        }
    }
    // 根据任务栈里的数据，弹出第一个任务，将这个任务对应的节点相关的入边个数删除
    // 更细入度记录表，如果在更新过程中，发现入度为 0，直接入栈
    int index;
    while (top != -1)
    {
        index = stack[top--];
        cnt++;
        visitAGraphNode(&graph->nodes[index]);
        // 更新入度信息
        ArcEdge* edge = graph->nodes[index].firstEdge;
        while (edge)
        {
            --inDegree[edge->no];
            if (inDegree[edge->no] == 0)
            {
                stack[++top] = edge->no;
            }
            edge = edge->next;
        }
    }
    free(inDegree);
    free(stack);
    // 判断是否有环
    if (cnt == graph->nodeNum)
        return 0;
    else
        return 1;
}

关键路径

在开头，我想先讲一下事件与活动的概念：

事件：顶点

活动：边，时间，权值

一、定义

1、什么是 AOE 网

AOE 网（Activity On Edge），即边表示活动的网，是与AOV 网相对应的一个概念。而拓扑排序恰恰就是在AOV 网上进行到，这是拓扑排序与关键路径最直接的一个联系。AOE 网是一个带权的有向无环图，其中顶点表示事件（Event），弧表示活动，权表示活动持续的时间，下面的就是一个AOE 网：

其中 V0，V1，V2.....V8 表示事件，a1, a2......a11 表示活动，活动的取值表示该活动的所需时间，如 a1 = 6 表示完成活动 a1 所需要的时间为 6 天。此外每一事件 Vi 表示在它之前的活动均已完成，在它之后的活动可以开始，如 V4 表示活动 a4 和 a5 已完成，活动 a7 和 a8 可以开始。

2、关键路径

说白了，关键路径（Critical Path）就是路径长度最长的路径，如下图红色顶点和有向边构成的就是一条关键路径

3、什么是 ETV

**ETV（Earliest Time Of Vertex)：**事件最早发生时间，就是顶点的最早发生时间

事件 V2 的最早发生时间表示从源点 V0 出发到达顶点 V2 经过的路径上的权值之和，从源点 V0 出发到达顶点 V2 只经过了权值为 4 的边，则 V2 的最早发生时间为 4，表示在活动 a2 完成之后，事件 V2 才可以 开始；同理，事件 V4 要发生（即最早发生）需要活动 a4 和活动 a5 完成之后才可以，故事件 V4 的最早发生时间为 6 + 1 = 7。其他顶点（事件）的最早发生时间同理可的。需要说明，事件的最早发生时间⼀定是 从源点到该顶点进行计算的

4、什么是 LTV

**LTV（Latest Time Of Vertex)：**事件最晚发生时间，就是每个顶点对应的事件最晚需要开始的时间，如果超出此时间将会延误整个工期。

前面在谈关键路径的概念时给出了一条上图中的关键路径，该关键路径（V0，V1，V4，V6，V8）的长度为 18，为什么要提这个长度呢，因为要计算某⼀个事件的最晚发生时间，我们需要从汇点 V8 进行倒推。计算顶点 V5 的最晚发生时间为例，已知关键路径的长度为 18，事件 V1 到汇点 V8 所需要的时间 为 1 + 9 + 2 = 12，则事件 V1 的最晚发生时间为 18 - 12 = 6，这时候我们发现，这和事件 V1 的最早发生时间不是一样吗？的确如此，对于关键路径上的顶点都满足最早发生时间 ETV 等于 最晚发生时间 LTV 的情况，这也是我们识别关键活动的关键所在。再来计算一下事件 V5 的最晚发生时间，事件 V5 到汇点 V8 所需 要的时间为 4 + 4 = 8，则事件 V5 的最晚发生时间为 18 - 8 = 10；相当于说活动 a6 完成之后，大可以休息 3 天，再去完成活动 a9 也不会影响整个工期。

5、什么是 ETE

**ETE(Earliest Time Of Edge)：**活动的最早开工时间，就是弧的最早发生时间。

活动 a4 要最早开工时间为事件 V1 的最早发生时间 6；同理，活动 a9 的最早开工时间为事件 V5 的最早发生时间 7。显然活动的最早开工时间就是活动发生前的事件的最早开始时间。

6、什么是 LTE

**LTE(Lastest Time of Edge)：**活动的最晚开工时间，就是不推迟工期的最晚开工时间。

活动的最晚开工时间则是基于事件的最晚发生时间。比如活动 a4 的最晚开工时间为事件 V4 的最晚发生时间减去完成活动 a4 所需时间，即 7 - 1 = 6；活动 a9 的最晚开工时间为事件 V7 的最晚发生时间减去完成活动 a9 所需时间，即 14 - 4 = 10；

从上面也就可以看出只要知道了每一个事件（顶点）的 ETV 和 LTV，就可以推断出对应的 ETE 和 LTE。

此外还需要注意，关键路径是活动的集合，而不是事件的集合，所以当我们求得 ETV 和 LTV 之后，还需要计算 ETE 和 LTE。

二、算法实现

算法思路：

a.首先就是计算 ETV，这里的底层实现依旧是拓扑排序，但有一点不同，即关键路径默认只有一个源点。

b.将 ETV 计算完后，将 LTV 的每个结点初始化为 ETV 的最晚结束时间，以便后续做差

c.我们通过 topOut 的记录不断倒序更新 LTV

d.将 LTV 计算完后再计算边的 ETE 和 LTE，并直接输出关键路径

我们发现当计算出 ETV 和 LTV 后，我们的 ETE 和 LTE 的计算将会非常容易。故核心就在于前两个数组。

#include"KeyPath.h"
#include<stdio.h>
#include<stdlib.h>

static int topologicalOrder(const AGraph* graph, int* ETV, int* LTV)
{
    int* inDegree = malloc(sizeof(int) * graph->nodeNum);
    memset(inDegree, 0, sizeof(int) * graph->nodeNum);
    //1、初始化图中所有顶点的入度记录表
    for (int i = 0; i < graph->nodeNum; i++)
    {
        if (graph->nodes[i].firstEdge)
        {
            ArcEdge* edge = graph->nodes[i].firstEdge;
            while (edge)
            {
                ++inDegree[edge->no];
                edge = edge->next;
            }
        }
    }
    // 2、将入度为 0 的节点入栈，出栈的时候
    int top = -1;
    int* stack = malloc(sizeof(int) * graph->nodeNum);
    if (stack == NULL)
    {
        free(inDegree);
        return -1;
    }
    int* topOut = malloc(sizeof(int) * graph->nodeNum);
    if (stack == NULL)
    {
        free(stack);
        free(inDegree);
        return -1;
    }
    // 2.1、将初始化的入度为 0 的顶点编号压入栈，此点就是源点
    for (int i = 0; i < graph->nodeNum; i++)
    {
        if (inDegree[i] == 0)
        {
            stack[++top] = i;
            break; // 关键路径默认只有一个源点
        }
    }
    // 2.2、不断弹栈，不断更新入度记录表
    int tmp = 0; // 从栈上弹出的顶点编号
    int index = 0; // 记录排序结果的情况
    while (top != -1)
    {
        tmp = stack[top--];
        topOut[index++] = tmp;
        ArcEdge* edge = graph->nodes[tmp].firstEdge; // 取节点
        while (edge)
        {
            // 遍历出度
            --inDegree[edge->no];
            if (inDegree[edge->no] == 0)
            {
                // 若删除前一个节点后，后一个节点的入度为 0，那就入栈
                stack[++top] = edge->no;
            }
            // 此处为什么是大于，因为一个节点的前面的入度可能不一样，但因为此时记录的是最早时间，故我们需要等前面所有人都到才能开始行动。
            if (ETV[tmp] + edge->w > ETV[edge->no])
            {
                // 更新 ETV，看该结点的出度结点权值与原结点的 ETV 值相
                ETV[edge->no] = ETV[tmp] + edge->w;
            }
            edge = edge->next;
        }
    }
    free(inDegree);
    free(stack);
    if (index < graph->nodeNum)
    {
        // 有环
        free(topOut);
        return -1;
    }
    tmp = topOut[--index];
    // 3、更新 LTV
    for (int i = 0; i < graph->nodeNum; i++)
    {
        LTV[i] = ETV[tmp];
    }
    while (index)
    {
        int getTopNo = topOut[--index];
        ArcEdge* edge = graph->nodes[getTopNo].firstEdge;
        while (edge)
        {
            // 后一个节点的最早时间减该边的权值，就为该节点的最晚时间
            // 至于为什么是小于，是因为一定要保证前一个结点对于所有出度的情况均满足
            // 比如 0 到 2 的权值为 4，而到 2 的最晚时间却为 6，此时我们就会有 2 小时的闲鱼时间，也就是 0 的最晚开始时间是 2
            // But, 我们 0 到 1 的权值是 6 小时，而到 1 的最晚时间也是 6 小时，此时如果再将 0 从 2 小时开始，那么我们就会发现明显不能满足 1 的最晚时间
            // 故，我们需要考虑到每种情况，所以我们这边是小于。同上，大于也是此理
            if (LTV[edge->no] - edge->w < LTV[getTopNo])
            {
                LTV[getTopNo] = LTV[edge->no] - edge->w;
            }
            edge = edge->next;
        }
    }
    free(topOut);
}

static void showTable(int* table, int n, const char* name)
{
    printf("%s", name);
    for (int i = 0; i < n; i++)
    {
        printf(" %d", table[i]);
    }
    printf("\n");
}

void KeyPath(const AGraph* graph)
{
    // 1、计算顶点的 ETV 和 LTV
    int* ETV = malloc(sizeof(int) * graph->nodeNum);
    int* LTV = malloc(sizeof(int) * graph->nodeNum);
    memset(ETV, 0, sizeof(int) * graph->nodeNum);
    memset(LTV, 0, sizeof(int) * graph->nodeNum);
    topologicalOrder(graph, ETV, LTV);
    showTable(ETV, graph->nodeNum, "ETV: ");
    showTable(LTV, graph->nodeNum, "LTV: ");
    // 2、计算边的 ETE 和 LTE，直接输出关键路径
    for (int i = 0; i < graph->nodeNum; i++)
    {
        ArcEdge* edge = graph->nodes[i].firstEdge;
        while (edge)
        {
            // 每个边最早发生时间就是边的弧尾的 ETV
            // 每个边的最晚发生时间就是边的弧头的 LTV 减去当前的边权值
            if (ETV[i] == LTV[edge->no] - edge->w)
            {
                printf("<%s>---%d---<%s>\n", graph->nodes[i].show, edge->w, graph->nodes[edge->no].show);
            }
            edge = edge->next;
        }
    }
    free(ETV);
    free(LTV);
}