C语言实现关键路径算法 - 拓扑排序与关键路径计算

#include <stdio.h>\n#include <stdlib.h>\n\n// 邻接表中的节点\nstruct Node {\n int task; // 任务编号\n int duration; // 任务持续时间\n struct Node* next; // 指向下一个节点的指针\n};\n\n// 邻接表\nstruct Graph {\n int numTasks; // 任务数量\n struct Node** adjList; // 邻接表的指针数组\n};\n\n// 创建一个节点\nstruct Node* createNode(int task, int duration) {\n struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));\n newNode->task = task; \n newNode->duration = duration; \n newNode->next = NULL; \n return newNode; \n}\n\n// 创建一个邻接表\nstruct Graph* createGraph(int numTasks) {\n struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));\n graph->numTasks = numTasks; \n graph->adjList = (struct Node**)malloc(numTasks * sizeof(struct Node*));\n for (int i = 0; i < numTasks; i++) {\n graph->adjList[i] = NULL; \n }\n return graph; \n}\n\n// 添加边\nvoid addEdge(struct Graph* graph, int src, int dest, int duration) {\n struct Node* newNode = createNode(dest, duration);\n newNode->next = graph->adjList[src];\n graph->adjList[src] = newNode; \n}\n\n// 拓扑排序的递归函数\nvoid topologicalSortUtil(struct Graph* graph, int v, int* visited, int* stack, int* top) {\n visited[v] = 1; // 标记当前节点为已访问\n\n struct Node* temp = graph->adjList[v];\n while (temp != NULL) {\n if (!visited[temp->task]) {\n topologicalSortUtil(graph, temp->task, visited, stack, top);\n }\n temp = temp->next; \n }\n\n stack[++(top)] = v; // 将当前节点压入栈中\n}\n\n// 执行拓扑排序\nvoid topologicalSort(struct Graph graph, int* stack) {\n int numTasks = graph->numTasks; \n int visited[numTasks]; \n int top = -1; \n\n for (int i = 0; i < numTasks; i++) {\n visited[i] = 0; // 初始化visited数组\n }\n\n for (int i = 0; i < numTasks; i++) {\n if (!visited[i]) {\n topologicalSortUtil(graph, i, visited, stack, &top);\n }\n }\n}\n\n// 计算关键路径\nvoid calculateCriticalPath(struct Graph* graph, int* stack, int* est, int* lst) {\n int numTasks = graph->numTasks; \n\n // 初始化最早开始时间和最晚开始时间数组\n for (int i = 0; i < numTasks; i++) {\n est[i] = -1; \n lst[i] = -1; \n }\n\n est[0] = 0; // 第一个任务的最早开始时间为0\n\n // 计算最早开始时间\n for (int i = 0; i < numTasks; i++) {\n int currentTask = stack[i]; \n struct Node* temp = graph->adjList[currentTask]; \n while (temp != NULL) {\n if (est[temp->task] < est[currentTask] + temp->duration) {\n est[temp->task] = est[currentTask] + temp->duration; \n }\n temp = temp->next; \n }\n }\n\n lst[numTasks-1] = est[numTasks-1]; // 最后一个任务的最晚开始时间等于最早开始时间\n\n // 计算最晚开始时间\n for (int i = numTasks-1; i >= 0; i--) {\n int currentTask = stack[i];\n struct Node* temp = graph->adjList[currentTask];\n while (temp != NULL) {\n if (lst[temp->task] - temp->duration > lst[currentTask] || lst[currentTask] == -1) {\n lst[currentTask] = lst[temp->task] - temp->duration; \n }\n temp = temp->next; \n }\n }\n}\n\nint main() {\n int numTasks = 6; \n struct Graph* graph = createGraph(numTasks); \n\n // 添加边\n addEdge(graph, 0, 1, 2); // 采购原材料 -> 设计图纸\n addEdge(graph, 1, 2, 5); // 设计图纸 -> 制造产品\n addEdge(graph, 2, 3, 10); // 制造产品 -> 测试产品\n addEdge(graph, 3, 4, 3); // 测试产品 -> 包装产品\n addEdge(graph, 4, 5, 2); // 包装产品 -> 发货产品\n\n int stack[numTasks];\n topologicalSort(graph, stack); \n\n int est[numTasks];\n int lst[numTasks];\n calculateCriticalPath(graph, stack, est, lst);\n\n printf("关键路径：");\n for (int i = 0; i < numTasks; i++) {\n if (est[i] == lst[i]) {\n printf("%d ", i);\n }\n }\n printf("\n");\n\n return 0; \n}