设计求解AOE网关键路径程序（详细设计，附完整实现代码）

本文主要是介绍设计求解AOE网关键路径程序（详细设计，附完整实现代码），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一、课程设计内容

二、课程设计实现功能

三、具体实现功能过程以及可能遇到的问题

四、实现程序功能模块图

五、具体实现代码（完整代码C语言）

六、演示如何操作（注意输入信息,这里以上面AOE网为准输入）

6.1先输入AOE网的顶点个数和边数

6.2输入顶点元素（复制粘贴一下即可）

6.3输入边的信息（复制粘贴即可）

6.5运行结果页面展示

6.5.1AOE输入信息图：

6.5.2图的邻接表示图：

6.5.3关键路径图和最短总工程时间：

七、总结与心得体会

坚持阅读，才能发现美的存在！

更多精彩等你哦！

一起来场跨时空的交流。

一、课程设计内容

设计内容：某新房精装修项目工作内容主要包括：(A)施工作业场所检验交接；(B)窗橱，门框防护；(C)防水作业；(D)土建改造；(E)防水检验接收；(F)水电检验接收；(G)原始地面防护；(H)铺贴瓷砖作业；(I)厅房吊顶作业；(J)天花吊顶作业；(K)顶棚一次面油；(L)墙面一次面油；(M)橱柜安装；(N)顶棚二次面油；(O)厨卫家电安装；(P)衣橱，门框进场作业；(Q)墙纸或墙面二次面油作业；(R)空调安装；(S)门扇安装；(T)木地板作业；(U)验收及整改；(V)施工完成并交付(将相应说明书的保留及移交物业)。根据以上各项工作内容具体工作时间如下表1所示。请构建本项目的AOE网，求出其关键路径及最短总工期。具体装修项目工期估计如下表1所以：

表1：某装修项目工期估计表

工作名称	工作内容	估计工期(单位：天)
A	施工作业场所检验交接	3
B	窗橱,门框防护	3
C	防水作业	10
D	土建改造	20
E	防水检验接收	3
F	水电检验接收	3
G	原始地面防护	2
H	铺贴瓷砖作业	6
I	厅房吊顶作业	10
J	天花吊顶作业	9
K	顶棚一次面油	14
L	墙面一次面油	10
M	橱柜安装	3
N	顶棚二次面油	10
O	厨卫家电安装	5
P	衣橱,门框进场作业	4
Q	墙纸或墙面二次面油作业	10
R	空调安装	3
S	门扇安装	3
T	木地板作业	10
U	验收及整改	20
V	施工完成并交接交付	17

二、课程设计实现功能

确定各项工作的先后关系，绘制AOE网络图；
计算AOE 网络图中的各活动时间；
确定关键路径；
计算最短总工期。

三、具体实现功能过程以及可能遇到的问题

1. 构建AOE网：根据用户输入的顶点个数和边数，使用邻接矩阵或邻接表的方式来表示图的结构。为每个顶点分配一个唯一的标识符，并将边的起始顶点和结束顶点添加到图中。可以使用二维数组表示邻接矩阵，或者使用链表表示邻接表。

2. 计算最早开始时间和最早完成时间：使用拓扑排序的方式来确定活动的顺序。从起始顶点开始，按照拓扑排序的顺序依次计算每个活动的最早开始时间和最早完成时间。对于每个活动，需要考虑其前驱活动的最早完成时间。可以使用深度优先搜索或广度优先搜索来进行拓扑排序。

3. 计算最晚开始时间和最晚完成时间：可以使用逆拓扑排序的方式来确定活动的顺序。从终点顶点开始，按照逆拓扑排序的顺序依次计算每个活动的最晚开始时间和最晚完成时间。对于每个活动，需要考虑其后继活动的最晚开始时间。可以使用深度优先搜索或广度优先搜索来进行逆拓扑排序。

4. 输出关键路径和最短总工期：通过比较每个活动的最早完成时间和最晚完成时间，可以确定关键路径上的活动。关键路径上的活动即为最早开始时间和最晚开始时间相等的活动。最短总工期可以通过终点顶点的最早完成时间来确定。

5. 错误处理：需要处理输入错误的情况，例如输入的顶点个数或边数为负数，活动的持续时间为负数等。可以使用条件判断语句来检查输入的有效性，并在出现错误时给出适当的提示信息。

6. 内存管理：在程序结束后，需要释放动态分配的内存，以防止内存泄漏。可以使用`malloc()`函数来分配内存，使用`free()`函数来释放内存。

四、实现程序功能模块图

4.1AOE网络图4.2程序流程图

五、具体实现代码（完整代码C语言）

