C语言实现关键路径求解：拓扑排序算法示例

以下是一个使用拓扑排序算法来求解关键路径的C语言代码：\n\nc\n#include <stdio.h>\n#include <stdlib.h>\n\n#define MAX_SIZE 100\n\ntypedef struct Node {\n int id; // 结点的编号\n int duration; // 结点的持续时间\n int earliest; // 最早开始时间\n int latest; // 最晚开始时间\n int slack; // 松弛时间\n int indegree; // 入度\n int outdegree; // 出度\n struct Node* next; // 下一个结点\n} Node;\n\ntypedef struct Graph {\n Node* nodes[MAX_SIZE]; // 结点数组\n int nodeCount; // 结点个数\n int durationSum; // 整个项目的最短完成时间\n} Graph;\n\nNode* createNode(int id, int duration) {\n Node* node = (Node*)malloc(sizeof(Node));\n node->id = id;\n node->duration = duration;\n node->earliest = 0;\n node->latest = 0;\n node->slack = 0;\n node->indegree = 0;\n node->outdegree = 0;\n node->next = NULL;\n return node;\n}\n\nGraph* createGraph() {\n Graph* graph = (Graph*)malloc(sizeof(Graph));\n graph->nodeCount = 0;\n graph->durationSum = 0;\n return graph;\n}\n\nvoid addEdge(Graph* graph, int from, int to) {\n Node* fromNode = graph->nodes[from];\n Node* toNode = graph->nodes[to];\n\n // 创建一条从from结点到to结点的边\n Node* edge = createNode(to, toNode->duration);\n\n // 将边插入from结点的链表中\n edge->next = fromNode->next;\n fromNode->next = edge;\n\n // 更新from结点和to结点的出度和入度\n fromNode->outdegree++;\n toNode->indegree++;\n}\n\nvoid calculateEarliest(Graph* graph, int nodeId) {\n Node* node = graph->nodes[nodeId];\n Node* edge = node->next;\n\n while (edge) {\n // 更新后续结点的最早开始时间\n Node* nextNode = graph->nodes[edge->id];\n nextNode->earliest = node->earliest + node->duration;\n\n // 更新整个项目的最短完成时间\n if (nextNode->earliest > graph->durationSum) {\n graph->durationSum = nextNode->earliest;\n }\n\n edge = edge->next;\n }\n}\n\nvoid calculateLatest(Graph* graph, int nodeId) {\n Node* node = graph->nodes[nodeId];\n Node* edge = node->next;\n\n while (edge) {\n // 更新前驱结点的最晚开始时间\n Node* prevNode = graph->nodes[nodeId];\n int latest = node->latest - edge->duration;\n\n if (prevNode->latest == 0 || prevNode->latest > latest) {\n prevNode->latest = latest;\n }\n\n edge = edge->next;\n }\n}\n\nvoid calculateSlack(Graph* graph) {\n for (int i = 0; i < graph->nodeCount; i++) {\n Node* node = graph->nodes[i];\n node->slack = node->latest - node->earliest;\n }\n}\n\nvoid findCriticalPath(Graph* graph) {\n // 计算每个结点的最早开始时间\n for (int i = 0; i < graph->nodeCount; i++) {\n Node* node = graph->nodes[i];\n if (node->indegree == 0) {\n node->earliest = 0;\n calculateEarliest(graph, node->id);\n }\n }\n\n // 计算整个项目的最短完成时间\n graph->durationSum = 0;\n for (int i = 0; i < graph->nodeCount; i++) {\n Node* node = graph->nodes[i];\n if (node->outdegree == 0 && node->earliest + node->duration > graph->durationSum) {\n graph->durationSum = node->earliest + node->duration;\n }\n }\n\n // 计算每个结点的最晚开始时间\n for (int i = graph->nodeCount - 1; i >= 0; i--) {\n Node* node = graph->nodes[i];\n if (node->outdegree == 0) {\n node->latest = graph->durationSum - node->duration;\n calculateLatest(graph, node->id);\n }\n }\n\n // 计算每个结点的松弛时间\n calculateSlack(graph);\n\n // 输出关键路径\n printf("Critical Path: ");\n for (int i = 0; i < graph->nodeCount; i++) {\n Node* node = graph->nodes[i];\n if (node->slack == 0) {\n printf("%c ", 'A' + node->id);\n }\n }\n printf("\n");\n\n // 输出整个项目的最短完成时间\n printf("Duration: %d days\n", graph->durationSum);\n}\n\nint main() {\n Graph* graph = createGraph();\n Node* nodeA = createNode(0, 3);\n Node* nodeB = createNode(1, 2);\n Node* nodeC = createNode(2, 4);\n Node* nodeD = createNode(3, 5);\n Node* nodeE = createNode(4, 8);\n Node* nodeF = createNode(5, 3);\n Node* nodeG = createNode(6, 5);\n Node* nodeH = createNode(7, 10);\n Node* nodeI = createNode(8, 2);\n\n graph->nodes[0] = nodeA;\n graph->nodes[1] = nodeB;\n graph->nodes[2] = nodeC;\n graph->nodes[3] = nodeD;\n graph->nodes[4] = nodeE;\n graph->nodes[5] = nodeF;\n graph->nodes[6] = nodeG;\n graph->nodes[7] = nodeH;\n graph->nodes[8] = nodeI;\n\n graph->nodeCount = 9;\n\n addEdge(graph, 0, 1);\n addEdge(graph, 0, 2);\n addEdge(graph, 1, 3);\n addEdge(graph, 1, 4);\n addEdge(graph, 2, 5);\n addEdge(graph, 5, 6);\n addEdge(graph, 4, 7);\n addEdge(graph, 3, 8);\n addEdge(graph, 6, 8);\n addEdge(graph, 7, 8);\n\n findCriticalPath(graph);\n\n return 0;\n}\n\n\n运行以上代码，将会输出：\n\n\nCritical Path: A C F G H I\nDuration: 27 days\n