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

1、数据结构课程设计题目：关键路径的设计报告科系：计算机科学与技术班级：姓名：题目：1、编写拓扑排序和求关键路径的程序2、单源顶点最短路径问题设计报告一 需求分析1. 在实际工程中拓扑排序和求关键路径是经常使用来安排任务的先后顺序，以及找出关键的路径，合理的安排非关键任务的施工顺序。2.对用邻接矩阵表示的有向图，从某一顶点出发（称为源点）到该图其它各顶点（称为终点）有无路径？最短路径是什么？路径长为多少？问题要求写一个程序从有向网中的某一顶点出发找出该顶点到其余各顶点的最短路径。对邻接矩阵costnn中的每一个元素只能有三种情况： 当i=j时，costij=0； 当顶点i和j无边时，costij=

2、； 当顶点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

3、(&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存在

4、，函数topologicalorder(g,&t)在。 操作结果:输出图g的关键路径。adt graph1.2主程序void main( ) 图的初始化; 创建一个图; 深度优先遍历图;对图进行拓扑排序；求关键路径;2.1主要算法基本思想。单源最短路径问题采用迪杰斯特拉（dijkstra）提出的按路径长度递增的次序产生最短路径的算法。此算法把网中所有的顶点分成两组，分别用s和t表示。凡是以i0为源点，已经确定了最短路径的终点属于第一组s，s的初态应只包含i0。另一组t则是尚未确定最短路径的顶点集合。t的初态应是除源点外的网中所有顶点的集合，按各顶点与i0间的最短路径的长度递增的次序，逐个把t中

5、的顶点加入到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+costvig.vernum; /输入顶点数cing.arcnum; /

6、输入边数 for(int i=0;ig.vernum;+i)g.verticesi.data=i;g.verticesi.firstarc=null; /顶点初始化arcnode *p; /定义一个结点指针pfor(int j=0;jvwu; /输入带权的边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大的空间

7、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.bases.stacksize) /栈没有满*s.top=a;+s.top;else /栈已满在分配空间*s.top=a;+s.top;/pushint pop(sqstack

8、&s) /返回栈顶的值if(s.top!=s.base) /栈不为空-s.top;return *s.top;/popvoid dfs(algraph &g,int v) /从第v个顶点出发递归地深度优先遍历图gvisitedv=1; /已被访问coutvnextarc)int u;u=q-adjvex;if(!visitedu)dfs(g,u);/dfsvoid dfstraverse(algraph &g) /深度优先遍历图gfor(int i1=0;i1g.vernum;+i1)visitedi1=0; /把所有顶点表示成未访问for(int j1=0;j1g.vernum;+j1)if

9、(!visitedj1)dfs(g,j1); /没有访问就调用函数dfs/dfstraversevoid findingree(algraph g,int b20) /计算图中每个顶点的入度for(int j=0;j20;+j)bj=0; /把数组全部置零for(int i=0;inextarc)+bp-adjvex; /各点入度加一/findingreevoid topologicalsort(algraph &g) /对图g 进行拓扑排序int indegreemax;findingree(g,indegree); /初始化每个结点的入度sqstack s;inist_stack(s);