#include <stdio.h>
#include <stdlib.h>
#define VertexType int //顶点的数据类型（char） 
#define VertexMax 40 //最大顶点个数 
typedef struct ArcNode//边表 
{int adjvex;//存储的是该顶点在顶点数组即AdjList[]中的位置 int weight;//权值 struct ArcNode* next;
}ArcNode;typedef struct VNode //顶单个点 
{VertexType vertex;struct ArcNode* firstarc;
}VNode;typedef struct //顶点表 
{VNode AdjList[VertexMax];//由顶点构成的结构体数组 int vexnum, arcnum; //顶点数和边数 
}ALGraph;int LocateVex(ALGraph* G, VertexType v)
{int i;for (i = 0; i < G->vexnum; i++){if (v == G->AdjList[i].vertex){return i;}}printf("No Such Vertex!\n");return -1;
}//有向图 
void CreateDN(ALGraph* G)
{int i, j;//1.输入顶点数和边数 printf("输入顶点个数和边数：\n");printf("顶点数 n=");scanf("%d", &G->vexnum);printf("边  数 e=");scanf("%d", &G->arcnum);printf("\n");printf("\n");//2.顶点表数据域填值初始化顶点表指针域 printf("输入顶点元素(用空格隔开)：");for (i = 0; i < G->vexnum; i++){/*printf("输入第%d个顶点信息：", i + 1);*/scanf(" %d", &G->AdjList[i].vertex);//printf("222%d", G->AdjList[i].vertex);G->AdjList[i].firstarc = NULL;}printf("\n");//3.输入边信息构造邻接表 int n, m;VertexType v1, v2;int weight;ArcNode* p1, * p2;printf("请输入边的信息：\n\n");for (i = 0; i < G->arcnum; i++){   //输入边信息，并确定v1和v2在G中的位置，即顶点在AdjList[]数组中的位置（下标）  printf("输入第%d条边信息：", i + 1);scanf(" %d%d,%d", &v1, &v2, &weight);n = LocateVex(G, v1);m = LocateVex(G, v2);if (n == -1 || m == -1){printf("NO This Vertex!\n");return;}p1 = (ArcNode*)malloc(sizeof(ArcNode));p1->adjvex = m;//填上坐标 p1->weight = weight;//填上权值 p1->next = G->AdjList[n].firstarc;//改链（头插法）  G->AdjList[n].firstarc = p1;}//for  
}void print(ALGraph G)
{int i;ArcNode* p;printf("\n-------------------------------");printf("\n图的邻接表表示：\n");for (i = 0; i < G.vexnum; i++){printf("\n   AdjList[%d]%4d", i, G.AdjList[i].vertex);p = G.AdjList[i].firstarc;while (p != NULL){printf("-->%d(%d)", p->adjvex+1, p->weight);p = p->next;}}printf("\n");printf("\n-------------------------------\n");
}int TopologicalSort(ALGraph* G, int* topo)
{int i;int top = -1;//栈顶指针 int Gettop;//用于存储/获取栈的栈顶元素 int count = 0;//用于统计拓扑排序生成的结点数（若生成结点数 < 图的结点数，则代表图中有环，拓扑排序不成功） int stack[VertexMax] = { 0 };//栈 int indegree[VertexMax] = { 0 };//入度数组 struct ArcNode* p;//临时变量 //1.计算顶点入度，并存入indegree数组中for (i = 0; i < G->vexnum; i++){if (G->AdjList[i].firstarc != NULL){p = G->AdjList[i].firstarc;while (p != NULL){indegree[p->adjvex]++;p = p->next;}}}//2.初始化部分：将初始入度为0的顶点入栈for (i = 0; i < G->vexnum; i++){if (indegree[i] == 0){stack[++top] = i;//先将指针加一在进行存储 }}//3.拓扑排序int m = 0;while (top != -1)//栈不为空 {Gettop = stack[top--];//获取栈顶元素，并且栈顶指针减一 topo[m++] = Gettop;//printf(" %c(%d)",G->AdjList[Gettop].vertex,topo[m-1]);//输出栈顶元素 count++;p = G->AdjList[Gettop].firstarc;while (p != NULL){indegree[p->adjvex]--;if (indegree[p->adjvex] == 0){stack[++top] = p->adjvex;}p = p->next;}}//4.判断拓扑排序是否成功（生成结点数 < 图的结点数，则代表图中有环，拓扑排序不成功） if (count < G->vexnum){printf("TopologicalSort Failed!\n");return 0; //拓扑排序失败 }elsereturn 1; //拓扑排序成功   
}void CriticalPath(ALGraph* G)
{int i;int j, k;// <Vj,Vk>int e, l;//活动最早开始时间/活动最晚开始时间  int topo[VertexMax];//拓扑数组，用于存储拓扑排序结果（存储内容是每个结点的坐标） int ve[VertexMax]; //事件vi的最早发生时间 int vl[VertexMax]; //事件vi的最晚发生时间 struct ArcNode* p;//1.调用拓扑排序，检测图是否存在环 if (!TopologicalSort(G, topo))//若拓扑排序成功，topo数组也将处理完毕 {return;}//2.正拓扑排序，求出事件最早发生时间 for (i = 0; i < G->vexnum; i++)ve[i] = 0;for (i = 0; i < G->vexnum; i++){j = topo[i];//j为起始点，k为终点 p = G->AdjList[j].firstarc;//用指针p去依次寻找j的每一个邻接点 while (p){k = p->adjvex;if (ve[k] < ve[j] + p->weight)//根据j的邻接点k，不断更新ve[]的值（选出最大值，原理类似于选择排序） {ve[k] = ve[j] + p->weight;}p = p->next;}}//3.逆拓扑排序，求出事件最迟发生时间 for (i = 0; i < G->vexnum; i++)vl[i] = ve[G->vexnum - 1];for (i = G->vexnum - 1; i >= 0; i--){j = topo[i];p = G->AdjList[j].firstarc;//让p去依次查找邻接点 while (p){k = p->adjvex;if (vl[j] > vl[k] - p->weight)//根据j的邻接点k，不断更新vl[]的值（选出最小值，原理类似于选择排序）{vl[j] = vl[k] - p->weight;}p = p->next;}}//输出ve[i] printf("\tve[i]:");for (i = 0; i < G->vexnum; i++){printf("\t%d", ve[i]);}printf("\n");//输出vl[i]printf("\tvl[i]:");for (i = 0; i < G->vexnum; i++){printf("\t%d", vl[i]);}printf("\n\n");//4.计算e和l，通过判断e是否等于l确定该活动是否是关键活动，从而确定关键路径for (i = 0; i < G->vexnum; i++){p = G->AdjList[i].firstarc;//让p去依次查找邻接点 while (p){j = p->adjvex;e = ve[i];//计算活动最早开始时间 e l = vl[j] - p->weight;//计算活动最晚开始时间 l if (e == l)//如果e=l，说明该活动是关键活动 {printf("\t%d->%d(%d)\n", G->AdjList[i].vertex, G->AdjList[j].vertex, p->weight);}p = p->next;}}printf("最短总工期：%d\n", ve[16]);}int main()
{ALGraph G;//声明顶点表 顶点数和边数 CreateDN(&G);//根据输入顶点数和边，生成有向图 print(G); //打印有向图邻接表 printf("关键路径：\n\n");CriticalPath(&G);  //输出关键路径 正向拓扑排序，逆向拓扑排序，确定关键路径，输出关键路径 system("pause"); return 0;
}

六、演示如何操作（注意输入信息,这里以上面AOE网为准输入）

6.1先输入AOE网的顶点个数和边数

n= 17

e = 22

6.2输入顶点元素（复制粘贴即可）

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

6.3输入边的信息（复制粘贴即可）

1 2,3

2 3,3

3 4,10

3 5,20

4 6,3

5 6,3

6 7,6

6 8,10

6 11,2

7 11,9

8 9,14

8 10,10

9 11,10

10 11,10

11 12,3

11 13,3

11 14,4

12 15,5

13 15,3

14 15,10

15 16,20

16 17,17

6.5运行结果页面展示

6.5.1AOE输入信息图：

6.5.2图的邻接表示图：

6.5.3关键路径图和最短总工程时间：

七、总结与心得体会

在进行AOE拓扑排序程序设计开发过程中，我深刻体会到了以下几点：1. 计划和组织能力的重要性：在开始课程设计之前，我充分意识到了计划和组织的重要性。我制定了详细的计划和时间表，明确了每个阶段的任务和时间节点。我将整个课程设计分解为多个小任务，并合理安排了每个任务的时间和资源。这样，我能够更好地掌握整个项目的进度，及时调整和安排，确保项目的顺利进行。2. 需求分析的重要性：在进行课程设计之前，我进行了充分的需求分析。我与用户和相关人员进行了深入的沟通，了解了他们的需求和期望。我通过用户故事、用户画像等方式，对用户需求进行了详细的描述和分析。这样，我能够更好地理解用户的需求，确定关键功能和优先级，为后续的设计和开发提供了明确的方向。3. 设计思维的应用：在课程设计的过程中，我运用了设计思维的方法和工具。我通过用户故事、用户画像、原型设计等方式，深入理解用户需求，提出创新的解决方案。我将用户体验放在首位，注重用户的感受和需求，设计出更符合用户期望的解决方案。4. 团队合作的重要性：在进行课程设计的过程中，我与团队成员密切合作。我们共同讨论问题，提出解决方案，分工合作，共同努力实现项目的目标。我们通过有效的沟通和协作，解决了许多困难和问题。团队合作的力量是巨大的，它能够激发出团队成员的创造力和潜力，取得更好的成果。5. 测试和调试的重要性：在课程设计完成后，我进行了充分的测试和调试。我对程序进行了功能测试，确保程序的各个功能正常运行。我进行了性能测试，检查程序的性能是否满足需求。我进行了安全测试，确保程序的安全性和稳定性。通过测试和调试，我发现了一些问题，并及时进行了修复和优化，确保程序的正确性和可靠性。

总之，通过这次课程设计，我不仅学到了专业知识和技能，还培养了自己的计划和组织能力、分析和解决问题的能力、团队合作的能力等。我深刻体会到，课程设计是一个综合能力的考验，需要综合运用各种技能和方法，才能取得好的结果。同时，我也意识到，课程设计是一个不断学习和提升的过程，需要不断反思和总结，不断改进和完善自己。