有向图的关键路径计算机与软件工程学院课程设计说明书课程名称: 数据结构与算法课程设计课程代码:题目:年级/专业/班:学生姓名:学号:开始时间:2016 年 5 月8 日完成时间:2016 年5月18 日课程设计成绩：指导教师签名：年月日目录引言 (1)1需求分析 (1)1.1任务与分析 (1)1.2测试数据 (1)2 概要设计 (3)2.1设计思路 (3)2.2层次图 (3)3 详细设计 (4)3.1主函数的实现 (4)3.2数据录入实现 (5)3.3输出图的各顶点和弧的实现 (6)3.4计算各顶点的入度 (7)3.5输出关键路径 (8)4调试分析 (8)5用户使用说明 (9)6测试结果 (9)6.1录入数据 (9)6.2功能实现 (10)6.3测试结论 (11)致谢 (13)参考文献 (14)摘要具有最大路径长度的路径称关键路径，关键路径上的活动称关键活动。
课程设计主要要求求有向图的关键路径。
用领接表存储结构储存有向图。
用深度遍历的方式输出有向图的顶点和弧。
程序实现了存储有向图，输出有向图的各顶点和弧，计算顶点的入度和求有向图的关键路径这四个功能。
用领接表存储结构储存有向图，用深度遍历的方式输出有向图的顶点和弧，用遍历查找的方式计算顶点的入度。
求关键路径时先用拓扑排序函数判断有向图是否有回路，调用求关键活动的函数找到关键路径，最后输出。
关键词：领接表；入度；AOE网；关键路径；有向图的关键路径引言工程有很多的阶段，这些阶段之间有一定的先后关系和自己的时间。
我们可以用图来表示工程，将其输入程序中，可以用程序计算出工程的相关信息，如，工程完成的最短时间，哪些活动会影响工程的进度等。
要解决这些问题就可以用领接表储存图，并计算各个事件和各个阶段的最早发生时间和最晚发生时间，得到关键活动，从而的到关键路径。
1需求分析从键盘上输入图的各顶点和弧上的权值，用领接表储存。
在屏幕上输出图的顶点和弧。
计算输出顶点的入度。
如果图是AOE网，输出关键路径。
1.1任务与分析1、首先定义边节点和顶点的结构体，将输入的数据用链接表储存起来，领接表即是顺序+链式的存储方式。
将顶点顺序储存，将该顶点为起点的弧指向的另一顶点及其相关信息存储在链表中。
2、采用深度遍历的方式，输出顶点和弧。
3、判断顶点是否在弧尾，在弧尾就在入度的计数变量上加一。
4、首先要将图进行拓扑排序，看是否有回路，没有回路才能求关键路径。
求AOE网的关键路径要先求到各个事件的最早发生时间和最迟发生时间，再求有向边的最早和最迟发生时间，活动的最晚发生时间和最早发生时间相减等于0时，该活动即为关键活动，再将关键活动按顺序连起来极为关键路径。
1.2测试数据带权有向图测试数据如下：测试数据1如图1-1：图1-1测试图1测试数据2如图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()；输出关键路径：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 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;cin>>e;}vname=new string[n];cout<<"请输入顶点：";for(int j=0;j<n;j++){cin>>vname[j];}ALGraph<string> g(vname, n, e);while(choose==1){cout<<"-------------------------------------------------------"<< endl;cout<<"\n1******-------输出该有有向图的个顶点和弧--******";cout<<"\n2******-------计算各顶点的入度--------------******";cout<<"\n3******-------计算AOE网的关键路径------------******";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;};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++){adjlist[i].vertex=a[i];adjlist[i].firstedge=NULL;}for (k=0; k<arcNum; k++){cout<<"请输入图中弧的起始点及权值：其格式为<起点，终点，权值>";cin>>i>>j>>w;ArcNode *s;s=new ArcNode;s->adjvex=j;s->weight=w;s->next=adjlist[i].firstedge;adjlist[i].firstedge=s;}}3.3输出图的各顶点和弧的实现对图进行深度遍历，输出顶点和弧。
void ALGraph<T>::Print() //输出有向图的个顶点和弧{for(int i=0;i<vertexNum;i++){ArcNode *p;p=adjlist[i].firstedge;while(p){cout<<adjlist[i].vertex<<"---->";int j;j=p->adjvex;cout<<adjlist[j].vertex<<'\t'<<"权值："<<p->weight<<endl;p=p->next;}}}3.4计算各顶点的入度用双重循环，外层循环找到各个顶点，内层循环计算有几条弧指向外层循环中的顶点，用累加器累加，最后累加器得到的数就是该顶点的入度。
void ALGraph<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=adjlist[j].firstedge;while(p){if(p->adjvex==i) count++;p=p->next;}}else continue;}adjlist[i].in=count;cout<<adjlist[i].vertex<<"的入度为："<<adjlist[i].in<<endl;}}3.5输出关键路径首先，调用拓扑排序判断有向图中是否回路，有回路不能求关键路径，没有回路则求关键路径。
先调用vv函数求顶点的最早发生时间和最迟发生时间，在调用keyEvent函数找到关键活动，再将关键路径串起来输出。
void ALGraph<T>::critical_path(){int ts[MaxSize],ve[MaxSize],vl[MaxSize];if(TopSort(ts)==0){cout<<"有关键路径！"<<endl;int k,v;k=ts[0];vv(ve,vl,ts);keyEvent(ve,vl,ts);cout<<"关键路径："<<endl;cout<<adjlist[k].vertex;for(int i=0;i<10;i++){if(ev[i].v1==k){v=ev[i].v2;cout<<"->"<<adjlist[v].vertex;k=ev[i].v2;}}cout<<endl;}else{cout<<"，没有关键路径！"<<endl;}}4调试分析问题1：在类中定义私有成员int ts[]，用来储存经过拓扑排序后的顶点的编号，但在拓扑排序的函数中无法对数组进行写入。