数据结构拓扑排序和关键路径的求解

1、 数据结构课程设计大作业 题 目拓扑排序和关键路径的求解专 业 计算机科学与技术 学生姓名 学 号 指导教师 完成日期 2015.3 哈尔滨理工大学目 录一：实验内容概述2二：实验目的概述2三：解题思路的描述3四：源程序清单6五：程序调试及测试结果11六：结论13七：参考文献13拓扑排序和关键路径的求解【内容摘要】建立一个AOV网，把对象与对象之间的关系在AOV网中体现出来，要注意AOV网不可以建立成环的形式，否则工程将无法进行。之后对建立的网进行拓扑排序。对于一个工程来说，不仅要关心各子工程的之间的先后关系，还要关系整个工程的最短时间，即有向带权图的关键路径问题。在描述关键路径问题的有向图时

2、，顶点表示事件，便表示活动，边上的权表示活动所需的时间，即此有向图为AOE网。对AOV网构造其所有定点的线性序列，此序列保持网中各顶点间原有的先后关系，且是原来没有先后关系的顶点也成为有先后关系，这样的线性序列称为拓扑有序序列，构造AOV网的拓扑有序序列操作称为拓扑排序。在AOE网中有些活动可以并行地进行，所以完成整个工程的最短时间是从源点到汇点的最长路径的长度，路径长度是路径各边的权值之和，把从源点到汇点的最长路径称为关键路径。【关键字】AOE网 拓扑排序 关键路径 The topological sort and critical path method【Abstract】Establis

3、h a AOV nets, the relationship between the object and the object in AOV nets reflected in AOV nets, should pay attention to the form of can't establish cyclization, otherwise the project will not be able to do so. After the nets to establish topological sort.For a project, it should not only abo

4、ut the relationship between the construction of the project, the shortest time relationship, which is the key to the weighted graph routing problem. In the description of the critical path problem digraph, vertices, then said that events, the right side of the time needed to denote activities, namel

5、y, this is to the net. AOE For all its designated AOV network structure, the sequence of linear sequence of each vertex keep the relationship between the original and is originally has no successively relationship has become a vertex, such as linear topological orderly sequences, AOV tectonic sequen

6、ces of topological orderly sequences operation called topological sort. In some activity can AOE net parallel to complete the whole project, so the shortest time from point of origin to the length of the longest path sinks, path length is the path to the sum of the weights, from the point of origin

7、to the longest path called zhonghua critical path.【Key words】AOE net Topological sort The key path 一：实验内容概述采用图的邻接表（出边表）表示方法，实现拓扑排序和关键路径的求解过程。使用实现的算法对于图的AOE网，求出各活动的可能的最早开始时间和最晚开始时间。输出整个工程的最短完成时间是多少？哪些活动是关键活动？说明哪项活动提高速度后能导致整个工程提前完成。二：实验目的概述 AOE网是一个带权的有向无环图，其中，顶点表示事件，弧表示活动，权表示活动持续的时间。在AOE网络中, 有些活动顺序进行，

8、有些活动并行进行。由于整个工程只有一个开始点和一个完成点，故在正常情况下（无环），网中只有一个入度为零的点（称作源点）和一个出度为零的点（叫做汇点）.如图1 图1AOE网络在某些工程估算方面非常有用，为了进行人力、物力的调度和分配，以缩短工期，我们必须找出影响工程进度的关键活动，争取提高关键活动的功效，若网中有多条关键路径那么只提高一条关键路径上的关键活动的速度还不能导致整个工程缩短工期，还必须提高同时在所有关键路径上的活动的速度，因此必须求出所有关键路径。三：解题思路的描述从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同

9、，但只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。要找出关键路径，必须找出关键活动，即不按期完成就会影响整个工程完成的活动。 事件Vi的最早开始时间Ve(i)为源点V1到Vi的最长路径长度。活动ai的最早开始时间e(i)，活动ai 的最迟开始时间l(i),e(i)=l(i)的活动叫做关键活动。关键路径上的所有活动都是关键活动。因此，只要找到了关键活动，就可以找到。例如，下图是一个有11项活动的AOE-网。其中有9个事件V1,

10、V2,V9,每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如V1表示整个工程开始，V9表示整个工程结束，V5表示活动a4和a5已经完成，活动a7和a8可以开始。与每个活动相联系的数指的是执行该活动所需的时间。如，活动a1需要6天，活动a4需要1天等等。 从源点到汇点的关键路径为：V1，V2，V5，V8，V9，路径长度为18，即活动V9的最早发生时间是18。活动a6的最早开始时间是5，最迟开始时间是8，这意味着：活动a6推迟3天开始或者延迟3天完成，都不会影响这个工程的完成。分析：关键路径上的所有活动都是关键活动，只有提高关键活动的效率，才能缩短整个工期。提前完成非关键活动并不能加

11、快工程进度。辨别关键活动就是找l(i)=e(i)的活动。要得到活动的l(i)和e(i)，必须先计算事件的最早和最迟发生时间ve和vl。关键路径举例找出图一中的关键路径！为了找出关键路径，需要找出关键活动；因此需要计算每个事件、每个活动的最早开始时间和最晚开始时间。最早开始时间需要从源点开始正向的进行计算，而最晚开始时间需要从汇点逆向的开始计算。（a）（b）（c） 图二：关键路径的算法： 1  入e条弧j,k，建立AOE-网的存储结构； 2从源点V0出发，令ve0=0，按拓扑有序求其余各顶点的最早发生时间veI(1in-1)。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中

