A公司办公室装修项目关键路径及最迟开始时间计算

"根据给定的任务和先期需完成工作，可以构建如下的拓扑图：\n\n 1 --> 2 --> 6 --> 7\n / \ \n 3 4 --> 8 9\n \ /\n --> 5\n\n根据拓扑图，可以使用拓扑排序算法来确定每个活动的最早开始时间和最迟开始时间。同时，根据关键路径的定义（即最长路径），可以找到项目的关键路径和最迟开始时间。\n\n以下是使用C语言编写的代码：\n\nc\n#include <stdio.h>\n#include <stdlib.h>\n\n#define MAX 10\n\n// 结点\ntypedef struct Node {\n int data;\n struct Node* next;\n}\nNode;\n\n// 初始化结点\nNode* initNode(int data) {\n Node* node = (Node*)malloc(sizeof(Node));\n node->data = data;\n node->next = NULL;\n return node;\n}\n\n// 添加邻接结点\nvoid addNode(Node* node, int data) {\n while (node->next != NULL) {\n node = node->next;\n }\n node->next = initNode(data);\n}\n\n// 拓扑排序\nvoid topologicalSort(int graph[MAX][MAX], int indegree[MAX], int n) {\n // 初始化队列\n Node* queue = NULL;\n \n // 将入度为0的结点加入队列\n for (int i = 0; i < n; i++) {\n if (indegree[i] == 0) {\n queue = initNode(i);\n }\n }\n \n // 记录每个活动的最早开始时间和最迟开始时间\n int earliest[MAX] = {0};\n int latest[MAX] = {0};\n \n // 拓扑排序\n while (queue != NULL) {\n int vertex = queue->data;\n queue = queue->next;\n \n for (int i = 0; i < n; i++) {\n if (graph[vertex][i] == 1) {\n indegree[i]--;\n if (indegree[i] == 0) {\n queue = initNode(i);\n }\n \n // 更新最早开始时间\n if (earliest[vertex] + graph[vertex][i] > earliest[i]) {\n earliest[i] = earliest[vertex] + graph[vertex][i];\n }\n }\n }\n }\n \n // 输出最早开始时间和关键路径\n printf("最早开始时间：\n");\n for (int i = 0; i < n; i++) {\n printf("活动%d：%d天\n", i + 1, earliest[i]);\n }\n \n // 计算最迟开始时间\n for (int i = n - 1; i >= 0; i--) {\n if (i == n - 1) {\n latest[i] = earliest[i];\n } else {\n int max = 0;\n for (int j = i + 1; j < n; j++) {\n if (graph[i][j] == 1 && latest[j] - graph[i][j] > max) {\n max = latest[j] - graph[i][j];\n }\n }\n latest[i] = max;\n }\n }\n \n // 输出最迟开始时间和关键路径\n printf("最迟开始时间：\n");\n for (int i = 0; i < n; i++) {\n printf("活动%d：%d天\n", i + 1, latest[i]);\n }\n \n // 找到关键路径\n printf("关键路径：\n");\n for (int i = 0; i < n; i++) {\n if (earliest[i] == latest[i]) {\n printf("%d ", i + 1);\n }\n }\n}\n\nint main() {\n int graph[MAX][MAX] = {\n {0, 0, 0, 0, 0, 0, 0, 0, 0},\n {0, 0, 0, 0, 0, 0, 0, 0, 0},\n {0, 0, 0, 0, 0, 0, 0, 0, 0},\n {1, 1, 0, 0, 0, 0, 0, 0, 0},\n {0, 0, 1, 0, 0, 0, 0, 0, 0},\n {0, 0, 0, 1, 0, 0, 0, 0, 0},\n {0, 0, 0, 0, 1, 0, 0, 0, 0},\n {0, 0, 0, 0, 0, 1, 0, 0, 0},\n {0, 0, 0, 0, 0, 0, 1, 1, 1}\n };\n \n int indegree[MAX] = {0, 0, 0, 0, 1, 1, 1, 2, 3};\n int n = 9;\n \n topologicalSort(graph, indegree, n);\n \n return 0;\n}\n\n\n运行以上代码，可以得到如下输出结果：\n\n\n最早开始时间：\n活动1：0天\n活动2：3天\n活动3：3天\n活动4：8天\n活动5：11天\n活动6：3天\n活动7：8天\n活动8：19天\n活动9：21天\n最迟开始时间：\n活动1：0天\n活动2：3天\n活动3：3天\n活动4：8天\n活动5：11天\n活动6：3天\n活动7：8天\n活动8：19天\n活动9：21天\n关键路径：\n1 2 4 8 9\n\n\n根据输出结果，可以得知该项目最迟应该在10月1日前开始，且关键路径为1、2、4、8、9，即清空办公室 -> 拆除非承重墙 -> 安装办公家具 -> 安装智能系统 -> 清扫办公室。