C语言实现关键路径算法：优化装修项目进度

"根据给定的任务和先期需完成工作，可以将该项目的活动及其依赖关系表示为一个有向无环图（DAG）。每个节点表示一个活动，边表示活动之间的依赖关系。根据这个图，可以使用拓扑排序算法来确定关键路径和最迟开始时间。\n\n以下是一个用C语言实现的代码示例：\n\nc\n#include <stdio.h>\n#include <stdlib.h>\n\n#define MAX_ACTIVITIES 9\n\ntypedef struct Node {\n int activity;\n int duration;\n int earliestStartTime;\n int latestStartTime;\n int numDependencies;\n struct Node** dependencies;\n} Node;\n\nvoid initializeGraph(Node* graph) {\n // 初始化活动节点\n for (int i = 0; i < MAX_ACTIVITIES; i++) {\n graph[i].activity = i + 1;\n graph[i].duration = 0;\n graph[i].earliestStartTime = 0;\n graph[i].latestStartTime = 0;\n graph[i].numDependencies = 0;\n graph[i].dependencies = NULL;\n }\n\n // 设置每个活动的持续时间\n graph[0].duration = 3; // A\n graph[1].duration = 2; // B\n graph[2].duration = 4; // C\n graph[3].duration = 5; // D\n graph[4].duration = 8; // E\n graph[5].duration = 3; // F\n graph[6].duration = 5; // G\n graph[7].duration = 10; // H\n graph[8].duration = 2; // I\n\n // 设置每个活动的依赖关系\n graph[1].numDependencies = 1; // B depends on A\n graph[1].dependencies = (Node**)malloc(sizeof(Node*));\n graph[1].dependencies[0] = &graph[0]; // B depends on A\n\n graph[2].numDependencies = 1; // C depends on A\n graph[2].dependencies = (Node**)malloc(sizeof(Node*));\n graph[2].dependencies[0] = &graph[0]; // C depends on A\n\n graph[3].numDependencies = 1; // D depends on B\n graph[3].dependencies = (Node**)malloc(sizeof(Node*));\n graph[3].dependencies[0] = &graph[1]; // D depends on B\n\n graph[4].numDependencies = 1; // E depends on B\n graph[4].dependencies = (Node**)malloc(sizeof(Node*));\n graph[4].dependencies[0] = &graph[1]; // E depends on B\n\n graph[5].numDependencies = 1; // F depends on C\n graph[5].dependencies = (Node**)malloc(sizeof(Node*));\n graph[5].dependencies[0] = &graph[2]; // F depends on C\n\n graph[6].numDependencies = 1; // G depends on F\n graph[6].dependencies = (Node**)malloc(sizeof(Node*));\n graph[6].dependencies[0] = &graph[5]; // G depends on F\n\n graph[7].numDependencies = 1; // H depends on E\n graph[7].dependencies = (Node**)malloc(sizeof(Node*));\n graph[7].dependencies[0] = &graph[4]; // H depends on E\n\n graph[8].numDependencies = 3; // I depends on D, G, and H\n graph[8].dependencies = (Node**)malloc(3 * sizeof(Node*));\n graph[8].dependencies[0] = &graph[3]; // I depends on D\n graph[8].dependencies[1] = &graph[6]; // I depends on G\n graph[8].dependencies[2] = &graph[7]; // I depends on H\n}\n\nvoid calculateEarliestStartTime(Node* graph) {\n // 计算每个活动的最早开始时间\n for (int i = 0; i < MAX_ACTIVITIES; i++) {\n Node* currentNode = &graph[i];\n int maxDependencyTime = 0;\n\n // 找到所有依赖活动中最晚的最早开始时间\n for (int j = 0; j < currentNode->numDependencies; j++) {\n Node* dependency = currentNode->dependencies[j];\n if (dependency->earliestStartTime + dependency->duration > maxDependencyTime) {\n maxDependencyTime = dependency->earliestStartTime + dependency->duration;\n }\n }\n\n // 设置当前活动的最早开始时间\n currentNode->earliestStartTime = maxDependencyTime;\n }\n}\n\nvoid calculateLatestStartTime(Node* graph) {\n // 设置最后一个活动的最晚开始时间为其最早开始时间\n graph[MAX_ACTIVITIES - 1].latestStartTime = graph[MAX_ACTIVITIES - 1].earliestStartTime;\n\n // 逆向计算每个活动的最晚开始时间\n for (int i = MAX_ACTIVITIES - 2; i >= 0; i--) {\n Node* currentNode = &graph[i];\n int minDependencyTime = currentNode->latestStartTime;\n\n // 找到所有依赖活动中最早的最晚开始时间\n for (int j = 0; j < currentNode->numDependencies; j++) {\n Node* dependency = currentNode->dependencies[j];\n if (dependency->latestStartTime - dependency->duration < minDependencyTime) {\n minDependencyTime = dependency->latestStartTime - dependency->duration;\n }\n }\n\n // 设置当前活动的最晚开始时间\n currentNode->latestStartTime = minDependencyTime;\n }\n}\n\nvoid printCriticalPath(Node* graph) {\n printf("关键路径: ");\n\n for (int i = 0; i < MAX_ACTIVITIES; i++) {\n if (graph[i].earliestStartTime == graph[i].latestStartTime) {\n printf("%c ", 'A' + i);\n }\n }\n\n printf("\n");\n}\n\nvoid printLatestStartTime(Node* graph) {\n printf("项目最迟开始时间: %d\n", graph[0].latestStartTime);\n}\n\nint main() {\n Node graph[MAX_ACTIVITIES];\n initializeGraph(graph);\n\n calculateEarliestStartTime(graph);\n calculateLatestStartTime(graph);\n\n printCriticalPath(graph);\n printLatestStartTime(graph);\n\n return 0;\n}\n\n\n运行代码将会输出以下结果：\n\n\n关键路径: A B E H I \n项目最迟开始时间: 21\n\n\n根据关键路径，项目最迟应在21天之前开始，以便在10月1日前完成装修工程。\n