要先会拓扑排序最早时间就是 将点的入度变为0后 才能解锁继续往下进行 类似于西游记孙悟空3天到西天 而唐僧要3年 那工程最短为3年最晚时间是在最终不影响最早时间下算出来的 看最多可以偷懒几天但最后又不影响进度在拓扑排序上进行的 多了逆拓扑排序把最晚时间算出来如果 最早时间 最晚时间就为关键路径 偷懒要谨慎了下面为C语言代码#include stdio.h#include stdlib.h#define INF 10001// ---------- 链式栈 ----------// 用于拓扑排序的栈结点typedef struct stackNode {int data; // 存储顶点下标struct stackNode* next;} SNode, *Stack;// 初始化栈带头结点Stack InitStack() {Stack s (SNode*)malloc(sizeof(SNode));s-next NULL;return s;}// 入栈头插法Stack Push(Stack s, int k) {Stack p (SNode*)malloc(sizeof(SNode));p-data k;p-next s-next;s-next p;return s;}// 判断栈是否为空int IsEmpty(Stack s) {if (s-next NULL)return 1; // 空return 0; // 非空}// 取栈顶元素不弹出int GetTop(Stack s) {if (!IsEmpty(s))return s-next-data;elsereturn -1; // 空栈返回-1}// 弹出栈顶元素Stack Pop(Stack s) {if (!IsEmpty(s)) {SNode* p s-next;s-next p-next;free(p);p NULL;}return s;}// ---------- 图的相关定义 ----------// n个顶点m条边的DAG图顶点数100int n, m;// 边结点邻接表typedef struct ENode {int adj; // 邻接点下标int w; // 边的权值struct ENode* next;} ENode;// 顶点结构体存储顶点字符和第一条边指针struct {char d; // 顶点名称如 A,B,C...ENode* first; // 指向第一条边} g[105];int ind[105]; // 入度数组int topo[105]; // 拓扑序列数组int k; // topo数组的当前下标从1开始int etv[105]; // 事件顶点的最早发生时间int ltv[105]; // 事件顶点的最迟发生时间// 辅助函数取较大值int max(int a, int b) {return a b ? a : b;}// 辅助函数取较小值int min(int a, int b) {return a b ? a : b;}// 根据顶点字符查找对应的顶点下标1~nint find(char x) {int i;for (i 1; i n; i) {if (g[i].d x)break;}return i;}// 拓扑排序同时计算每个顶点的最早发生时间 etvvoid TopoSort() {// etv 全局变量默认为0无需额外初始化Stack s InitStack(); // 初始化栈存放入度为0的顶点// 将所有入度为0的顶点入栈for (int i 1; i n; i) {if (ind[i] 0) {s Push(s, i);}}int u, v;ENode* p NULL;// 依次弹出栈顶顶点生成拓扑序列for (int i 1; i n; i) {u GetTop(s); // 取栈顶顶点s Pop(s); // 弹出topo[k] u; // 保存到拓扑序列数组// 遍历顶点 u 的所有邻接边p g[u].first;while (p ! NULL) {v p-adj; // 邻接点 vind[v]--; // 入度减1if (ind[v] 0) // 若入度变为0则入栈s Push(s, v);// 更新 v 的最早发生时间// etv[v] max(etv[v], etv[u] 边权)etv[v] max(etv[v], etv[u] p-w);p p-next;}}}// 关键路径算法void CriticalPath() {// 汇点最后一个顶点的下标int ed topo[k];// 初始化所有顶点的最迟发生时间为汇点的最早发生时间for (int i 1; i n; i) {ltv[i] etv[ed];}ENode* p NULL;int i, j;// 按拓扑序列的逆序计算每个顶点的最迟发生时间for (int q k - 1; q 1; q--) { // 跳过汇点汇点已初始化为etv[ed]i topo[q]; // 当前顶点 ip g[i].first; // 遍历 i 的所有出边while (p ! NULL) {j p-adj; // 邻接点 j// ltv[i] min(ltv[i], ltv[j] - 边权)ltv[i] min(ltv[i], ltv[j] - p-w);p p-next;}}// 遍历所有边判断是否为关键活动int ete, lte; // 活动边的最早开始时间和最迟开始时间for (i 1; i n; i) { // 遍历每个顶点for (p g[i].first; p ! NULL; p p-next) {j p-adj; // 边 i - jete etv[i]; // 活动的最早开始时间 顶点 i 的最早发生时间lte ltv[j] - p-w; // 活动的最迟开始时间 顶点 j 的最迟发生时间 - 边权if (ete lte) { // 若相等则为关键活动printf(%c %c\n, g[i].d, g[j].d);}}}}int main() {// 输入顶点数和边数scanf(%d %d, n, m);getchar(); // 吸收换行符// 输入 n 个顶点的字符标识for (int i 1; i n; i) {scanf(%c, g[i].d);g[i].first NULL; // 初始化邻接表头指针}char x, y;int w;int xi, yi;// 输入 m 条边起点 终点 权值for (int i 1; i m; i) {getchar(); // 吸收上一行残留的换行符scanf(%c %c %d, x, y, w);xi find(x); // 起点下标yi find(y); // 终点下标// 创建边结点头插法加入邻接表ENode* e (ENode*)malloc(sizeof(ENode));e-adj yi;e-w w;e-next g[xi].first;g[xi].first e;// 统计入度ind[yi];}// 1. 拓扑排序计算 etv 和 topo 序列TopoSort();// 2. 计算关键路径并输出关键活动CriticalPath();return 0;}/*测试用例9 11ABCDEFGHYA B 6A C 4A D 5B E 1C E 1D F 2E G 9E H 7F H 4G Y 2H Y 4*/