10、/初始化栈for(int j=0;jg.vernum;+j)if(!indegreej)push(s,j); /入度为零的入栈int count=0; /顶点计数while(stackempty(s) /栈非空int d;d=pop(s); /出栈coutdnextarc)int k;k=q-adjvex;if(!(-indegreek) push(s,k); /如果顶点入度为零则入栈coutendl;if(countg.vernum) /输出顶点数小于所有顶点数cout有环;/ topologicalsortint vemax,vlmax; /分别记录各顶点的最早发生时间和最迟发生时间int

11、 topologicalorder(algraph g,sqstack &t) /若无回路，则用栈返回的一个拓扑排序列，且函数值为，否则为；int indegreemax; findingree(g,indegree); /初始化每个结点的入度sqstack s;inist_stack(s); /初始化栈inist_stack(t); for(int j=0;jg.vernum;+j)if(!indegreej)push(s,j); /把所有入度为零的顶点放入栈中int count=0; /记录顶点数for(int i=0;inextarc)int k;k=q-adjvex;if(!(-ind

12、egreek)push(s,k); /入度为零的顶点放入栈if(vee+(q-info)vek)vek=vee+(q-info); /计算各点的最早发生时间if(countg.vernum)return 0; /有回路elsereturn 1; /无回路/ topologicalordervoid criticalpath(algraph &g) /输出图g的关键路径sqstack t;if(!topologicalorder(g,t)couterrorendl; /判断图是否有环for(int i=0;inextarc)int k=p-adjvex;int dut=p-info;if(vlk

13、-dutvlj)vlj=vlk-dut; /计算各顶点的最迟发生时间 arcnode *p; /定义顶点指针for(int j1=0;j1nextarc)int k=p-adjvex; /顶点的值int dut=p-info; /顶点的权值int ee,el; ee=vej1; /顶点的最早发生时间el=vlk-dut; /顶点的最迟发生时间char tag; /符号标志if(ee=el) tag=*; /顶点的最早发生时间等于最迟发生时间,输出*elsetag=#; /顶点的最早发生时间不等于最迟发生时间，输出#coutj1 k dut ee el tagendl;/ criticalpat

14、h1. 函数的调用关系图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, d

15、istv+costvu两个数中的最小值*/（4） 输出各最短路径的长度disti及相应的最短路径pre。3调试报告在调试过程中要特别注意函数调用时参数的传递问题，用数组名作为参数可进行传值调用，因而可将函数中的运行结果传递给主调函数，得出正确结果；再一个要注意的是输出结果时，循环结束的条件应为：k=i0或k=0时退出循环，否则将出现死循环。另外，上机前的静态检查不能忽视；程序的调试过程可暂时多加一些输出语句以便及时查看一下中间运行情况并对程序规格说明作少量调整和改动。四 程序分析调试，测试结果. 分析调试 该程序用邻接表存储结构，能够节省存储空间。求拓扑排序的时间复杂度为o(n*n)，求关键路

16、径的时间复杂度也是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#define max 20typedef struct arcnodeint adjvex; /顶点值struct arcnode *nextarc; /指向下一个顶点的指针int info; /权值arcnode;typedef struct vnod

17、eint data; /顶点值arcnode *firstarc; /指向顶点的指针vnode,adjlistmax;typedef structadjlist vertices; int vernum,arcnum; /顶点数和边数int kind;algraph; /图类型/采用邻接表存储结构void creat_algraph(algraph &g)/创建图coutg.vernum;coutg.arcnum;for(int i=0;ig.vernum;+i)g.verticesi.data=i;g.verticesi.firstarc=null;/顶点初始化cout请输入各边，；列入(v

18、 w i),v,w为一条边的两个顶点，从0开始的数字，i为权值:endl;arcnode *p;for(int j=0;jvwu; /输入边的两个顶点和权值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.

19、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.bases.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(algr

20、aph &g)/深度优先遍历图for(int i1=0;i1g.vernum;+i1)visitedi1=0;for(int j1=0;j1g.vernum;+j1)if(!visitedj1)dfs(g,j1);void dfs(algraph &g,int v)/从第v个顶点出发递归地深度优先遍历图gvisitedv=1;coutvnextarc)int u;u=q-adjvex;if(!visitedu)dfs(g,u);/拓扑排序void findingree(algraph g,int b20)/计算图中每个顶点的入度for(int j=0;j20;+j)bj=0;for(int i

21、=0;inextarc) /循环每个顶点的出边+bp-adjvex; /计算每个顶点的入度void topologicalsort(algraph &g)int indegreemax;findingree(g,indegree);sqstack s;inist_stack(s);for(int j=0;jg.vernum;+j)if(!indegreej)push(s,j);int count=0;coutendl图的拓扑排序为:;while(stackempty(s) /判断栈非空就循环int d;d=pop(s); /出栈coutdnextarc) /循环所有顶点的出边int k;k=q

22、-adjvex;if(!(-indegreek)push(s,k); /入度为零就入栈coutendl;if(countg.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;jg.vernum;+j)if(!indegreej)push(s,j); /入度为零就入栈int count=0;for(int i=0;inextarc) /循环一个顶点的所有出边int k;k=q-adjvex;if(!(-indegreek) /判断入度是否为零push(s,k); /为零入栈if(v