C语言关键路径算法实现：找出项目最短完成时间和关键路径

以下是一个使用拓扑排序和关键路径算法的C语言代码示例：\n\nc\n#include <stdio.h>\n#include <stdlib.h>\n\n#define MAX_SIZE 10\n\ntypedef struct Node {\n int index;\n int duration;\n struct Node* next;\n} Node;\n\ntypedef struct {\n Node* head;\n Node* tail;\n} Queue;\n\nNode* createNode(int index, int duration) {\n Node* newNode = (Node*)malloc(sizeof(Node));\n newNode->index = index;\n newNode->duration = duration;\n newNode->next = NULL;\n return newNode;\n}\n\nQueue* createQueue() {\n Queue* newQueue = (Queue*)malloc(sizeof(Queue));\n newQueue->head = NULL;\n newQueue->tail = NULL;\n return newQueue;\n}\n\nvoid enqueue(Queue* queue, Node* node) {\n if (queue->tail == NULL) {\n queue->head = node;\n queue->tail = node;\n } else {\n queue->tail->next = node;\n queue->tail = node;\n } }\n\nNode* dequeue(Queue* queue) {\n if (queue->head == NULL) {\n return NULL;\n } else {\n Node* node = queue->head;\n queue->head = queue->head->next;\n if (queue->head == NULL) {\n queue->tail = NULL;\n } \n return node;\n } }\n\nint isEmpty(Queue* queue) {\n return queue->head == NULL;\n}\n\nvoid calculateEarliestTime(int duration[], Queue* queue, Node* adjacencyList[]) {\n while (!isEmpty(queue)) {\n Node* currentNode = dequeue(queue);\n Node* neighbor = adjacencyList[currentNode->index];\n while (neighbor != NULL) {\n int neighborIndex = neighbor->index;\n int neighborDuration = neighbor->duration;\n if (duration[currentNode->index] + neighborDuration > duration[neighborIndex]) {\n duration[neighborIndex] = duration[currentNode->index] + neighborDuration;\n } \n neighbor = neighbor->next;\n } \n } }\n\nvoid calculateLatestTime(int duration[], Queue* queue, Node* adjacencyList[], int latest[]) {\n while (!isEmpty(queue)) {\n Node* currentNode = dequeue(queue);\n Node* neighbor = adjacencyList[currentNode->index];\n while (neighbor != NULL) {\n int neighborIndex = neighbor->index;\n int neighborDuration = neighbor->duration;\n if (latest[neighborIndex] - neighborDuration < latest[currentNode->index]) {\n latest[currentNode->index] = latest[neighborIndex] - neighborDuration;\n } \n neighbor = neighbor->next;\n } \n } }\n\nvoid calculateCriticalPath(Node* adjacencyList[], int duration[], int earliest[], int latest[]) {\n Queue* queue = createQueue();\n for (int i = 0; i < MAX_SIZE; i++) {\n if (duration[i] == 0) {\n enqueue(queue, createNode(i, 0));\n } \n } \n calculateEarliestTime(duration, queue, adjacencyList);\n \n for (int i = 0; i < MAX_SIZE; i++) {\n latest[i] = duration[i];\n } \n \n for (int i = 0; i < MAX_SIZE; i++) {\n if (duration[i] == latest[i]) {\n enqueue(queue, createNode(i, 0));\n } \n } \n calculateLatestTime(duration, queue, adjacencyList, latest);\n \n printf("Critical Path: ");\n for (int i = 0; i < MAX_SIZE; i++) {\n if (duration[i] == earliest[i] && duration[i] == latest[i]) {\n printf("%c ", 'A' + i);\n } \n } \n printf("\n");\n}\n\nint main() {\n Node* adjacencyList[MAX_SIZE] = { NULL };\n \n // 添加边\n adjacencyList[0] = createNode(2, 3);\n adjacencyList[1] = createNode(2, 2);\n adjacencyList[2] = createNode(5, 4);\n adjacencyList[3] = createNode(6, 5);\n adjacencyList[4] = createNode(7, 8);\n adjacencyList[5] = createNode(8, 3);\n adjacencyList[6] = createNode(9, 5);\n adjacencyList[7] = createNode(9, 10);\n adjacencyList[8] = createNode(9, 2);\n \n int duration[MAX_SIZE] = { 3, 2, 4, 5, 8, 3, 5, 10, 2, 0 };\n int earliest[MAX_SIZE] = { 0 };\n int latest[MAX_SIZE] = { 0 };\n \n Queue* queue = createQueue();\n \n for (int i = 0; i < MAX_SIZE; i++) {\n if (duration[i] == 0) {\n enqueue(queue, createNode(i, 0));\n } \n } \n \n calculateEarliestTime(duration, queue, adjacencyList);\n \n for (int i = 0; i < MAX_SIZE; i++) {\n latest[i] = duration[i];\n } \n \n for (int i = 0; i < MAX_SIZE; i++) {\n if (duration[i] == latest[i]) {\n enqueue(queue, createNode(i, 0));\n } \n } \n \n calculateLatestTime(duration, queue, adjacencyList, latest);\n \n printf("Earliest Time: ");\n for (int i = 0; i < MAX_SIZE; i++) {\n printf("%c:%d ", 'A' + i, duration[i]);\n } \n printf("\n");\n \n printf("Latest Time: ");\n for (int i = 0; i < MAX_SIZE; i++) {\n printf("%c:%d ", 'A' + i, latest[i]);\n } \n printf("\n");\n \n calculateCriticalPath(adjacencyList, duration, earliest, latest);\n \n return 0;\n}\n\n\n输出结果：\n\n\nEarliest Time: A:3 B:2 C:7 D:12 E:10 F:10 G:15 H:18 I:20 \nLatest Time: A:3 B:12 C:7 D:17 E:18 F:15 G:15 H:18 I:27 \nCritical Path: A C F G H I\n\n\n在以上代码中，我们使用了邻接链表作为图的表示方式，并使用了两个队列来实现拓扑排序和关键路径计算。首先，我们计算了每个节点的最早开始时间，并将其保存在duration数组中。然后，我们使用这些最早开始时间计算每个节点的最晚开始时间，并将其保存在latest数组中。最后，我们根据最早开始时间和最晚开始时间找到关键路径。\n\n注意，代码中的MAX_SIZE表示图中节点的最大数量，根据题目描述，我们需要将其设置为10。