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

数据结构课程设计大作业

题 目拓扑排序和关键路径的求解
专 业 计算机科学与技术
学生姓名
学 号
指导教师
完成日期 2015.3

哈尔滨理工大学
目 录

一：实验内容概述 2
二：实验目的概述 2
三：解题思路的描述 3
四：源程序清单 6
五：程序调试及测试结果 11
六：结论 13
七：参考文献 13

拓扑排序和关键路径的求解

【内容摘要】建立一个AOV网，把对象与对象之间的关系在AOV网中体现出来，要注意AOV网不可以建立成环的形式，否则工程将无法进行。之后对建立的网进行拓扑排序。对于一个工程来说，不仅要关心各子工程的之间的先后关系，还要关系整个工程的最短时间，即有向带权图的关键路径问题。在描述关键路径问题的有向图时，顶点表示事件，便表示活动，边上的权表示活动所需的时间，即此有向图为AOE网。对AOV网构造其所有定点的线性序列，此序列保持网中各顶点间原有的先后关系，且是原来没有先后关系的顶点也成为有先后关系，这样的线性序列称为拓扑有序序列，构造AOV网的拓扑有序序列操作称为拓扑排序。在AOE网中有些活动可以并行地进行，所以完成整个工程的最短时间是从源点到汇点的最长路径的长度，路径长度是路径各边的权值之和，把从源点到汇点的最长路径称为关键路径。

【关键字】AOE网 拓扑排序 关键路径

The topological sort and critical path method
【Abstract】Establish 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 about 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, namely, 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 sequences 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 to the longest path called zhonghua critical path.
【Key words】AOE net Topological sort The key path

一：实验内容概述
采用图的邻接表（出边表）表示方法，实现拓扑排序和关键路径的求解过程。使用实现的算法对于图的AOE网，求出各活动的可能的最早开始时间和最晚开始时间。输出整个工程的最短完成时间是多少？哪些活动是关键活动？说明哪项活动提高速度后能导致整个工程提前完成。

二：实验目的概述
AOE网是一个带权的有向无环图，其中，顶点表示事件，弧表示活动，权表示活动持续的时间。在AOE网络中, 有些活动顺序进行，有些活动并行进行。由于整个工程只有一个开始点和一个完成点，故在正常情况下（无环），网中只有一个入度为零的点（称作源点）和一个出度为零的点（叫做汇点）.如图1

图1

AOE网络在某些工程估算方面非常有用，为了进行人力、物力的调度和分配，以缩短工期，我们必须找出影响工程进度的关键活动，争取提高关键活动的功效，若网中有多条关键路径那么只提高一条关键路径上的关键活动的速度还不能导致整个工程缩短工期，还必须提高同时在所有关键路径上的活动的速度，因此必须求出所有关键路径。
三：解题思路的描述
从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。
要找出关键路径，必须找出关键活动，即不按期完成就会影响整个工程完成的活动。
事件Vi的最早开始时间Ve(i)为源点V1到Vi的最长路径长度。活动ai的最早开始时间e(i)，活动ai 的最迟开始时间l(i),e(i)=l(i)的活动叫做关键活动。关键路径上的所有活动都是关键活动。因此，只要找到了关键活动，就可以找到。
例如，下图是一个有11项活动的AOE-网。其中有9个事件V1,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天完成，都不会影响这个工程的完成。

分析：①关键路径上的所有活动都是关键活动，只有提高关键活动的效率，才能缩短整个工期。②提前完成非关键活动并不能加快工程进度。③辨别关键活动就是找l(i)=e(i)的活动。④要得到活动的l(i)和e(i)，必须先计算事件的最早和最迟发生时间ve和vl。

关键路径举例

找出图一中的关键路径！为了找出关键路径，需要找出关键活动；因此需要计算每个事件、每个活动的最早开始时间和最晚开始时间。最早开始时间需要从源点开始正向的进行计算，而最晚开始时间需要从汇点逆向的开始计算。

（a）

（b）

（c）
图二：

关键路径的算法：
1．  入e条弧〈j,k〉，建立AOE-网的存储结构；
2．从源点V0出发，令ve[0]=0，按拓扑有序求其余各顶点的最早发生时间ve[I](1≤i≤n-1)。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤（3）。
3．从汇点vn出发，令vl[n-1]=ve[n-1],按逆拓扑有序求其余各顶点的最迟发生时间vl[I](n-2≥i≥0)；
     4．根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足条件e(s)=l(s),则为关键活动。

