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

1、 有向图的关键路径计算机与软件工程学院课程设计说明书课 程 名 称: 数据结构与算法课程设计 课 程 代 码: 题 目: 年级/专业/班: 学 生 姓 名: 学 号: 开 始 时 间: 2013 年 12 月 18 日完 成 时 间: 2013 年 12 月 28 日课程设计成绩：学习态度及平时成绩（20）技术水平与实际能力（20）完成情况(20)创新（5） 说明书（计算书、图纸、分析报告）撰写质量（35）总 分（100）指导教师签名： 年 月 日目 录 引 言11需求分析11.1任务与分析11.2测试数据12 概要设计32.1设计思路32.2层次图33 详细设计43.1主函数的实现43.2数

2、据录入实现53.3输出图的各顶点和弧的实现63.4计算各顶点的入度73.5输出关键路径74调试分析85用户使用说明96测试结果96.1录入数据96.2功能实现96.3测试结论11致 谢13参考文献14摘 要 具有最大路径长度的路径称关键路径，关键路径上的活动称关键活动。课程设计主要要求求有向图的关键路径。用领接表存储结构储存有向图。用深度遍历的方式输出有向图的顶点和弧。程序实现了存储有向图，输出有向图的各顶点和弧，计算顶点的入度和求有向图的关键路径这四个功能。用领接表存储结构储存有向图，用深度遍历的方式输出有向图的顶点和弧，用遍历查找的方式计算顶点的入度。求关键路径时先用拓扑排序函数判断有向图

3、是否有回路，调用求关键活动的函数找到关键路径，最后输出。关键词：领接表；入度；AOE网；关键路径； 引 言 工程有很多的阶段，这些阶段之间有一定的先后关系和自己的时间。我们可以用图来表示工程，将其输入程序中，可以用程序计算出工程的相关信息，如，工程完成的最短时间，哪些活动会影响工程的进度等。要解决这些问题就可以用领接表储存图，并计算各个事件和各个阶段的最早发生时间和最晚发生时间，得到关键活动，从而的到关键路径。1需求分析从键盘上输入图的各顶点和弧上的权值，用领接表储存。在屏幕上输出图的顶点和弧。计算输出顶点的入度。如果图是AOE网，输出关键路径。1.1任务与分析 1、 首先定义边节点和顶点的结

4、构体，将输入的数据用链接表储存起来，领接表即是顺序+链式的存储方式。将顶点顺序储存，将该顶点为起点的弧指向的另一顶点及其相关信息存储在链表中。2、 采用深度遍历的方式，输出顶点和弧。3、 判断顶点是否在弧尾，在弧尾就在入度的计数变量上加一。4、 首先要将图进行拓扑排序，看是否有回路，没有回路才能求关键路径。求AOE网的关键路径要先求到各个事件的最早发生时间和最迟发生时间，再求有向边的最早和最迟发生时间，活动的最晚发生时间和最早发生时间相减等于0时，该活动即为关键活动，再将关键活动按顺序连起来极为关键路径。1.2测试数据 带权有向图测试数据如下：测试数据1如图1-1：图1-1测试图1测试数据2如

5、图1-2：图1-2 测试图2测试数据3如图1-3：图1-2 测试图32 概要设计 2.1设计思路程序分总的来说分为四大功能模块：输入储存；输出顶点和弧；输出各顶点的入度；输出关键路径。在输出关键路径的模块中包括：拓扑排序判断是否有回路；计算各事件的最早发生时间和最晚发生时间；求活动的最晚发生时间，判断该活动是否是关键活动；输出关键路径。首先调用输入存储模块创建图，用菜单工作的方式来实现对各个输出功能模块的调用。输入储存：ALGraph<T>:ALGraph(T a , int n, int e)输出顶点和弧：void Print(); 输出各顶点的入度：void indegree(

6、)；输出关键路径：void critical_path(ALGraph G)；输出关键路径模块中的子模块：拓扑排序：void TopSort(ALGraph G);事件的时间：void vv(ALGrapph G);判断是否是关键活动：void keyEvent(ALGraph G);2.2层次图各模块间的层次如图2-1：图2-1 各模块间的层次图3 详细设计3.1主函数的实现首先输入图的顶点的个数和边的个数，程序通过输入的数来判断要创建的图的大小，调用图的构造函数，输入图的相关信息。之后，为了方便用户操作，用工作菜单的方式来实现对各个功能的调用。void main() int n,e;int

7、 choose=1;/控制int which;/功能选择变量string *vname;/MaxSize;cout<<"请输入图的顶点数："cin>>n;while(n<0|n>20)cout<<"顶点个数应在-20之间！请重新输入！"<<endl;cin>>n;cout<<"请输入图的边数："cin>>e;while(e<0)cout<<"您输入的顶点个数小于零！请重新输入！"<<endl

8、;cin>>e;vname=new stringn;cout<<"请输入顶点："for(int j=0;j<n;j+)cin>>vnamej;ALGraph<string> g(vname, n, e);while(choose=1)cout<<"-"<<endl;cout<<"n1*-输出该有有向图的个顶点和弧-*"cout<<"n2*-计算各顶点的入度-*"cout<<"n3*-计算AOE

9、网的关键路径-*"cout<<"n4*-退出-*-*"<<endl;cout<<"-"<<endl;cin>>which;switch(which)case 1:g.Print();break;case 2:g.indegree();break;case 3:g.critical_path();break;case 4:choose=0;break;3.2数据录入实现定义边表节点和顶点表节点。struct ArcNode int adjvex,weight; ArcNode *next

