求关键路径设计报告 数据结构课程设计毕业设计（论文） .doc

数据结构课程设计题目：关键路径的设计报告科系：计算机科学与技术班级：姓名：题目：1、编写拓扑排序和求关键路径的程序2、单源顶点最短路径问题设计报告一 需求分析1. 在实际工程中拓扑排序和求关键路径是经常使用来安排任务的先后顺序，以及找出关键的路径，合理的安排非关键任务的施工顺序。2.对用邻接矩阵表示的有向图，从某一顶点出发（称为源点）到该图其它各顶点（称为终点）有无路径？最短路径是什么？路径长为多少？问题要求写一个程序从有向网中的某一顶点出发找出该顶点到其余各顶点的最短路径。对邻接矩阵costnn中的每一个元素只能有三种情况： 当i=j时，costij=0； 当顶点i和j无边时，costij=； 当顶点i和j有边，且其权值为Wij时，costij=Wij。由于题目中没有规定输出格式，此程序以顶点序号的形式将最短路径输出到终端上去，并输出该最短路径的长度。二 概要设计1.1抽象数据类型图的定义如下：ADT Graph数据对象V:V是具有相同特性的数据元素的集合,称为顶点集.数据对象I:I是具有相同特性的数据元素的集合,称为顶点集.数据关系R: R=VR VR=(v,w)|v,w属于V,(v,w)表示v和w之间存在路径基本操作P: Creat_ALGraph(&G,V,VR,I) 初始条件:V是图的顶点集，VR是图中边的集合,I是边的权值。 操作结果:按V和VR的定义构造图G。 DFS(&G, v) 初始条件:v是图的一个顶点，图G存在。 操作结果:从v点深度优先遍历图G。 DFSTraverse(&G) 初始条件:图G存在。 操作结果：深度优先遍历图G。 FindIngree( G,b) 初始条件：图G存在，数组b已知。 操作结果:图G的每个顶点的度放在数组b中。 TopologicalSort(&G) 初始条件:图G存在。 操作结果:对图G进行拓扑排序。 TopologicalOrder(G,&T) 初始条件:图G存在，栈T存在。 操作结果:若G无回路，则用栈T返回G的一个拓扑排序列，且函数值为OK,否则为ERROR. Criticalpath(&G) 初始条件:G存在，函数TopologicalOrder(G,&T)在。 操作结果:输出图G的关键路径。ADT Graph1.2主程序Void main( ) 图的初始化; 创建一个图; 深度优先遍历图;对图进行拓扑排序；求关键路径;2.1主要算法基本思想。单源最短路径问题采用迪杰斯特拉（Dijkstra）提出的按路径长度递增的次序产生最短路径的算法。此算法把网中所有的顶点分成两组，分别用S和T表示。凡是以i0为源点，已经确定了最短路径的终点属于第一组S，S的初态应只包含i0。另一组T则是尚未确定最短路径的顶点集合。T的初态应是除源点外的网中所有顶点的集合，按各顶点与i0间的最短路径的长度递增的次序，逐个把T中的顶点加入到S中，使得从i0到S中各顶点的路径长度始终不大于从i0到T中各顶点的路径长度。它的初始状态即是邻接矩阵cost中第i0列内各列的值。显然，从源点到各顶点的最短路径中最短的一条路径应为 distv=mindisti(i=1,2,n)第一次求的最短路径长度必然是(i0,v) ，这时顶点号v应从T中删除而并入S。每当选出一个顶点号v并使之并入S后，就要修改T中各顶点的最短路径长度dist。对于T中的某一个顶点i来说，其最短路径长度或者仍是(i0,i)，或者是(i0,v,i)，决不可能有其它选择，也就是说，若distv+costvi<disti 则修改disti，使disti= distv+costvi当T组中各顶点的dist进行修改后，再从中挑选出一个路径长度路径最小的顶点，从T中删除后再并入S。依次类推，就能求出所需的最短路径长度。其中dist、S、pre都定义为整型数组，数组S用以标记那些已经找到最短路径的顶点。若Si为1，表示已找到源点到顶点i的最短路径；若Si为0，则表示从源点到顶点i的最短路径尚未求得。Pre i表示从源点到顶点i的最短路径上该点的前趋顶点，若从源点到顶点无路径，则用0用为其前一个顶点序号。三 详细设计. 顶点，边和图类型，堆栈以下为图的邻接表结构#define 图中顶点数的最大值typedef struct Arcnodeint adjvex;结点的值struct Arcnode *nextarc;指向下个结点的指针int info;结点的权值Arcnode;结点类型typedef struct Vnodeint data;主结点值Arcnode *firstarc;指向结点的指针Vnode,AdjlistMAX;typedef structAdjlist vertices;int vernum,arcnum;顶点数和边数int kind;图的种类ALGraph;图类型 以下为堆栈结构 typedef structint *base,*top;栈底和栈顶int stacksize;栈的大小Sqstack; 栈的类型图的基本操作：void Creat_ALGraph(ALGraph &G)；创建一个带权的有向图。void DFS(ALGraph &G,int v);从点深度遍历图。void DFSTraverse(ALGraph &G)；深度遍历图。void FindIngree(ALGraph G,int b20)；求图每个顶点的入度void FindIngree(ALGraph G,int b20)；对图进行拓扑排序。int TopologicalOrder(ALGraph G,Sqstack &T)；若无回路，则用栈返回的一个拓扑排序列，且函数值为，否则为；void Criticalpath(ALGraph &G)；为有向图，输出图的关键路径。栈的基本操作：void Inist_stack(Sqstack &S)；初始化栈。int StackEmpty(Sqstack &S)；判断栈是否为空。void push(Sqstack &S,int a)；入栈。int pop(Sqstack &S)；出栈。.主程序和其他伪代码算法void main() /主程序ALGraph G; /定义一个图Creat_ALGraph(G); /创建一个带权的有向无环图 DFSTraverse(G); /深度优先遍历 TopologicalSort(G); /拓扑排序 Criticalpath(G); /求关键路径/mainvoid Creat_ALGraph(ALGraph &G) /创建一个邻接表结构的图cin>>G.vernum; /输入顶点数cin>>G.arcnum; /输入边数 for(int i=0;i<G.vernum;+i)G.verticesi.data=i;G.verticesi.firstarc=NULL; /顶点初始化Arcnode *p; /定义一个结点指针pfor(int j=0;j<G.arcnum;+j) int v,w,u;cin>>v>>w>>u; /输入带权的边p=new Arcnode;p->adjvex=w;p->info=u;p->nextarc=G.verticesv.firstarc;G.verticesv.firstarc=p;/Creat_ALGraphvoid Inist_stack(Sqstack &S) /初始化栈S.base=new int(MAX); /为栈分配一个MAX大的空间S.top=S.base; /栈顶等于栈底S.stacksize=MAX; /栈的大小/Inist_stackint StackEmpty(Sqstack &S) /判断栈是否为空if(S.base=S.top) /栈顶等于栈底，则为空，返回0；return 0;elsereturn 1; /否则返回1；/StackEmptyvoid push(Sqstack &S,int a) /把元素a放入栈if(S.top-S.base<S.stacksize) /栈没有满*S.top=a;+S.top;else /栈已满在分配空间*S.top=a;+S.top;/pushint pop(Sqstack &S) /返回栈顶的值if(S.top!=S.base) /栈不为空-S.top;return *S.top;/popvoid DFS(ALGraph &G,int v) /从第v个顶点出发递归地深度优先遍历图Gvisitedv=1; /已被访问cout<<v<<" "Arcnode *q;for(q=G.verticesv.firstarc;q;q=q->nextarc)int u;u=q->adjvex;if(!visitedu)DFS(G,u);/DFSvoid DFSTraverse(ALGraph &G) /深度优先遍历图Gfor(int i1=0;i1<G.vernum;+i1)visitedi1=0; /把所有顶点表示成未访问for(int j1=0;j1<G.vernum;+j1)if(!visitedj1)DFS(G,j1); /没有访问就调用函数DFS/DFSTraversevoid FindIngree(ALGraph G,int b20) /计算图中每个顶点的入度for(int j=0;j<20;+j)bj=0; /把数组全部置零for(int i=0;i<G.vernum;+i)Arcnode *p; /定义一个结点指针for(p=G.verticesi.firstarc;p;p=p->nextarc)+bp->adjvex; /各点入度加一/FindIngreevoid TopologicalSort(ALGraph &G) /对图G 进行拓扑排序int indegreeMAX;FindIngree(G,indegree); /初始化每个结点的入度Sqstack S;Inist_stack(S); /初始化栈for(int j=0;j<G.vernum;+j)if(!indegreej)push(S,j); /入度为零的入栈int count=0; /顶点计数while(StackEmpty(S) /栈非空int d;d=pop(S); /出栈cout<<d<<" " /输出顶点count+;for(Arcnode *q=G.verticesd.firstarc;q;q=q->nextarc)int k;k=q->adjvex;if(!(-indegreek) push(S,k); /如果顶点入度为零则入栈cout<<endl;if(count<G.vernum) /输出顶点数小于所有顶点数cout<<"有环"/ TopologicalSortint veMAX,vlMAX; /分别记录各顶点的最早发生时间和最迟发生时间int TopologicalOrder(ALGraph G,Sqstack &T) /若无回路，则用栈返回的一个拓扑排序列，且函数值为，否则为；int indegreeMAX; FindIngree(G,indegree); /初始化每个结点的入度Sqstack S;Inist_stack(S); /初始化栈Inist_stack(T); for(int j=0;j<G.vernum;+j)if(!indegreej)push(S,j); /把所有入度为零的顶点放入栈中int count=0; /记录顶点数for(int i=0;i<G.vernum;+i)vei=0; /记录最早发生时间while(StackEmpty(S) /栈非空int e; e=pop(S);push(T,e); /用栈返回的一个拓扑排序列+count;Arcnode *q;for(q=G.verticese.firstarc;q;q=q->nextarc)int k;k=q->adjvex;if(!(-indegreek)push(S,k); /入度为零的顶点放入栈if(vee+(q->info)>vek)vek=vee+(q->info); /计算各点的最早发生时间if(count<G.vernum)return 0; /有回路elsereturn 1; /无回路/ TopologicalOrdervoid Criticalpath(ALGraph &G) /输出图G的关键路径Sqstack T;if(!TopologicalOrder(G,T)cout<<"error"<<endl; /判断图是否有环for(int i=0;i<G.vernum;+i)vli=veG.vernum-1; /初始化while(StackEmpty(T) /栈非空int j;j=pop(T); /出栈for(Arcnode *p=G.verticesj.firstarc;p;p=p->nextarc)int k=p->adjvex;int dut=p->info;if(vlk-dut<vlj)vlj=vlk-dut; /计算各顶点的最迟发生时间 Arcnode *p; /定义顶点指针for(int j1=0;j1<G.vernum;+j1)for(p=G.verticesj1.firstarc;p;p=p->nextarc)int k=p->adjvex; /顶点的值int dut=p->info; /顶点的权值int ee,el; ee=vej1; /顶点的最早发生时间el=vlk-dut; /顶点的最迟发生时间char tag; /符号标志if(ee=el) tag='*' /顶点的最早发生时间等于最迟发生时间,输出*elsetag='#' /顶点的最早发生时间不等于最迟发生时间，输出#cout<<j1<<" "<<k<<" "<<dut<<" "<<ee<<" "<<el<<" "<<tag<<endl;/ Criticalpath1. 函数的调用关系图MainCreat_ALGraphDFSTraverse(G)TopologicalSortCriticalpathDFSFindIngreeTopologicalOrderFindIngreeDijkstra算法描述如下：（1） 输入顶点个数n、邻接矩阵cost和源点序号i0；（2） 送初值：将i0加入第一组S；令disti=costi0i；(i=1,2,n)；（3） 重复n-1次做：Ø 在不属于S的顶点U中，选取具有最小distu值的顶点v；Ø 将v加入S；Ø 对不属于S的顶点U做distu=mindistu, distv+costvu;/* distu取distu, distv+costvu两个数中的最小值*/（4） 输出各最短路径的长度disti及相应的最短路径pre。3调试报告在调试过程中要特别注意函数调用时参数的传递问题，用数组名作为参数可进行传值调用，因而可将函数中的运行结果传递给主调函数，得出正确结果；再一个要注意的是输出结果时，循环结束的条件应为：k=i0或k=0时退出循环，否则将出现死循环。另外，上机前的静态检查不能忽视；程序的调试过程可暂时多加一些输出语句以便及时查看一下中间运行情况并对程序规格说明作少量调整和改动。四 程序分析调试，测试结果. 分析调试 该程序用邻接表存储结构，能够节省存储空间。求拓扑排序的时间复杂度为O(n*n)，求关键路径的时间复杂度也是O(n*n). 测试 结果输入一个带权有向图（像这样输入（v,w,i）其中v,w为一条边的两个顶点，i为边的权值）：（0，1，6），（0，2，4），（0，3，5），（1，4，1），（2，4，1），（3，5，2）,（4，6，9），（4，7，7），（5，7，4），（6，8，2），（7，8，4）。结果为：五 源程序#include<iostream.h>#define MAX 20typedef struct Arcnodeint adjvex; /顶点值struct Arcnode *nextarc; /指向下一个顶点的指针int info; /权值Arcnode;typedef struct Vnodeint data; /顶点值Arcnode *firstarc; /指向顶点的指针Vnode,AdjlistMAX;typedef structAdjlist vertices; int vernum,arcnum; /顶点数和边数int kind;ALGraph; /图类型/采用邻接表存储结构void Creat_ALGraph(ALGraph &G)/创建图cout<<"请输入顶点数:"cin>>G.vernum;cout<<"请输入边数:"cin>>G.arcnum;for(int i=0;i<G.vernum;+i)G.verticesi.data=i;G.verticesi.firstarc=NULL;/顶点初始化cout<<"请输入各边，；列入(v w i),v,w为一条边的两个顶点，从0开始的数字，i为权值:"<<endl;Arcnode *p;for(int j=0;j<G.arcnum;+j) int v,w,u;cin>>v>>w>>u; /输入边的两个顶点和权值p=new Arcnode; /分配一个顶点空间p->adjvex=w;p->info=u;p->nextarc=G.verticesv.firstarc; G.verticesv.firstarc=p;/定义栈typedef structint *base,*top;int stacksize;Sqstack;void Inist_stack(Sqstack &S)/初始化栈S.base=new int(MAX);S.top=S.base;S.stacksize=MAX;int StackEmpty(Sqstack &S)/判断栈是否为空if(S.base=S.top) /栈顶等于栈底return 0;elsereturn 1;void push(Sqstack &S,int a)/入栈if(S.top-S.base<S.stacksize)*S.top=a;+S.top;int pop(Sqstack &S)/出栈if(S.top!=S.base)-S.top;return *S.top;/深度优先遍历图Gbool visitedMAX;void DFS(ALGraph &G,int v);void DFSTraverse(ALGraph &G)/深度优先遍历图for(int i1=0;i1<G.vernum;+i1)visitedi1=0;for(int j1=0;j1<G.vernum;+j1)if(!visitedj1)DFS(G,j1);void DFS(ALGraph &G,int v)/从第v个顶点出发递归地深度优先遍历图Gvisitedv=1;cout<<v<<" "Arcnode *q;for(q=G.verticesv.firstarc;q;q=q->nextarc)int u;u=q->adjvex;if(!visitedu)DFS(G,u);/拓扑排序void FindIngree(ALGraph G,int b20)/计算图中每个顶点的入度for(int j=0;j<20;+j)bj=0;for(int i=0;i<G.vernum;+i)Arcnode *p;for(p=G.verticesi.firstarc;p;p=p->nextarc) /循环每个顶点的出边+bp->adjvex; /计算每个顶点的入度void TopologicalSort(ALGraph &G)int indegreeMAX;FindIngree(G,indegree);Sqstack S;Inist_stack(S);for(int j=0;j<G.vernum;+j)if(!indegreej)push(S,j);int count=0;cout<<endl<<"图的拓扑排序为:"while(StackEmpty(S) /判断栈非空就循环int d;d=pop(S); /出栈cout<<d<<" " /输出顶点count+;for(Arcnode *q=G.verticesd.firstarc;q;q=q->nextarc) /循环所有顶点的出边int k;k=q->adjvex;if(!(-indegreek)push(S,k); /入度为零就入栈cout<<endl;if(count<G.vernum)cout<<"有环"/求关键路径int veMAX,vlMAX;int TopologicalOrder(ALGraph G,Sqstack &T)int indegreeMAX;FindIngree(G,indegree); Sqstack S;Inist_stack(S);Inist_stack(T);for(int j=0;j<G.vernum;+j)if(!indegreej)push(S,j); /入度为零就入栈int count=0;for(int i=0;i<G.vernum;+i)vei=0;while(StackEmpty(S) /栈非空就循环int e;e=pop(S);push(T,e);+count;Arcnode *q;for(q=G.verticese.firstarc;q;q=q->nextarc) /循环一个顶点的所有出边int k;k=q->adjvex;if(!(-indegreek) /判断入度是否为零push(S,k); /为零入栈if(vee+(q->info)>vek)vek=vee+(q->info);if(count<G.vernum)return 0; /图有环elsereturn 1; /无环void Criticalpath(ALGraph &G)Sqstack T;if(!TopologicalOrder(G,T)cout<<"error"<<endl; /判断图是否为有环for(int i=0;i<G.vernum;+i)vli=veG.vernum-1; /把每个顶点的最迟发生时间初始化为最后完成时间while(StackEmpty(T) /栈非空就循环int j;j=pop(T); /出栈for(Arcnode *p=G.verticesj.firstarc;p;p=p->nextarc)int k=p->adjvex;int dut=p->info; /权值if(vlk-dut<vlj)vlj=vlk-dut; /各点的最迟发生时间cout<<"输出为(i1,i2,i3,i4,i5,i6)i1,i2为边，i3为权值，i4为最早发生时间，i5为最迟发生时间,带'*'的是关键路径:"<<endl; Arcnode *p;for(int j1=0;j1<G.vernum;+j1)for(p=G.verticesj1.firstarc;p;p=p->nextarc)int k=p->adjvex;int dut=p->info;int ee,el;ee=vej1;el=vlk-dut;char tag;if(ee=el) tag='*' /最早发生时间等于最迟发生时间elsetag='#' /最早发生时间不等于最迟发生时间cout<<j1<<" "<<k<<" "<<dut<<" "<<ee<<" "<<el<<" "<<tag<<endl;void main()ALGraph G;Creat_ALGraph(G); /创建一个带权的有向无环图 DFSTraverse(G); /深度优先遍历 TopologicalSort(G); /拓扑排序 Criticalpath(G); /求关键路径六 心得在这次编程的过程中，虽然经历的很多困难，但最终我都克服了，这给了我在以后的编程过程中战胜困难的信心。通过这次编程，使我的编程经验有所增加，锻炼了我的编程能力，使我学到了很多的东西。