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

有向图的关键路径计算机与软件工程学院课程设计说明书课 程 名 称: 数据结构与算法课程设计 课 程 代 码: 题 目: 年级/专业/班: 学 生 姓 名: 学 号: 开 始 时 间: 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 数据录入实现 .53.3 输出图的各顶点和弧的实现 .63.4 计算各顶点的入度 .73.5 输出关键路径 .74 调试分析 .85 用户使用说明 .96 测试结果 .96.1 录入数据 .96.2 功能实现 .96.3 测试结论 .11致 谢 .13参考文献 .14有向图的关键路径摘 要 具有最大路径长度的路径称关键路径，关键路径上的活动称关键活动。课程设计主要要求求有向图的关键路径。用领接表存储结构储存有向图。用深度遍历的方式输出有向图的顶点和弧。程序实现了存储有向图，输出有向图的各顶点和弧，计算 顶点的入度和求有向图的关键路径这四个功能。用领接表存储结构储存有向图，用深度遍历的方式输出有向图的顶点和弧，用遍历查找的方式计算顶点的入度。求关键路径时先用拓扑排序函数判断有向图是否有回路，调用求关键活动的函数找到关键路径，最后输出。关键词：领接表；入度；AOE 网；关键路径； 有向图的关键路径引 言 工程有很多的阶段，这些阶段之间有一定的先后关系和自己的时间。我们可以用图来表示工程，将其输入程序中，可以用程序计算出工程的相关信息，如，工程完成的最短时间，哪些活动会影响工程的进度等。要解决这些问题就可以用领接表储存图，并计算各个事件和各个阶段的最早发生时间和最晚发生时间，得到关键活动，从而的到关键路径。1 需求分析从键盘上输入图的各顶点和弧上的权值，用领接表储存。在屏幕上输出图的顶点和弧。计算输出顶点的入度。如果图是 AOE 网，输出关键路径。1.1 任务与分析 1、首先定义边节点和顶点的结构体，将输入的数据用链接表储存起来，领接表即是顺序+链式的存储方式。将顶点顺序储存，将该顶点为起点的弧指向的另一顶点及其相关信息存储在链表中。2、采用深度遍历的方式，输出顶点和弧。3、判断顶点是否在弧尾，在弧尾就在入度的计数变量上加一。4、首先要将图进行拓扑排序，看是否有回路，没有回路才能求关键路径。求 AOE 网的关键路径要先求到各个事件的最早发生时间和最迟发生时间，再求有向边的最早和最迟发生时间，活动的最晚发生时间和最早发生时间相减等于0 时，该活动即为关键活动，再将关键活动按顺序连起来极为关键路径。1.2 测试数据 带权有向图测试数据如下：测试数据 1 如图 1-1：有向图的关键路径2V 0V 1V 2V 5V 6V 7V 3V 8V464512792414图 1-1 测试图 1测试数据 2 如图 1-2：V 0 V 1V 2 V 32564图 1-2 测试图 2测试数据 3 如图 1-3：V 0 V 1V 2 V 3564图 1-2 测试图 3有向图的关键路径32 概要设计 2.1 设计思路程序分总的来说分为四大功能模块：输入储存；输出顶点和弧；输出各顶点的入度；输出关键路径。在输出关键路径的模块中包括：拓扑排序判断是否有回路；计算各事件的最早发生时间和最晚发生时间；求活动的最晚发生时间，判断该活动是否是关键活动；输出关键路径。首先调用输入存储模块创建图，用菜单工作的方式来实现对各个输出功能模块的调用。输入储存：ALGraph:ALGraph(T a , int n, int e)输出顶点和弧：void Print(); 输出各顶点的入度：void indegree()；输出关键路径：void critical_path(ALGraph G)；输出关键路径模块中的子模块：拓扑排序：void TopSort(ALGraph G);事件的时间：void vv(ALGrapph G);判断是否是关键活动：void keyEvent(ALGraph G);2.2 层次图各模块间的层次如图 2-1：有向图的关键路径4计算顶点的入度输出关键路径输入储存输出各顶点和弧有向图的关键计算事件的最早和最晚发生时间找关键活动图 2-1 各模块间的层次图3 详细设计3.1 主函数的实现首先输入图的顶点的个数和边的个数，程序通过输入的数来判断要创建的图的大小，调用图的构造函数，输入图的相关信息。之后，为了方便用户操作，用工作菜单的方式来实现对各个功能的调用。void main() int n,e;int choose=1;/控制int which;/功能选择变量string *vname;/MaxSize;coutn;while(n20)coutn;coute;while(ee;有向图的关键路径5vname=new stringn;coutvnamej;ALGraph g(vname, n, e);while(choose=1)coutwhich;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;template 有向图的关键路径6struct VertexNode T vertex;int in;ArcNode *firstedge;用构造函数实现数据的录入，录入时根据程序的提示录入数据。ALGraph:ALGraph(T a , int n, int e)vertexNum=n; arcNum=e;int i,j,k,w;for (i=0; i“;cinijw; ArcNode *s;s=new ArcNode; s-adjvex=j;s-weight=w;s-next=adjlisti.firstedge; adjlisti.firstedge=s;3.3 输出图的各顶点和弧的实现对图进行深度遍历，输出顶点和弧。void ALGraph:Print() /输出有向图的个顶点和弧for(int i=0;i“;int j;j=p-adjvex;coutweightnext;3.4 计算各顶点的入度用双重循环，外层循环找到各个顶点，内层循环计算有几条弧指向外层循环中的顶点，用累加器累加，最后累加器得到的数就是该顶点的入度。void ALGraph:ind