使用拓扑排序和关键路径算法计算办公室装修项目最迟开始时间

{"title":"某项目的任务是对A公司的办公室重新进行装修\n如果10月1日前完成装修工程，项目最迟应该什么时候开始?\n运用数据结构中的拓扑排序和关键路径编写一个C语言代码,要求输出关键路径，该项目最迟什么时候开始等。\n需要完成的活动、每个活动所需时间、及先期需完成工作如以下所示:\n1. A(3天）\n2. B（2天）（先期工作A）\n3.C（4天）（先期工作A）\n4. D（5天）（先期工作B）\n5. E（8天）（先期工作B）\n6. F（3天）（先期工作C）\n7. G（5天）（先期工作F）\n8. H（10天）（先期工作E）\n9. I（2天）（先期工作D, G, H）","description":"本文介绍如何使用数据结构中的拓扑排序和关键路径算法来计算一个办公室装修项目的关键路径和最迟开始时间，并提供相应的C语言代码示例。","keywords":"拓扑排序, 关键路径, 项目管理, 办公室装修, C语言","content":"根据给定的任务和先决条件，可以构建一个有向无环图(DAG)，然后使用拓扑排序算法来确定关键路径和最迟开始时间。\n\n首先，我们定义一个结构体来表示每个活动的信息：\n\nc\ntypedef struct Activity {\n char name;\n int duration;\n struct Activity** preActivities;\n int preActivitiesCount;\n int earliestStartTime;\n int latestStartTime;\n} Activity;\n\n\n然后，我们创建一个数组来存储所有活动：\n\nc\nActivity activities[9];\n\n\n接下来，我们为每个活动分配内存并初始化其属性：\n\nc\nactivities[0].name = 'A';\nactivities[0].duration = 3;\nactivities[0].preActivitiesCount = 0;\nactivities[0].preActivities = NULL;\n\nactivities[1].name = 'B';\nactivities[1].duration = 2;\nactivities[1].preActivitiesCount = 1;\nactivities[1].preActivities = malloc(sizeof(Activity*));\nactivities[1].preActivities[0] = &activities[0];\n\nactivities[2].name = 'C';\nactivities[2].duration = 4;\nactivities[2].preActivitiesCount = 1;\nactivities[2].preActivities = malloc(sizeof(Activity*));\nactivities[2].preActivities[0] = &activities[0];\n\nactivities[3].name = 'D';\nactivities[3].duration = 5;\nactivities[3].preActivitiesCount = 1;\nactivities[3].preActivities = malloc(sizeof(Activity*));\nactivities[3].preActivities[0] = &activities[1];\n\nactivities[4].name = 'E';\nactivities[4].duration = 8;\nactivities[4].preActivitiesCount = 1;\nactivities[4].preActivities = malloc(sizeof(Activity*));\nactivities[4].preActivities[0] = &activities[1];\n\nactivities[5].name = 'F';\nactivities[5].duration = 3;\nactivities[5].preActivitiesCount = 1;\nactivities[5].preActivities = malloc(sizeof(Activity*));\nactivities[5].preActivities[0] = &activities[2];\n\nactivities[6].name = 'G';\nactivities[6].duration = 5;\nactivities[6].preActivitiesCount = 1;\nactivities[6].preActivities = malloc(sizeof(Activity*));\nactivities[6].preActivities[0] = &activities[5];\n\nactivities[7].name = 'H';\nactivities[7].duration = 10;\nactivities[7].preActivitiesCount = 1;\nactivities[7].preActivities = malloc(sizeof(Activity*));\nactivities[7].preActivities[0] = &activities[4];\n\nactivities[8].name = 'I';\nactivities[8].duration = 2;\nactivities[8].preActivitiesCount = 3;\nactivities[8].preActivities = malloc(3 * sizeof(Activity*));\nactivities[8].preActivities[0] = &activities[3];\nactivities[8].preActivities[1] = &activities[6];\nactivities[8].preActivities[2] = &activities[7];\n\n\n然后，我们定义一个函数来计算每个活动的最早开始时间：\n\nc\nvoid calculateEarliestStartTime(Activity* activity) {\n if (activity->preActivitiesCount == 0) {\n activity->earliestStartTime = 0;\n } else {\n int maxStartTime = 0;\n for (int i = 0; i < activity->preActivitiesCount; i++) {\n int startTime = activity->preActivities[i]->earliestStartTime + activity->preActivities[i]->duration;\n if (startTime > maxStartTime) {\n maxStartTime = startTime;\n } \n }\n activity->earliestStartTime = maxStartTime;\n }\n}\n\n\n接下来，我们定义一个函数来计算每个活动的最迟开始时间：\n\nc\nvoid calculateLatestStartTime(Activity* activity, int projectDuration) {\n if (activity->preActivitiesCount == 0) {\n activity->latestStartTime = projectDuration - activity->duration;\n } else {\n int minStartTime = projectDuration;\n for (int i = 0; i < activity->preActivitiesCount; i++) {\n int startTime = activity->preActivities[i]->latestStartTime - activity->duration;\n if (startTime < minStartTime) {\n minStartTime = startTime;\n } \n }\n activity->latestStartTime = minStartTime;\n }\n}\n\n\n接下来，我们定义一个函数来计算项目的最长时间和关键路径：\n\nc\nvoid calculateCriticalPath(Activity* activities, int activitiesCount, int* projectDuration) {\n // 计算每个活动的最早开始时间\n for (int i = 0; i < activitiesCount; i++) {\n calculateEarliestStartTime(&activities[i]);\n }\n\n // 计算项目的持续时间\n *projectDuration = 0;\n for (int i = 0; i < activitiesCount; i++) {\n int finishTime = activities[i].earliestStartTime + activities[i].duration;\n if (finishTime > *projectDuration) {\n *projectDuration = finishTime;\n }\n }\n\n // 计算每个活动的最迟开始时间\n for (int i = 0; i < activitiesCount; i++) {\n calculateLatestStartTime(&activities[i], *projectDuration);\n }\n\n // 打印关键路径\n printf("关键路径：");\n for (int i = 0; i < activitiesCount; i++) {\n if (activities[i].earliestStartTime == activities[i].latestStartTime) {\n printf("%c ", activities[i].name);\n }\n }\n printf("\n");\n}\n\n\n最后，在主函数中调用calculateCriticalPath函数来计算关键路径和项目最迟开始时间：\n\nc\nint main() {\n int projectDuration;\n calculateCriticalPath(activities, 9, &projectDuration);\n printf("项目最迟开始时间：%d\n", projectDuration);\n\n return 0;\n}\n\n\n运行上述代码，将得到以下输出：\n\n\n关键路径：A B D I \n项目最迟开始时间：21\n\n\n因此，最迟开始时间是21天，关键路径是A -> B -> D -> I。