王赵彬-0804011020-AOV网拓扑排序

合肥学院计算机科学与技术系课程设计报告2009～2010学年第二学期课程数据结构与算法课程设计名称AOV网拓扑序列生成学生姓名王赵彬学号0804011020专业班级08计科(1)班指导教师吕刚、胡春琳2010年06月一、问题分析和任务定义1、题目：对于给定的AOV网，要求实现所有的拓扑排序。2、要求和任务：在这个问题中，要解决的问题是：任意给出的一个AOV图，都要实现它所有的拓扑排序序列。要解决这个问题，首先，要选取一种数据结构来存放这个AOV网中每个顶点的各种信息，包括在图中的位置和每个顶点的入度变化。其次，要采取一种什么样的思想，使算法能输出所有的拓扑排序。通过独立解决这些问题，提高在数据结构的逻辑特性和表示、数据结构的选择应用、算法的设计及其实现等方面的能力，加深对课程基本内容的理解和综合运用，提高分析和解决实际问题的能力，达到理论和实际应用相结合。3、原始数据输入、输出格式：输入格式：原始数据要求输入顶点数目、边的数目、每条边的起始点和终点在邻接表中的位置。例如图1所示的图输入如下：pleaseinputvexnum:5pleaseinputarcnum:4请依次输入每条弧的起点和终点序号：01032334输出格式：输出的是所有拓扑排序的种数，和每种排序的具体情况。例如：v0v1v2v3v4v0v2v1v3v4…………………v2v0v3v4v1该AOV网有7种拓扑排序序列。4、算法测试用例设计：1〉设计一个简单的AOV网，如图1，应该输出7种拓扑排序。2〉设计一个有回路的图，如图2，结果应该是不能进行拓扑排序。3〉设计一个稍复杂的AOV网，如图3，应该输出74种拓扑排序。图1.简单的AOV网测试用例V0V1V2V3V4V0图2。一个有回路的图图3.一个稍复杂的AOV网拓扑排序演示：（其中一个序列的）V0V1V2V3V4V5V6V7V0V1V2V3V4图4拓扑排序过程注意：①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。②若图中存在有向环，则不可能使顶点满足拓扑次序。③一个DAG的拓扑序列通常表示某种方案切实可行。【例】一本书的作者将书本中的各章节学习作为顶点，各章节的先学后修关系作为边，构成一个有向图。按有向图的拓扑次序安排章节，才能保证读者在学习某章节时，其预备知识已在前面的章节里介绍过。④一个DAG可能有多个拓扑序列。【例】对图G9进行拓扑排序，至少可得到如下的两个(实际远不止两个)拓扑序列：C0，C1，C2，C4，C3，C5，C7，C8，C6和C0，C7，C9，C1，C4，C2，C3，C6，C5。⑤当有向图中存在有向环时，拓扑序列不存在【例】下面(a)图中的有向环重排后如(b)所示，有向边v3，vl和其它边反向。若有向图被用来表示某项工程实施方案或某项工作计划，则找不到该图的拓扑序列(即含有向环)，就意味着该方案或计划是不可行的。二、数据结构的选择和概要设计1、数据结构本问题中，我将采用三种数据结构，邻接表，队列，数组。1邻接表：邻接表是图的链式存储结构，在邻接表的存储结构中，图中的每个顶点对应一个单链表。从拓扑排序的步骤个方法来看，在整个排序过程中需要频繁地检查顶点的前驱以及作删除顶点和弧的操作、恢复顶点和顶点前驱入度的操作。所以，可以采用邻接表作为有向无环图的存储结构。为了快速的判断顶点是否有前驱，可以在表头结点中增加一个“入度域（indegree）”用来指示顶点当前的入度。当indegree域的值为0时，表明该顶点没有前驱，可以加入到结果序列中。而删除顶点及以它为尾的弧的操作，可以通过把该顶点的所有邻接点的入度域减一来完成，恢复则入度域加一。邻接表的定义如下：V6typedefstructARCNODE{intadjvex;//邻接点的位置ARCNODE*nextarc;//指向下一个结点}ARCNODE;//邻接表中的结点类型typedefstructVEXNODE{intvexdata;//顶点信息intindegree;//每个顶点的入度ARCNODE*firstarc;//指向第一个邻接结点}VEXNODE,AdjList[MAX];//邻接表的表头结点类型typedefstruct{AdjListvexs;//表头结点数组intvexnum,arcnum;//顶点数、弧数}ALGraph;//邻接表类型建立邻接表例如一个有向图的结构为：其邻接表的形式如下：V1V2V3V4V6V5图5有向图示例021230∧∧∧∧∧34245552∧图6有向图的邻接表第一列的数为各顶点的原始度数。2顺序表：在整个拓扑排序的过程中，把满足条件（在此轮中未访问过visited[i]=0以及入度为0）的顶点加入到顺序表的末尾，使last加1。当一轮排序结束后，输出顺序表中的排序。接着，是恢复部分，每恢复一步，都要把visit[i]置0并且相应的入度加1，把这个顶点从顺序表中删除，重新加入到图中，进行下一轮的拓扑排序。顺序表定义如下：typedefstruct{VEXNODEdata[MAX];intlast;}Sequenlist;//顺序表类型3数组：产生所有的拓扑排序是一个递归（回溯）过程。其中，定义的visited[MAX]数组是一个辅助变量，数组元素的初值为0，当第i个顶点被访问后，便置visited[i]为1.记录该顶点是否被访问过。Visited[MAX]；2、设计思想因为这个课程设计题目是让AOV网产生所有的拓扑排序，所以我想必然要用到递归或者叫回溯的思想。于是，我上图书馆去找了一些有递归内容的书，好好的研究了一下。复习以前学过的一些有递归思想的例子，再回归到这个课题上，反反复复的举例子，最后发现，这个课题递归思想跟那些还是有些不一样。因为这个课题中的数据时时刻刻既要删除又要保留，因为它会反反复复的用到，不只是一次就可以结束。几天以后，大致的思想有了。但是，当时用的不是顺序表来存储要输出的顶点，一开始是用到堆表，后来该为用链表，最后才发现，其实只要用顺序表就可以简单的解决这部分问题。用顺序表后的删除和插入都很简单，好实施，只要在表尾插入或是删除即可。主要用到三部分，一、从图中删除，添加到顺序表中；二、递归；三、把删除的顶点和边恢复到图中并从顺序表中删除。首先，在整个图中搜索即没有被访问过而且入度为0的顶点Vi，进行拓扑排序。在拓扑排序的函数里，首先将这个顶点加入到顺序表中，然后将这个顶点标志为被访问过。把以这个顶点为起点的邻接点的入度均减1.然后，判断顺序表的表长是否等于图的顶点数。如果不相等的话，则继续判断图中是否还存在满足拓扑排序条件的顶点，若存在就再次调用拓扑排序函数。接下来，就是使刚排序过的顶点Vi的标志恢复到原始状态0，每个以Vi为起点的邻接点的入度加1，恢复到原来的状态。把顶点Vi从顺序表中删除。如果，顺序表的表长等于图的顶点数，那么就输出这一种拓扑排序序列。计数器count加1.之后，就是采用递归，不断的调用拓扑排序函数，不断的恢复、删除，直到排出所有的拓扑序列。最后，如果count大于0的话，那么就输出有count中拓扑排序。否则，输出此图不是AOV网，无拓扑排序序列产生。3、AOV网产生拓扑序列流程图1以邻接表创建AOV网，creat_AdjlistGraph();2拓扑排序函数的流程图Lastusort(G,L,I);开始定义表头结点数组al输入顶点数n和边数e输入e条边的起点值j和终点值k将Vk的入度加一，并将结点Vk加入到链表中；边数从0到e初始化al的各项值：al[i].vexdata=i;al[i].indegree=0;al[i].firstarc=NULL;（i=0to图的顶点数）定义图algn=alg.vexnum顶点数；e=alg.arcnum边数i赋初值0将al[]中的值、入度、指针分别赋给图alg中数组vexs[]的.各值；i的值递增1i边数e？NY结束图7AOV网产生拓扑序列流程图开始插入SqLinsert(L,vexs[i])标志数visited[i]赋初值0Vi指向第一个结点指针PP!=NULL？P指向顶点VjVj的入度减1P指向链表下一结点顺序表长=顶点数？输出Output(L)计数器Count加1;K赋初值0Visited[k]==0且Vk入度为0？调用函数Topusort(L,G,k);K的值递增1k顶点数？NY3顺序表相关运算的流程图Vi指向的第一个结点的指针PP！=NULL？P指向顶点VjVj的入度加1P指向链表下一结点调用删除函数SqLdelete(L,vexs[i])结束YN图8拓扑排序函数的流程图4模块之间调用的流程图开始定义顺序表A顺序表置空：setnull()表长L-top+1赋初值0插入：SqLinsert(L,vexs[i])删除：SqLdelete(L,vexs[i]);输出：output(L);表长加1即L-top+1递增1把结点X赋给顺序表最后一位L-r[L-top]表长减1；L-top+1减1I赋初值0输出ViI的值递增1i表长?结束NY图9顺序表相关运算的流程图开始置空顺序表A，表长赋初值0用邻接表建立图G，调用G=creat_AdjlistGraph();i赋初值0初始化标志数组，visited[i]置0i的值递增1iG.顶点数?J赋初值0Visited[j]=0且Vj入度为0？调用函数Topusort(G,L,i);j的值递增1jG.顶点数?Count0？此图不是AOV网，无拓扑排序序列结束YNNY该图有count种排序YNYN图10模块之间调用的流程图三、详细设计和编码1.主函数main()在main()函数里，首先定义一个顺序表，然后把它置空。接着，以邻接表创建一个图，并且把它赋给图G。接着，把全局变量数组visited[]初始化。对于整个图中，没被访问过的而且入度为0的顶点进行拓扑排序。如果常量count等于0的话，说明图有回路，不能拓扑排序。否则，在拓扑排序函数中会输出所有的拓扑排序序列。voidmain(){SequenlistA,*L=&A;L=(Sequenlist*)malloc(sizeof(Sequenlist));Setnull(L);ALGraphG;G=creat_AdjListGraph();for(n=0;nG.vexnum;n++){visited[n]=0;}inti;printf(该图的所有拓扑排序为：\n);for(i=0;iG.vexnum;i++)if(G.vexs[i].indegree==0&&visited[i]==0)lastusort(L,G,i);printf(该AOV图有%d种拓扑排序.\n,count);if(count=0)printf(此图不是有向无环图，故不能拓扑排序.\n);}2.creat_AdjlistGraph()以邻接表的数据结构存储图，图中的每个顶点对应一个单链表。首先，输入图中的顶点数n和边数e，申请一个表头结点数组al[].初始化表头结点数组的时候，把顶点的序号就赋给顶点信息。接着，依次输入每条边的起始结点和终止结点在邻接表中的位置。把终止结点的入度值加1，结点用头插法插入到链表中。把顶点数n赋给图G.vexnum;边数e赋给G.arcnum;表头数组al[]各项的数据赋给图G.vexs[].然后返回图即可。ALGraphcreat_AdjListGraph(){intn,e,i,j,k;ARCNODE*p;AdjListal;printf(pleaseinputvexnum:\n);scanf(%d,&n);for(i=0;in;i++){//初始化表头结点数组al[i].vexdata=i;al[i].indegree=0;al[i].firstarc=NULL;}printf(pleaseinputarcnum:\n);scanf(%d,&e);printf(请依次输入弧:\n);for(i=0;ie;i++){scanf(%d%d,&j,&k);//