拓扑排序与关键路径在实际的应用

数学与计算机学院课程设计说明书课程名称：算法设计与分析-课程设计课程代码：8174123题目：拓扑排序与关键路径在实际的应用年级/专业/班：学生姓名：学号:开始时间：年月日完成时间：年月日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总分（100）指导教师签名：年月日e目录TOC\o"1-5"\h\z\o"CurrentDocument"摘要i\o"CurrentDocument"1引言2\o"CurrentDocument"1.1问题的提出2\o"CurrentDocument"1.2C++语言2\o"CurrentDocument"1.3算法设计与分析的地位21.4拓扑排序的描述3\o"CurrentDocument"1.5任务与分析4\o"CurrentDocument"2设计方案4\o"CurrentDocument"2.1问题描述4\o"CurrentDocument"2.2算法描述5\o"CurrentDocument"2.3算法设计6\o"CurrentDocument"2.4算法编码实现7\o"CurrentDocument"3.系统测试9\o"CurrentDocument"3.1图形化界面展示图及所求解的顶点和路径9\o"CurrentDocument"3.2算法的时间复杂度分析10\o"CurrentDocument"结论12\o"CurrentDocument"致谢13\o"CurrentDocument"参考文献14摘要排课问题是现在各个学校必须面临的一个问题。而且随着近年来学生规模的扩招，教育机构的复杂化，课程各类的多样化，排课的问题越来越难。尽管目前对排课采用了程序设计的计算机智能排课系统，但是仍然存在着这样或者那样的问题。最为突出的一个问题，比如，有一些排课方案，看上去完美无缺，或者效率比较高，甚至达到了最优解,但是具体地去实施的时候，发现整个课程的设计方案有着大的漏洞，经常出现的问题是，排课的拓扑图出现了一些环，以至于进入了死循环。该文的目的就是针对于如何检测环的存在而避免错误的排课方案。本文采用的算法是基于拓扑序列的拓扑排序算法对特定条件的排课问题提出的一种解决方案，具体的实验结果是展示出一个符合条件的课程拓扑序列，整个算法的设计与实现过程将要用到邻接表，堆栈等数据结构等等。关键词：有向图，拓扑排序，排课1引言1.1问题的提出自1946年第一台计算机问世以来，计算机产业的飞速发展已远远超出人们对它的预料，在某些生产线上，甚至几秒钟就能生产出一台微型计算机，产量猛增，价格低廉，这就使得它的应用范围迅速扩展。如今，计算机已深入到人类社会的各个领域。计算机的应用已不再局限于科学计算，而更多地用于控制、管理及数据处理等非数值计算的处理工作。与这些相应，计算机加工处理的对象由纯粹的数值处理发展到字符、表格和图像等各种具有一定结构的数据，这就给程序设计带来一些新的问题。为了编写出一个“好”的程序，必须分析待处理的对象的特性以及处理对象之间存在的关系。这就是“算法设计与分析”这门学科形成和发展的背景。1.2C++语言C语言本身存在一些局限，例如：C语言不支持代码重用，C语言对类型的检查机制相对较弱。为了解决C语言自身所具有的诸多问题，1980年，贝尔实验室的BjarneStroutstrup博士及其同事开始对C语言进行改进和扩充，并使C++语言在C语言的基础上发展起来。在基本语法特点方面，C++语言保持与C语言兼并，二者没有本质上的差别，大多数使用C语言编写的代码可以在C++语言中直接使用。这也是C++语言很快普及的一个重要原因。C++语言与C语言的主要区别是编程思想上的更新，即编码由面向过程变为面向对象，基于此，C++语言引入了类与对象机制，包括类的定义，类的继承与派生，类的多态性等。在类定义方面，C++语言一方面自定义结构类型进行扩充，另一方面也支持新的类构造。数据封装和隐藏是与类的定义紧密相关，并且在C++语言中经常碰到的现象，也是C++语言中的一大特点。数据的封装和隐藏使重要的内部数据得到保护。1.3算法设计与分析的地位算法设计与分析在计算机科学中是一门综合性的专业基础课。算法的研究不仅涉及到计算机硬件（特别是编码理论、存储装置和存取方法等）的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更为方便。因此，可以认为算法设计与分析是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。在计算机科学中，算法设计与分析不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。1.4拓扑排序的描述1.4.1拓扑排序的基本思想：对于学生选修课程问题：顶点——表示课程；有向弧——表示先决条件，若课程i是j的先决条件，则图中有弧＜i,j＞。学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业一一拓扑排序。AOV网——用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(ActivityOnVertexnetwork)，简称AOV网。若＜vi,vj＞是图中有向边，则vi是vj的直接前驱；vj是vi的直接后继；AOV网中不允许有回路，这意味着某项活动以自己为先决条件。拓扑排序——把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫拓扑排序。检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。1.4.2设计拓扑排序的步骤：1、在有向图中选一个没有前驱的顶点且输出之；1、从图中删除该顶点和所有以它为尾的孤；3、重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。1.4.3拓扑排序问题的特征：拓扑排序的有效性依赖于图本身所具有的两个重要性质：有向和无环。1、有向：任务之间有先后关系，即有方向。2、无环：若有环，回路中就会存在彼此矛盾的条件。在项目管理中，关键路径是指网络终端元素的元素的序列，该序列具有最长的总工期并决定了整个项目的最短完成时间。关键路径的工期决定了整个项目的工期。任何关键路径上的终端元素的延迟将直接影响项目的预期完成时间(例如在关键路径上没

有浮动时间)。一个项目可以有多个，并行的关键路径。另一个总工期比关键路径的总工期略少的一条并行路径被称为次关键路径。最初，关键路径方法只考虑终端元素之间的逻辑依赖关系。关键链方法中增加了资源约束。用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有向图叫AOE(ActivityOnEdgeNetwork)网。AOE网常用于估算工程完成时间。1.4.5设计关键路径的步骤:输入e条弧<j,k>，建立AOE网的存储结构。从源点v1出发，令ve(1)=0,求ve(j)2<=j<=n。从汇点vn出发，令vl(n)=ve(n),求vl(i)1<=i<=n-1。根据各顶点的ve和vl值，求每条弧s(活动)的最早开始时间e(s)和最晚开始时间l(s)，其中e(s)=l(s)的为关键活动。1.4.6关键路径问题的特征:求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径;只有缩短关键活动的工期才有可能缩短工期；若一个关键活动不在所有的关键路径上，减少它并不能减少工期；只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。1.5任务与分析掌握拓扑排序算法的基本思想，包括有向无环图的性质和基于拓扑排序的关键路径计算方法。熟练掌握拓扑排序和关键路径分析方法。学会利用拓扑排序和关键路径算法解决实际问题。2设计方案2.1问题描述给定一个有向无环图，其存储形式为如下所示。在此图中，从入度为0的顶点出发，删除此顶点和所有以它为尾的孤；重复直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。