10、;template <class T>struct VertexNode T vertex;int in;ArcNode *firstedge;用构造函数实现数据的录入，录入时根据程序的提示录入数据。ALGraph<T>:ALGraph(T a , int n, int e)vertexNum=n; arcNum=e;int i,j,k,w;for (i=0; i<vertexNum; i+) adjlisti.vertex=ai;adjlisti.firstedge=NULL; for (k=0; k<arcNum; k+) cout<<&qu

11、ot;请输入图中弧的起始点及权值：其格式为<起点，终点，权值>"cin>>i>>j>>w; ArcNode *s;s=new ArcNode; s->adjvex=j;s->weight=w;s->next=adjlisti.firstedge; adjlisti.firstedge=s;3.3输出图的各顶点和弧的实现对图进行深度遍历，输出顶点和弧。void ALGraph<T>:Print() /输出有向图的个顶点和弧for(int i=0;i<vertexNum;i+)ArcNode *p;p=a

12、djlisti.firstedge;while(p)cout<<adjlisti.vertex<<"->"int j;j=p->adjvex;cout<<adjlistj.vertex<<'t'<<"权值："<<p->weight<<endl;p=p->next;3.4计算各顶点的入度用双重循环，外层循环找到各个顶点，内层循环计算有几条弧指向外层循环中的顶点，用累加器累加，最后累加器得到的数就是该顶点的入度。void ALGraph

13、<T>:indegree() /输出每个顶点的入度ArcNode *p;int count;for(int i=0;i<vertexNum;i+)count=0;for(int j=0;j<vertexNum;j+)if(j!=i)p=adjlistj.firstedge;while(p)if(p->adjvex=i) count+;p=p->next;else continue;adjlisti.in=count;cout<<adjlisti.vertex<<"的入度为："<<adjlisti.in&

14、lt;<endl;3.5输出关键路径首先，调用拓扑排序判断有向图中是否回路，有回路不能求关键路径，没有回路则求关键路径。先调用vv函数求顶点的最早发生时间和最迟发生时间，在调用keyEvent函数找到关键活动，再将关键路径串起来输出。void ALGraph<T>:critical_path()int tsMaxSize,veMaxSize,vlMaxSize;if(TopSort(ts)=0)cout<<"有关键路径！"<<endl;int k,v;k=ts0;vv(ve,vl,ts);keyEvent(ve,vl,ts);cou

15、t<<"关键路径："<<endl;cout<<adjlistk.vertex;for(int i=0;i<10;i+)if(evi.v1=k)v=evi.v2;cout<<"->"<<adjlistv.vertex;k=evi.v2;cout<<endl;elsecout<<"，没有关键路径！"<<endl;4调试分析问题1：在类中定义私有成员int ts，用来储存经过拓扑排序后的顶点的编号，但在拓扑排序的函数中无法对数组进行写

16、入。分析及解决方法：没有想明白是什么原因。直接在调用拓扑排序函数是传入数组ts来代替类的私有成员int ts来储存经过拓扑排序后的顶点的编号。问题2：在运行求事件的最早发生时间和最迟发生时间的函数时，发生读写位置冲突的问题。分析及解决方法：经检查后发现是传入的用来储存事件最早发生时间和最迟发生时间的数组ve和vl没有进行初始化。用for循环语句对两个数组进行初始化。问题3：当调用求关键路径的方法时程序运行到一半时不再运行。分析及解决方法：经调试后发现是求顶点的最早发生时间和最迟发生时间的vv函数的while循环中少写了P=P->next语句导致出现了死循环。在while循环中加上P=P-

17、>next语句。5用户使用说明按照提示输入数据后，在菜单出现后，从键盘输入功能的编号就可以实现不同的功能。简单，方便，易操作。6测试结果用测试数据1进行测试。6.1录入数据从键盘上输入顶点的个数，边的条数，再根据提示输入顶点、边、权值，用领接表来进行储存。如图6-1所示：图6-1 录入存储6.2功能实现根据菜单选择功能。测试输出各顶点和弧的功能，结果如图6-2所示。图6-2 输出顶点和弧测试计算各顶点的入度功能，结果如图6-3所示。图6-3 计算各顶点的入度测试计算AOE网的关键路径的功能，结果如图6-4所示。图6-4 计算AOE网的关键路径6.3测试结论通过测试得知该程序实现了需求中的

18、所有功能。测试的结果完全符合预期结果。结 论 通过这次实训，使我学到了很多。由于求关键路径的算法在上课时没有深入学习，课后没有重视关键路径这块基本上没有理解，我在编程中遇到了很多困难，但在攻克困难的过程中提高了自己的自学能力，分析问题及解决问题的能力、熟练运用理论知识的能力。同时，让我更深入的掌握了有关求AOE网关键路径等方面的知识，巩固了所学内容。我从这次课程设计中所得的另外一个很大的收获是：不能因为问题难就逃避它，只有勇于尝试才可能解决根本问题。数据结构这门课程对我们学习好这个专业很重要，在以后，我会尽量利用我的空闲时间把以前不熟的和掌握不牢固的知识点再学习一遍。尽管这次的实习是独立的个人工作，但在完成课程设计遇到困难时，也得到了很多老师的指导和同学的帮助。然我明白了合作的重要性。在实训过程中收获了很多的丰富的经验知识，更加深了我对一些算法和新知识的理解与应用，让我受益匪浅。在实训中认识自己不足的地方。自己了解一些算法，但是在具体编程的时候不会应用。写的程序复杂度高，效率低下。因此，在以后的学习中我会更加注重学以致用。 致 谢 感谢有这次实训的机会。通过这