12、存在环，不能求关键路径，算法终止；否则执行步骤（3）。 3从汇点vn出发，令vln-1=ven-1,按逆拓扑有序求其余各顶点的最迟发生时间vlI(n-2i0)；      4根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足条件e(s)=l(s),则为关键活动。Status criticalpath(algraph g) /G为有向网，输出G的各项关键活动。 If (!topologicalorder(G,t) return ERROR; Vl0.G.vexnum-1=veG.vexnum-1; /初始化顶点事

13、件的最迟发生时间 While (!stackempty(t) / 按拓扑逆序求各项点的vl值 For (pop(t,j),p=g.vexticesj.firstarc;p;p=p->nextarc) K=p->adjvex;dut=*(p->info); /dutj,k If (vlk-dut<vlj) vlj=vlk-dut; for (j=0;j<g.vexnum;+j) /求ee,el和关键活动 for (p=g.verticesj).firstarc;p;p=p->nextarc) k=p->adjvex;dut=*(p->info);

14、ee=vej;el=vlk-dut; tag=(ee=el)?*:”; printf(j,k,dut,ee,el,tag); /输出关键活动 /criticalpath 四：源程序清单#include<stdio.h>#include<stdlib.h>#include <process.h>#include <ctype.h>typedef struct node /边表结点类型 int adjvex; /顶点的序号int dut; /边上的权值struct node *next; /指向下一条边的指针edgenode;typedef stru

15、ct /顶点表结点 int projectname; /顶点域int id; /顶点入度edgenode *link; /边表头指针vexnode;/建立图存储结构void CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber) /projectnumber为工程的节点数，activenumber int begin,end,duttem; edgenode *p; for(int i=0;i<projectnumber;i+) Gjectname=i; Graphicmapi

16、.id =0; Graphicmapi.link =NULL; printf("某项目的开始到结束在图中的工程输入<vi,vj,dut>n"); printf("如：1 3 6 回车表示第一个工程到第三各工程之间的活动用了6个小时n"); for(int k=0;k<activenumber;k+) scanf("%d %d %d",&begin,&end,&duttem); p=(edgenode*)malloc(sizeof(edgenode); p->adjvex =end-1;

17、/将邻接点序号j赋给新结点的邻接点域 p->dut =duttem; Graphicmapend-1.id +; / 将入度加1 p->next =Graphicmapbegin-1.link ; Graphicmapbegin-1.link =p; /将新结点插入到顶点vi的边表头部/求关键路径int SearchMapPath(vexnode* Graphicmap,int projectnumber,int activenumber,int& totaltime) int i,j,k,m=0; int front=-1,rear=-1; int* topologyst

18、ack=(int*)malloc(projectnumber*sizeof(int) ; /用来保存拓扑排列 int* vl=(int*)malloc(projectnumber*sizeof(int); /用来表示在不推迟整个工程的前提下，VJ允许最迟发生的时间 int* ve=(int*)malloc(projectnumber*sizeof(int); /用来表示Vj最早发生时间 int* l=(int*)malloc(activenumber*sizeof(int); int* e=(int*)malloc(activenumber*sizeof(int); /表示活动最早开始时间 e

19、dgenode *p; totaltime=0; for(i=0;i<projectnumber;i+)vei=0; for(i=0;i<projectnumber;i+) if(Graphicmapi.id=0) topologystack+rear=i;m+; while(front!=rear) front+; j=topologystackfront; m+; p=Graphicmapj.link ; while(p) k=p->adjvex ; Graphicmapk.id -; if(vej+p->dut >vek) vek=vej+p->dut

20、 ; if(Graphicmapk.id =0) topologystack+rear=k; p=p->next ; if(m<projectnumber) printf("n本程序所建立的图有回路不可计算出关键路径n"); printf("将退出本程序n"); return 0; totaltime=veprojectnumber-1; for(i=0;i<projectnumber;i+) vli=totaltime; for(i=projectnumber-2;i>=0;i-) j=topologystacki; p=Gra

21、phicmapj.link ; while(p) k=p->adjvex ; if(vlk-p->dut )<vlj) vlj=vlk-p->dut ; p=p->next ; i=0;printf("| 起点 | 终点 | 最早开始时间 | 最迟完成时间 | 差值 | 备注 |n"); for(j=0;j<projectnumber;j+) p=Graphicmapj.link; while(p) k=p->adjvex ; e+i=vej; li=vlk-p->dut; printf("| %5d | %5d |

22、 %5d | %5d | %5d |",Gjectname+1,Gjectname +1,ei,li,li-ei); if(li=ei) printf(" 关键活动 |"); printf("n"); p=p->next ; return 1; /寻找关键路径void seekkeyroot() int projectnumber,activenumber,totaltime=0; system("cls"); printf("请输入这个工程个数:&qu

23、ot;); scanf("%d",&projectnumber); printf("请输入这个工程和工程之间的边数:"); scanf("%d",&activenumber); vexnode* Graphicmap=(vexnode*)malloc(projectnumber*sizeof(vexnode); CreateGraphic(Graphicmap,projectnumber,activenumber); SearchMapPath(Graphicmap,projectnumber,activenumber

24、,totaltime); printf("整个工程所用的最短时间为：%d个小时n",totaltime); system("pause"); int main() char ch; for(;) do system("cls"); printf(" =n"); printf(" | 欢迎进入求关键路径算法程序 |n"); printf("%s"," (S)tart开始输入工程数据并求出关键路径n"); printf("%s"," (E)xit退出!n"); printf(" =n"); printf("%s"," 请输入选择(S,E):"); scanf("%c",&ch); ch=toupper(ch); while(ch!=&#