数据结构总目录

关键路径

在图结构中，源点到终点的所有路径中，其中具有最大路径长度的路径称为关键路径。

1. 图文解析

（1） 事件Vk的最早发生时间：指顶点活动从源点V1到终点Vk的最长路径长度；
如下图中，顶点D活动的最早发生时间为2+4=6，之所以称之为最早，是因为即便A->B->D很快，但是也必须等到C完成后D才能开始活动

事件Vk的最早发生时间计算过程：

1. 通过拓扑排序的顺序依次遍历顶点得到Vk，通过顶点Vk获取所有后继顶点
2. 比较【顶点Vk的最早发生时间 + 边大小】和【后继顶点的最早发生时间】两者大小
3. 选择最大值作为后继顶点的最早发生时间

例如：顶点C，后继顶点为D、F，【C最早发生时间 (2) + 边大小(4)】>【D的最早发生时间(5)】 ，则D的最早发生时间 = 2 + 4 = 6

（2） 事件Vk的最迟发生时间：指Vk在整个过程（源点到终点的最大时长）的前提下，保证后继事件能够发生的最迟时间
如下图中，源点A到终点F的最长时长 = 8，在此基础下，顶点活动E的最迟发生时间 = 7
如果E的最迟发生时间一旦超过7，则路径中通过【顶点活动E最迟发生时间(>7) + 边大小(1)】就会比原来的【关键路径长度(8)】花的时间更久，也就相当于活动E会拖慢整个工程的进度。

事件Vk的最早发生时间计算过程：

1. 通过逆拓扑排序的顺序依次遍历顶点得到Vk，通过顶点Vk获取所有后继顶点
2. 比较【后继顶点的最迟发生时间 - 边大小】和【顶点Vk的最迟发生时间】两者大小
3. 选择最小值作为顶点Vk的最迟发生时间

例如：顶点C，后继顶点为D、F，【F最迟发生时间 (8) - 边大小(3)】= 5，【D最迟发生时间 (6) - 边大小(4)】= 2，则C的最迟发生时间 = min（5，2） = 2；

（3）【最迟发生时间】 - 【最早发生时间】 = 0 的活动构成关键路径

2. 源代码

#include<stdio.h>
#include<stdlib.h>
#define MaxVex 20

typedef int EdgeType;
typedef char VertexType;

// 边结点结构（链表）
typedef struct EdgeNode
{
    int adjvex;         // 该边邻接的结点下标
    EdgeType edgeData;  // 该边结点的数据（权值）
    struct EdgeNode *next;
}EdgeNode, *EdgeList;

// 顶点结点结构（顺序表）
typedef struct
{
    VertexType vextexData;  // 顶点数据
    EdgeList edgeList;      // 顶点的边链表 
    int indegree;           // 顶点的入度
    EdgeType earliest;      // 该顶点活动的最早发生时间
    EdgeType latest;        // 该顶点活动的最迟发生时间
}VertexNode, *VertexList;

// 邻接表结构
typedef struct
{
    VertexList vertexList; // 顶点顺序表
    int numVertexs, numEdges;     // 顶点数
}ALGraph;

// 初始化邻接表
void InitALGraph(ALGraph *G)
{

    G->numVertexs = 0;
    G->numEdges = 0;
    G->vertexList = (VertexNode *)malloc(MaxVex * sizeof(VertexNode));
    
    // 初始化边链表头结点，和顶点入度
    int i;
    for (i = 0; i < MaxVex; i++)
    {
        G->vertexList[i].edgeList = (EdgeNode *)malloc(sizeof(EdgeNode));
        G->vertexList[i].edgeList->next = NULL;
        G->vertexList[i].indegree = 0;
        G->vertexList[i].earliest = 0;
        G->vertexList[i].latest = 0;
    }
    printf("已初始化邻接表\n\n");
}