2.2算法描述算法分析：这道题如果用拓扑排序法，在图的顶点数稍大的情况下(比如40,100或者更大)，由阶乘可知需要列举出的路径条数将是一个非常庞大的数目，故不做讨论。如果用其它方法又往往得不到最优解。在用拓扑排序考虑图的问题时可以自顶向下的分析，自底向上的计算。核心是从入度为0顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，删除该顶点和其尾弧。继续向下一个入度为0顶点做删除操作，直到全部顶点均已输出；或者当图中不存在无前驱的顶点为止。具体步骤如下：Stepl：存储信息，将邻接矩阵数据存放到数组charindegree[40]中。Step2:阶段划分，对于拓扑排序问题应该从上而下逐层决策，这样逐层递推求出最后结果。Step3：关键路径的存储，用indegree[][]存储各个路径的最优值，用TopologicalOrder[][]存储路径。indegree[i][j]初始化charindegree[i][j],TopologicalOrder[i][j]初始化0，TopologicalOrder[i][j]=0为向左，等于1为向右。Step4：信息的输出，路径最优质为TopologicalOrder[1][1],路径输出为：if(count<G.vexnum)returnERROR;//该有向网有回路elsereturnOK;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);//输出关键活动}returnOK;2.3算法设计本次实验程序主要用到二维数组，以及通过动态规划法进行比较每个数的大小。主要运用两个for循环语句实现动态规划，画出流程图如下图2-1所示。

