C--实现关键路径算法课程设计报告

有向图的关键路径计算机与软件工程学院课程设计说明书课程名称:数据结构与算法课程设计课程代码:题目:年级/专业/班:学生姓名:学号:开始时间:2016年5月8日完成时间:2016年5月18日课程设计成绩：学习态度及平时成绩（20）技术水平与实际能力（20）完成情况(20)创新（5）说明书（计算书、图纸、分析报告）撰写质量（35）总分（100）指导教师签名：年月日有向图的关键路径目录引言............................................................................................................................11需求分析.....................................................................................................................11.1任务与分析......................................................................................................11.2测试数据..........................................................................................................12概要设计....................................................................................................................32.1设计思路..........................................................................................................32.2层次图..............................................................................................................33详细设计....................................................................................................................43.1主函数的实现..................................................................................................43.2数据录入实现..................................................................................................53.3输出图的各顶点和弧的实现..........................................................................63.4计算各顶点的入度..........................................................................................73.5输出关键路径..................................................................................................84调试分析.....................................................................................................................85用户使用说明.............................................................................................................96测试结果.....................................................................................................................96.1录入数据..........................................................................................................96.2功能实现........................................................................................................106.3测试结论........................................................................................................11致谢..........................................................................................................................13参考文献......................................................................................................................14有向图的关键路径摘要具有最大路径长度的路径称关键路径，关键路径上的活动称关键活动。课程设计主要要求求有向图的关键路径。用领接表存储结构储存有向图。用深度遍历的方式输出有向图的顶点和弧。程序实现了存储有向图，输出有向图的各顶点和弧，计算顶点的入度和求有向图的关键路径这四个功能。用领接表存储结构储存有向图，用深度遍历的方式输出有向图的顶点和弧，用遍历查找的方式计算顶点的入度。求关键路径时先用拓扑排序函数判断有向图是否有回路，调用求关键活动的函数找到关键路径，最后输出。关键词：领接表；入度；AOE网；关键路径；有向图的关键路径1引言工程有很多的阶段，这些阶段之间有一定的先后关系和自己的时间。我们可以用图来表示工程，将其输入程序中，可以用程序计算出工程的相关信息，如，工程完成的最短时间，哪些活动会影响工程的进度等。要解决这些问题就可以用领接表储存图，并计算各个事件和各个阶段的最早发生时间和最晚发生时间，得到关键活动，从而的到关键路径。1需求分析从键盘上输入图的各顶点和弧上的权值，用领接表储存。在屏幕上输出图的顶点和弧。计算输出顶点的入度。如果图是AOE网，输出关键路径。1.1任务与分析1、首先定义边节点和顶点的结构体，将输入的数据用链接表储存起来，领接表即是顺序+链式的存储方式。将顶点顺序储存，将该顶点为起点的弧指向的另一顶点及其相关信息存储在链表中。2、采用深度遍历的方式，输出顶点和弧。3、判断顶点是否在弧尾，在弧尾就在入度的计数变量上加一。4、首先要将图进行拓扑排序，看是否有回路，没有回路才能求关键路径。求AOE网的关键路径要先求到各个事件的最早发生时间和最迟发生时间，再求有向边的最早和最迟发生时间，活动的最晚发生时间和最早发生时间相减等于0时，该活动即为关键活动，再将关键活动按顺序连起来极为关键路径。1.2测试数据带权有向图测试数据如下：测试数据1如图1-1：有向图的关键路径2V0V1V2V5V6V7V3V8V464512792414图1-1测试图1测试数据2如图1-2：V0V1V2V32564图1-2测试图2测试数据3如图1-3：V0V1V2V3564图1-2测试图3有向图的关键路径32概要设计2.1设计思路程序分总的来说分为四大功能模块：输入储存；输出顶点和弧；输出各顶点的入度；输出关键路径。在输出关键路径的模块中包括：拓扑排序判断是否有回路；计算各事件的最早发生时间和最晚发生时间；求活动的最晚发生时间，判断该活动是否是关键活动；输出关键路径。首先调用输入存储模块创建图，用菜单工作的方式来实现对各个输出功能模块的调用。输入储存：ALGraphT::ALGraph(Ta[],intn,inte)输出顶点和弧：voidPrint();输出各顶点的入度：voidindegree()；输出关键路径：voidcritical_path(ALGraphG)；输出关键路径模块中的子模块：拓扑排序：voidTopSort(ALGraphG);事件的时间：voidvv(ALGrapphG);判断是否是关键活动：voidkeyEvent(ALGraphG);2.2层次图各模块间的层次如图2-1：有向图的关键路径4计算顶点的入度输出关键路径输入储存输出各顶点和弧有向图的关键计算事件的最早和最晚发生时间找关键活动图2-1各模块间的层次图3详细设计3.1主函数的实现首先输入图的顶点的个数和边的个数，程序通过输入的数来判断要创建的图的大小，调用图的构造函数，输入图的相关信息。之后，为了方便用户操作，用工作菜单的方式来实现对各个功能的调用。voidmain(){intn,e;intchoose=1;//控制intwhich;//功能选择变量string*vname;//[MaxSize];cout请输入图的顶点数：;cinn;while(n0||n20){cout顶点个数应在-20之间！请重新输入！endl;cinn;}cout请输入图的边数：;cine;while(e0){cout您输入的顶点个数小于零！请重新输入！endl;cine;}有向图的关键路径5vname=newstring[n];cout请输入顶点：;for(intj=0;jn;j++){cinvname[j];}ALGraphstringg(vname,n,e);while(choose==1){cout-------------------------------------------------------endl;cout\n1******-------输出该有有向图的个顶点和弧--******;cout\n2******-------计算各顶点的入度--------------******;cout\n3******-------计算AOE网的关键路径------------******;cout\n4******-------退出--*******---------------******endl;cout-------------------------------------------------------endl;cinwhich;switch(which){case1:g.Print();break;case2:g.indegree();break;case3:g.critical_path();break;case4:choose=0;break;}}}3.2数据录入实现定义边表节点和顶点表节点。structArcNode{intadjvex,weight;ArcNode*next;有向图的关键路径6};templatec