// 创建邻接表
void CreateALGraph(ALGraph *G)
{
    printf("请输入顶点数和边数:");
    scanf("%d %d", &G->numVertexs, &G->numEdges);
    
    int i, j, k;
    EdgeType w;
    // 输入顶点数据
    for (i = 0; i < G->numVertexs; i++)
    {
        fflush(stdin);
        printf("请输入第%d个顶点数据:", i + 1);
        scanf("%c", &G->vertexList[i].vextexData);
    }
    // 输入边的权值
    for (k = 0; k < G->numEdges; k++)
    {
        printf("请输入边(vi, vj)上的顶点序号及权值:");
        scanf("%d %d %d", &i, &j, &w);

        EdgeNode *p1;
        p1 = (EdgeNode *)malloc(sizeof(EdgeNode));

        // 链表头插法 插入 顶点（vi -> vj）的边
        p1->edgeData = w;
        p1->next = G->vertexList[i - 1].edgeList->next;
        G->vertexList[i - 1].edgeList->next = p1;
        p1->adjvex = j - 1;                 // 该边邻接着顶点j
        G->vertexList[j - 1].indegree++;    // 邻接顶点j的入度加一
    }
    printf("已创建邻接表!\n\n");
}

// 拓扑排序
void KeyPath(ALGraph G)
{ 
    // 用一个数组来代表一个栈结构，top1为栈顶指针
    int top1 = 0, Stack[MaxVex];

    // 用于存储逆序拓扑排序的逆序栈
    int top2 = 0, RStack[MaxVex];

    // 初始化
    int i, indegree[MaxVex];
    for (i = 0; i < G.numVertexs; i++)
    {
        // 获取每个顶点的入度
        indegree[i] = G.vertexList[i].indegree;
        // 初始化栈，将入度为0的顶点入栈
        if (indegree[i] == 0)
        {
            Stack[top1++] = i;
        }
    }

    // 通过拓扑排序计算顶点活动的最早发生时间
    int v;
    EdgeNode *p;
    printf("拓扑排序:");
    while (top1 > 0)
    {
        // 将入度为0的顶点出栈
        i = Stack[--top1];
        // 入栈到逆序栈中
        RStack[top2++] = i;
        printf("%c--->", G.vertexList[i].vextexData);
        // 遍历该顶点所有的后继顶点
        for (p = G.vertexList[i].edgeList->next; p ; p = p->next)
        {
            v = p->adjvex;
            // 将后继顶点的入度减一
            indegree[v]--;
            // 如果后继顶点入度为零，则入栈
            if (!indegree[v])
            {
                Stack[top1++] = v;
            }
            // 更新所有后继顶点活动的最早发生时间
            if (G.vertexList[i].earliest + p->edgeData > G.vertexList[v].earliest)
            {
                G.vertexList[v].earliest = G.vertexList[i].earliest + p->edgeData;
            }
        }
    }   
    printf("\n");

    if (top2 < G.numVertexs)
    {
        printf("排序失败!存在回路\n");
    }
    else
    {
        // 初始化顶点活动的最迟发生时间
        v = RStack[--top2];
        for (i = 0; i < G.numVertexs; i++)
        {
            G.vertexList[i].latest = G.vertexList[v].earliest;
        }
        
        // 根据逆序栈更新顶点活动的最迟发生时间
        while (top2 > 0)
        {
            // 逆序依次获取顶点
            i = RStack[--top2];
            for (p = G.vertexList[i].edgeList->next; p ; p = p->next)
            {
                // 邻接的后继顶点
                v = p->adjvex;
                // 更新顶点活动的最迟发生时间
                if (G.vertexList[v].latest - p->edgeData < G.vertexList[i].latest)
                {
                    G.vertexList[i].latest = G.vertexList[v].latest - p->edgeData;
                }
            }
        }
    }    
}

void Display(ALGraph G)
{
    int i;
    printf("顶点\t");
    for (i = 0; i < G.numVertexs; i++)
    {
        printf("%c\t", G.vertexList[i].vextexData);
    }
    printf("\n最早\t");
    for (i = 0; i < G.numVertexs; i++)
    {
        printf("%d\t", G.vertexList[i].earliest);
    }
    printf("\n最迟\t");
    for (i = 0; i < G.numVertexs; i++)
    {
        printf("%d\t", G.vertexList[i].latest);
    }
    printf("\n关键路径:");
    for (i = 0; i < G.numVertexs; i++)
    {
        if (G.vertexList[i].latest - G.vertexList[i].earliest == 0)
        {
            printf("%C--->", G.vertexList[i].vextexData);
        }
    }
    printf("\n");
}

int main()
{
    ALGraph G;
    InitALGraph(&G);
    CreateALGraph(&G);
    KeyPath(G);
    Display(G);
    system("pause");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211

3. 测试结果

#测试用例
6 8
A
B
C
D
E
F
1 2 3
1 3 2
2 4 2
2 5 3
3 4 4
3 6 3
4 6 2
5 6 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16