indegree[j]==0)Push(S,j);YN--indegree[k]==0)Push(S,k);ve[j]+p->info>indegree[j]==0)Push(S,j);YN--indegree[k]==0)Push(S,k);ve[j]+p->info>ve[k])ve[k]=ve[j]+p->info;建立邻接表存储结构并初始化j从n到1循环i从1到n循环输出结果2.4算法编码实现拓扑排序：StatusTopologicalOrder(ALGraphG,Stack&T)(//有向网G采用邻接表存储结构，求各顶点事件的最早发生时间ve(全局变量)。//T为拓扑序列定点栈，S为零入度顶点栈。//若G无回路，则用栈T返回G的一个拓扑序列，且函数值为OK，否则为ERROR。StackS;intcount=0,k;charindegree[40];ArcNode*p;InitStack(S);FindInDegree(G,indegree);//对各顶点求入度indegree[0..vernum-1]for(intj=0;j<G.vexnum;++j)//建零入度顶点栈Sif(indegree[j]==0)Push(S,j);//入度为0者进栈InitStack(T);//建拓扑序列顶点栈Tcount=0;for(inti=0;i<G.vexnum;i++)ve[i]=0;//初始化while(!StackEmpty(S))(Pop(S,j);Push(T,j);++count;//j号顶点入T栈并计数for(p=G.vertices[j].firstarc;p;p=p->nextarc)(k=p->adjvex;//对j号顶点的每个邻接点的入度减1if(--indegree[k]==0)Push(S,k);//若入度减为0，则入栈if(ve[j]+p->info>ve[k])ve[k]=ve[j]+p->info;}//for*(p->info)=dut(<j,k>)}//whileif(count<G.vexnum)returnERROR;//该有向网有回路elsereturnOK;}//TopologicalOrder关键路径：StatusCriticalPath(ALGraphG)(//算法7.14,G为有向网，输出G的各项关键活动。StackT;inta,j,k,el,ee,dut;chartag;ArcNode*p;if(!TopologicalOrder(G,T))returnERROR;for(a=0;a<G.vexnum;a++)vl[a]=ve[G.vexnum-1];//初始化顶点事件的最迟发生时间while(!StackEmpty(T))//按拓扑逆序求各顶点的vl值for(Pop(T,j),p=G.vertices[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);//输出关键活动}returnOK;}//CriticalPath3.系统测试3.1图形化界面展示图及所求解的顶点和路径给定一个有向无环图，其存储形式为如下所示。在此图中，从入度为0的顶点出发，在每一入度为0的顶点可以选择向下走还是向右走，一直走到底层。请找出一条关键路径。输入样例(图)：9输出样例：C3;C6;C5;C2;C4;C10;C11.测试结果如下：3.2算法的时间复杂度分析。定义：如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数T(n)称为这一算法的“时间复杂性”。当输入量n逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂性”。我们常用大O表示法表示时间复杂性，注意它是某一个算法的时间复杂性。大O表示只是说有上界，由定义如果f(n)=O(n)，那显然成立f(n)=O(n”2)，它给你一个上界，但并不是上确界，但人们在表示的时候一般都习惯表示前者。for(intj=0;j<G.vexnum;++j)//建零入度顶点栈Sif(indegree[j]==0)Push(S,j);//入度为0者进栈InitStack(T);//建拓扑序列顶点栈Tcount=0;for(inti=0;i<G.vexnum;i++)ve[i]=0;解：建邻接表：T(n)=O(e)搜索入度为0的顶点的时间：T(n)=O(n)拓扑排序：T(n)=O(n+e)结论本次课程设计，让我受益匪浅，本次的课程设计主要是对所学过的知识进行实践应用，不仅是巩固了自己所学的知识，而且把知识与实践相结合，使得自己在各个方面都有所提高。这学期我所做的课程设计是拓扑排序与关键路径在实际中的应用，在做本次课程设计的时候，自己也相继遇到了很多问题，很多自己的不足之处也暴露了出来，但是因为知道了自己哪里有不足，所以可以针对不足去弥补，学到的东西更深刻，更透彻，所以本次课程设计使我对算法有了更好的理解。经过这段时间的上机实践学习，我对C++有了更进一步的认识和了解，要想学好它要重在实践，要通过不断地练习和上机编程才能熟练地掌握它。当然，在上机的同时也要有一定的C++理论知识，这样才能使理论和实践相互促进，在这两方面都有所提高。与此同时，我也认识到了算法设计的重要性。算法设计为我们提供了很好的结构和算法来实现一些比较难的程序。同时，它还能帮助我们减少程序在时间和空间上的花费。在许多与编程有关的地方都要用到算法设计的知识。通过本次课程设计，我对拓扑排序和关键路径都有了更深的了解，和更加熟练的应用。虽然过去编写程序也经常用到拓扑排序，但是当时根本就不了解拓扑