数据结构与算法-关键路径

1. 思路

核心：

• 至少满足拓扑排序。
• 利用最早发生时间数组etv和最晚发生时间数组ltv实现夹逼定理，确定关键路径。

过程：

• 至少满足拓扑排序。

  • 拓扑排序过程中，计算每个顶点的最早发生时间。
    • 所以有前置顶点都完成才能开始，更大的值为最早发生时间。

• 计算顶点最晚发生时间。

  1. 所有顶点都等于最后一个顶点的最早发生时间(因为这个时间是结束时间最大)。

  2. 倒序遍历(拓扑排序时，用栈存储，可直接出栈)。

     • 后面的最晚发生时间减去边的权值和前面的时间进行比较。

     • 最晚发生时间可以提前当然更好，所以取更小的值。

• 利用最早发生时间数组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);
            }
        }
    }
}