1. 思路
核心：
- 至少满足拓扑排序。
- 利用最早发生时间数组etv和最晚发生时间数组ltv实现夹逼定理，确定关键路径。
过程：
-
至少满足拓扑排序。
- 拓扑排序过程中，计算每个顶点的最早发生时间。
- 所以有前置顶点都完成才能开始，更大的值为最早发生时间。
- 拓扑排序过程中，计算每个顶点的最早发生时间。
-
计算顶点最晚发生时间。
-
所有顶点都等于最后一个顶点的最早发生时间(因为这个时间是结束时间最大)。
-
倒序遍历(拓扑排序时，用栈存储，可直接出栈)。
-
后面的最晚发生时间减去边的权值和前面的时间进行比较。
-
最晚发生时间可以提前当然更好，所以取更小的值。
-
-
-
利用最早发生时间数组etv和最晚发生时间数组ltv实现夹逼定理，没有额外时间的都是关键活动。
- 只看路径的话实现比较简单，两个数组中值相等，说明没有多余时间，进行输出。
- 如果需要输出权值，前一个顶点的最早发生时间加上边的权值后，若等于后一个顶点的最晚发生时间，说明中间没有多余时间，则是关键路径，进行输出。
2. 基础数据结构
#define MAXVEX 30
//边表结点
typedef struct EdgeNode {
//邻接点域，存储该顶点对应的下标
int adjvex;
//用于存储权值，对于非网图可以不需要
int weight;
//链域，指向下一个邻接点
struct EdgeNode *next;
} EdgeNode;
//顶点表结点
typedef struct VertexNode {
//顶点入度
int in;
//顶点域，存储顶点信息
int data;
//边表头指针
EdgeNode *firstedge;
}VertexNode, AdjList[MAXVEX];
typedef struct {
AdjList adjList;
//图中当前顶点数和边数
int numVertices,numEdges;
} graphAdjList, *GraphAdjList;
3. 实现
int *etv, *ltv; /* 事件最早发生时间和最迟发生时间数组，全局变量 */
int *stack2; /* 用于存储拓扑序列的栈 */
int top2; /* 用于stack2的指针*/
//拓扑排序
Status TopologicalSort(GraphAdjList GL) {
// 创建一个栈
int top = -1;
int *stack = (int *)malloc(GL->numVertices * sizeof(int));
// 先把所有入度为0的顶点入栈
for(int i = 0; i < GL->numVertices; i++)
if(GL->adjList[i].in == 0)
stack[++top] = i;
EdgeNode *edge; // 辅助遍历边
int idx; // 顶点的索引
int count = 0; // 统计遍历顶点的个数，所有顶点都被访问过，拓扑排序才正确
// 初始化拓扑序列栈
top2 = -1;
stack2 = (int *)malloc(sizeof(int) * GL->numVertices);
// 事件最早发生时间数组，并初始化
etv = (int *)calloc(GL->numVertices, sizeof(int));
printf("TopologicSort:\n");
int adjvex;
while (top > -1) {
// 出栈顶点并打印
idx = stack[top--];
printf(" -> %d", GL->adjList[idx].data);
count++;
// 将出栈的顶点序号压入拓扑排序的栈中
stack2[++top2] = idx;
edge = GL->adjList[idx].firstedge; // 获取边表头结点
while (edge) {
adjvex = edge->adjvex; // 获取顶点索引
if (--GL->adjList[adjvex].in == 0) { // 入度-1，同时如果结果==0，则入栈
stack[++top] = adjvex;
}
/*
idx→adjvex
idx的最早发生时间 + 边的权值 > adjvex的最早发生时间
则最早开始的时间需要更新
*/
if ((etv[idx] + edge->weight) > etv[adjvex]) {
etv[adjvex] = etv[idx] + edge->weight;
}
edge = edge->next; // 继续遍历
}
}
printf("\n");
if (count != GL->numVertices) { // 顶点都被访问过，拓扑排序才正确
return ERROR;
}
return OK;
}
//求关键路径，GL为有向网，则输出G的各项关键活动
void CriticalPath(GraphAdjList GL) {
//求得拓扑序列,计算etv数组以及stack2的值
TopologicalSort(GL);
//打印etv数组(事件最早发生时间)
printf("etv:\n");
for(int i = 0; i < GL->numVertices; i++)
printf("etv[%d] = %d \n",i,etv[i]);
printf("\n");
// 事件最晚发生时间数组
ltv = (int *)malloc(sizeof(int) * GL->numVertices);
// 初始化ltv数组，赋值etv最后一个事件的值(都最晚发生)
for (int i = 0; i < GL->numVertices; i++) {
ltv[i] = etv[GL->numVertices - 1];
}
EdgeNode *edge;
// 计算ltv(事件最晚发生时间)
// 拓扑排序结果从后往前进行更新
while (top2 > -1) {
int idx = stack2[top2--]; // 出栈顶点索引
// 遍历出栈顶点的边表
for (edge = GL->adjList[idx].firstedge; edge; edge = edge->next) {
int adjvex = edge->adjvex; // 相连的顶点索引
/*
idx→adjvex
反过来计算，adjvex最晚发生时间减去边的权值 < idx最晚发生时间
即最晚时间可以提早，则更新idx最晚发生时间
*/
if (ltv[idx] > ltv[adjvex] - edge->weight) {
ltv[idx] = ltv[adjvex] - edge->weight;
}
}
}
// 打印ltv数组
printf("ltv:\n");
for (int i = 0 ; i < GL->numVertices; i++)
printf("ltv[%d] = %d \n",i,ltv[i]);
// 只看路径，夹逼定理
printf("关键路径:\n");
for (int i = 0 ; i < GL->numVertices; i++)
if (etv[i] == ltv[i])
printf(" -> %d", i);
printf("\n");
// 打印权值
printf("关键路径和权值:\n");
for (int i = 0; i < GL->numVertices; i++) {
for (edge = GL->adjList[i].firstedge; edge; edge = edge->next) {
int adjvex = edge->adjvex; // i→adjvex
// i最早发生时间 + 到adjvex的时间 == adjvex最晚开工的时间
// i最早和adjvex最晚，出去必要时间，没有额外时间，即关键路径
if (etv[i] + edge->weight == ltv[adjvex]) {
printf("<%d-%d> weight: %d\n",GL->adjList[i].data, GL->adjList[adjvex].data, edge->weight);
}
}
}
}
网友评论