关键路径算法详解（C语言从零实现项目关键路径分析）

算法原理简述

关键路径算法基于拓扑排序（Topological Sorting）和动态规划思想，主要步骤如下：

1. 对有向无环图（DAG）进行拓扑排序；
2. 计算每个事件（节点）的最早发生时间（ve）；
3. 从终点反向计算每个事件的最迟发生时间（vl）；
4. 对每条边（活动）计算：
   - 最早开始时间 = 起点 ve
   - 最迟开始时间 = 终点 vl - 活动持续时间
   若两者相等，则该活动在关键路径上。

C语言实现步骤

我们使用邻接表存储图，并借助队列实现拓扑排序。

1. 定义数据结构

// 边结构体typedef struct ArcNode {    int adjvex;          // 目标顶点编号    int weight;          // 活动持续时间    struct ArcNode* next;} ArcNode;// 顶点结构体typedef struct VNode {    char data;           // 顶点名称（如A、B）    ArcNode* firstarc;   // 第一条出边} VNode, AdjList[100];// 图结构体typedef struct {    AdjList vertices;    int vexnum, arcnum;  // 顶点数、边数} ALGraph;

2. 拓扑排序函数

int TopologicalOrder(ALGraph G, int* topo, int* ve) {    int indegree[100] = {0};    int stack[100], top = -1;        // 计算入度    for (int i = 0; i < G.vexnum; i++) {        ArcNode* p = G.vertices[i].firstarc;        while (p) {            indegree[p->adjvex]++;            p = p->next;        }    }        // 入度为0的入栈    for (int i = 0; i < G.vexnum; i++) {        if (indegree[i] == 0) {            stack[++top] = i;        }    }        int count = 0;    while (top != -1) {        int j = stack[top--];        topo[count++] = j;                ArcNode* p = G.vertices[j].firstarc;        while (p) {            int k = p->adjvex;            if (--indegree[k] == 0) {                stack[++top] = k;            }            // 更新最早发生时间            if (ve[j] + p->weight > ve[k]) {                ve[k] = ve[j] + p->weight;            }            p = p->next;        }    }        return (count == G.vexnum); // 是否有环}

3. 关键路径主函数

void CriticalPath(ALGraph G) {    int topo[100], ve[100] = {0}, vl[100];        if (!TopologicalOrder(G, topo, ve)) {        printf("图中存在环，无法计算关键路径！\n");        return;    }        // 初始化最迟发生时间    int max_time = 0;    for (int i = 0; i < G.vexnum; i++) {        if (ve[i] > max_time) max_time = ve[i];    }    for (int i = 0; i < G.vexnum; i++) vl[i] = max_time;        // 反向更新最迟发生时间    for (int i = G.vexnum - 1; i >= 0; i--) {        int j = topo[i];        ArcNode* p = G.vertices[j].firstarc;        while (p) {            int k = p->adjvex;            if (vl[k] - p->weight < vl[j]) {                vl[j] = vl[k] - p->weight;            }            p = p->next;        }    }        // 输出关键活动    printf("关键路径上的活动：\n");    for (int j = 0; j < G.vexnum; j++) {        ArcNode* p = G.vertices[j].firstarc;        while (p) {            int k = p->adjvex;            int e = ve[j];          // 最早开始时间            int l = vl[k] - p->weight; // 最迟开始时间            if (e == l) {                printf("%c -> %c (持续时间: %d)\n",                        G.vertices[j].data, G.vertices[k].data, p->weight);            }            p = p->next;        }    }}

实际应用场景

项目管理是关键路径算法最常见的应用领域。例如软件开发、建筑工程、产品发布等复杂项目，都可以通过构建任务依赖图，利用关键路径算法找出瓶颈任务，从而优化资源分配、缩短工期。

总结

通过本文，你已经掌握了关键路径算法的核心思想及其在C语言实现中的具体步骤。记住，关键路径依赖于拓扑排序，且只适用于有向无环图。在实际工程中，结合甘特图等工具，能更直观地进行项目管理。

提示：完整代码可自行补充图的创建与输入部分。建议先手动绘制一个小例子（如5个任务），再用程序验证结果是否正确。