采用邻接表存储，实现关键路径算法具体c语言代码

关路径算法是求解工程项目中的关键活动的方法，其实现需要采用拓扑排序和动态规划的思想。以下是使用邻接表存储的关键路径算法具体C语言代码：

#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 100 // 最大顶点数
#define INFINITY 65535 // 无穷大表示

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

typedef struct VertexNode { // 顶点表结点
    int in; // 顶点入度
    int data; // 顶点域，存储顶点信息
    int earliest; // 事件最早发生时间
    int latest; // 事件最迟发生时间
    EdgeNode *firstedge; // 边表头指针
} VertexNode, AdjList[MAXVEX];

typedef struct { // 图结构
    AdjList adjList;
    int numVertexes, numEdges; // 图中当前的顶点数和边数
} GraphAdjList;

int TopologicalSort(GraphAdjList *graph) { // 拓扑排序
    int i, k, count, top = 0;
    int stack[MAXVEX]; // 存储入度为0的顶点
    EdgeNode *e;
    count = 0;
    for (i = 0; i < graph->numVertexes; i++) {
        if (graph->adjList[i].in == 0) { // 将入度为0的顶点入栈
            stack[++top] = i;
        }
    }
    while (top != 0) {
        k = stack[top--]; // 出栈
        printf("%d -> ", graph->adjList[k].data); // 输出拓扑序列
        count++; // 统计输出顶点数
        for (e = graph->adjList[k].firstedge; e; e = e->next) {
            if (--graph->adjList[e->adjvex].in == 0) { // 将入度为0的顶点入栈
                stack[++top] = e->adjvex;
            }
            if (graph->adjList[k].earliest + e->weight > graph->adjList[e->adjvex].earliest) {
                graph->adjList[e->adjvex].earliest = graph->adjList[k].earliest + e->weight; // 更新最早发生时间
            }
        }
    }
    if (count < graph->numVertexes) { // 图中存在环
        return 0;
    } else {
        return 1;
    }
}

void CriticalPath(GraphAdjList *graph) { // 关键路径算法
    int i, k, e, len;
    EdgeNode *p;
    TopologicalSort(graph);
    for (i = 0; i < graph->numVertexes; i++) { // 初始化事件最迟发生时间
        graph->adjList[i].latest = graph->adjList[graph->numVertexes - 1].earliest; // 最后一个事件的最早发生时间即为最终完成时间
    }
    for (k = 0; k < graph->numVertexes; k++) { // 按拓扑序列逆序计算事件最迟发生时间
        i = graph->adjList[k].data;
        for (p = graph->adjList[k].firstedge; p; p = p->next) {
            e = p->adjvex;
            if (graph->adjList[e].latest - p->weight < graph->adjList[i].latest) {
                graph->adjList[i].latest = graph->adjList[e].latest - p->weight; // 更新最迟发生时间
            }
        }
    }
    printf("\n关键路径为: ");
    for (k = 0; k < graph->numVertexes; k++) { // 求关键路径
        for (p = graph->adjList[k].firstedge; p; p = p->next) {
            i = graph->adjList[k].data;
            e = p->adjvex;
            len = p->weight;
            if (graph->adjList[i].earliest + len == graph->adjList[e].earliest && graph->adjList[e].latest - len == graph->adjList[i].latest) {
                printf("%d -> %d -> ", graph->adjList[i].data, graph->adjList[e].data); // 输出关键路径
            }
        }
    }
    printf("\n");
}

int main() {
    GraphAdjList graph;
    int i, j, k, weight;
    EdgeNode *e;
    printf("请输入图中顶点数和边数: ");
    scanf("%d %d", &graph.numVertexes, &graph.numEdges);
    getchar();
    printf("请输入图中各顶点信息: ");
    for (i = 0; i < graph.numVertexes; i++) {
        scanf("%d", &graph.adjList[i].data);
        graph.adjList[i].in = 0;
        graph.adjList[i].firstedge = NULL;
    }
    printf("请输入图中各边的起点和终点及权值: \n");
    for (k = 0; k < graph.numEdges; k++) {
        scanf("%d %d %d", &i, &j, &weight);
        e = (EdgeNode*)malloc(sizeof(EdgeNode));
        e->adjvex = j;
        e->weight = weight;
        e->next = graph.adjList[i].firstedge;
        graph.adjList[i].firstedge = e;
        graph.adjList[j].in++;
    }
    for (i = 0; i < graph.numVertexes; i++) { // 初始化事件最早发生时间
        graph.adjList[i].earliest = 0;
    }
    CriticalPath(&graph);
    return 0;
}