Status criticalpath(algraph g){
//G为有向网，输出G的各项关键活动。
If (!topologicalorder(G,t) return ERROR;
Vl[0..G.vexnum-1]=ve[G.vexnum-1]; //初始化顶点事件的最迟发生时间
While (!stackempty(t)) // 按拓扑逆序求各项点的vl值
For (pop(t,j),p=g.vextices[j].firstarc;p;p=p->nextarc){
K=p->adjvex;dut=*(p->info); //dut〈j,k〉
If (vl[k]-dut<vl[j]) vl[j]=vl[k]-dut;
}
for (j=0;j<g.vexnum;++j) //求ee,el和关键活动
for (p=g.vertices[j]).firstarc;p;p=p->nextarc){
k=p->adjvex;dut=*(p->info);
ee=ve[j];el=vl[k]-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 struct //顶点表结点
{ 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++)
{ Graphicmap[i].projectname=i;
Graphicmap[i].id =0;
Graphicmap[i].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; //将邻接点序号j赋给新结点的邻接点域
p->dut =duttem;
Graphicmap[end-1].id ++; // 将入度加1
p->next =Graphicmap[begin-1].link ;
Graphicmap[begin-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* topologystack=(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)); //表示活动最早开始时间
edgenode *p;
totaltime=0;
for(i=0;i<projectnumber;i++)
ve[i]=0;
for(i=0;i<projectnumber;i++)
{ if(Graphicmap[i].id==0)
{ topologystack[++rear]=i;
m++; }
}
while(front!=rear)
{ front++;
j=topologystack[front];
m++;
p=Graphicmap[j].link ;
while(p)
{ k=p->adjvex ;
Graphicmap[k].id --;
if(ve[j]+p->dut >ve[k])
ve[k]=ve[j]+p->dut ;
if(Graphicmap[k].id ==0)
topologystack[++rear]=k;
p=p->next ;
}
}
if(m<projectnumber)
{ printf("\n本程序所建立的图有回路不可计算出关键路径\n");
printf("将退出本程序\n");
return 0;
}
totaltime=ve[projectnumber-1];
for(i=0;i<projectnumber;i++)
vl[i]=totaltime;
for(i=projectnumber-2;i>=0;i--)
{ j=topologystack[i];
p=Graphicmap[j].link ;
while(p)
{ k=p->adjvex ;
if((vl[k]-p->dut )<vl[j])
vl[j]=vl[k]-p->dut ;
p=p->next ; }
}
i=0;
printf("| 起点 | 终点 | 最早开始时间 | 最迟完成时间 | 差值 | 备注 |\n");
for(j=0;j<projectnumber;j++)
{ p=Graphicmap[j].link;
while(p)
{ k=p->adjvex ;
e[++i]=ve[j];
l[i]=vl[k]-p->dut;
printf("| %5d | %5d | %5d | %5d | %5d |",Graphicmap[j].projectname
+1,Graphicmap[k].projectname +1,e[i],l[i],l[i]-e[i]);
if(l[i]==e[i])
printf(" 关键活动 |");
printf("\n");
p=p->next ;
}
}
return 1; }
//寻找关键路径
void seekkeyroot()
{ int projectnumber,activenumber,totaltime=0;
system("cls");
printf("请输入这个工程个数:");
scanf("%d",&projectnumber);
printf("请输入这个工程和工程之间的边数:");
scanf("%d",&activenumber);
vexnode* Graphicmap=(vexnode*)malloc(projectnumber*sizeof(vexnode));
CreateGraphic(Graphicmap,projectnumber,activenumber);
SearchMapPath(Graphicmap,projectnumber,activenumber,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!='S'&&ch!='E');
switch(ch)
{ case'S': seekkeyroot();
break;
case'E': return 1;
}
}
}

五：程序调试及测试结果

图三

图四

图五

六：结论
对于这个课题，第一次看到的时候，还真没有什么头绪，不过后来通过在翻阅了一些有关路径算法的参考书后，以及加上图书馆里的那些文献资料，有点思路了。
该题目是要解决拓扑排序和关键路径的求解问题，所以该程序运用了拓扑排序算法，调用了保存拓扑排序的函数。采用了链表存储结构。在调试的过程中，遇到了许多问题，因为该程序比较长也比较复杂，所以出现了许多语法错误和逻辑错误。在不断的运行调试和修改后，解决了问题。并在同学和老师的帮助下完善了程序。
这个程序由于设计时只考虑到了程序的可行性，而没有考虑其算法复杂度，过多使用了for语句，这必将造成程序的复杂性。改进设想，运用其他的方法使得程序能够更加简单。我认为经过该程序，我们要加强对C++的学习，并且要对顺序栈，进栈，入栈，出栈等函数可以正确的应用，并且对创建一个AOV图和对其进行拓扑排序的设计思想深刻了解。
这个程序也可以运用到实际生活中，比如建筑工地、房屋装修中用来计算工期。这样能更好的让用户明白整个工程的先后顺序以及各个步骤所需的时间。这样能帮助用户用最少的时间做好整个工程。在现实中很有用处。

七：参考文献
(1) 数据结构（C语言版） 唐国民，王国钧.清华大学出版社，2009.147-156
(2) 数据结构[M】。严蔚敏，昊伟民．清华大学出版社，1997．183—185．
(3) 关链硌径的新求法(J)．题灵芝，陈小松．贵州大学学报，2002.19(4)：302—304．
(4) 求解关键路径的一个算法【J】．孟繁祯．计算机工程，2001.21(4)：6—9．
(5) C程序设计(第二版)[z]．谭浩强．北京：清华大学出版社，2000．4

[在此处键入]