AOV网的拓扑序列生成-数据结构与算法课程设计报告

1、 AOV 拓扑序列生成课程设计报告题目： AOV 网的拓扑序列生成一、问题分析和任务定义本次课程设计要求对于给定的AOV 网求出它所有拓扑序列。 AOV 网（ Activityon VertexNetwork ）是一个有向无环图（Directed Acycline Graph， DAG 图）。 AOV 网中，如果顶点Vi表示的活动在和顶点Vj表示的活动之前进行，则称 Vi是 Vj的前驱顶点， Vj是 Vi后继顶点。拓扑排序就是将有向无环图中的各个顶点排成一个序列， 使得所有的前去后继关系都得到满足。对于相互之间没有次序关系的顶点，在拓扑排序的序列中可以处在任意的位置。因此，拓扑排序的结果往往是

2、不唯一的。 本次课程设计的主要任务就是将给定的一个 AOV 网输出所有的该种序列。下面以图一为例：对于该图其所有的拓扑序列如下：1）、V0 V1 V2 V3 V42）、V0 V1 V2 V4 V33）、V1 V0 V2 V3 V44）、V1 V0 V2 V4 V3二、数据结构的选择和概要设计对于给出的 AOV 网首先要确定它的存储方式，这里选择邻接表，它的具体数据结构如下图二所示：typedef struct node/邻接表中的结点类型int number;/结点编号struct node *next;/指向下一个结点int info;/与表头结点边的信息ListNode;typedef s

3、truct/定义表头结点数组int number;/顶点信息ListNode *firstarc;/指向第一个邻接点AdjList;/表头结点类型typedef struct/邻接表类型AdjList headmax_vertex_num;/邻接表的组int vexnum ,edgnum;/顶点个数、边的个数ALGraph;- 1 - AOV 拓扑序列生成课程设计报告一种拓扑序列的生成一般有一下步骤：1）、从有向无环图中选择一个没有前驱结点的顶点并加入到结点的序列中；2）、从有向无环图中删除该顶点以及该顶点为尾的所有的弧；3）、重复（ 1）（ 2）的步骤。在整个拓扑排序的过程中需要频繁的检查顶

4、点的前驱以及作删除顶点和弧的操作，在这里我们用两个全局变量rudumax_vertex_num和visitedmax_vertex_num来分别实现这两个操作，如果 rudui为零则表示无前驱结点，如果 visitedi为零则表示没有被访问过。如果每删除一个结点就检查，那样的话时间复杂度将很大（等于遍历所有的顶点一遍），因此设计一个堆栈， 把检测到的入度为零的结点入栈。 每次删除顶点只要从栈中取出一个结点即可。这里堆栈也有一个数据结构，具体实现如图三所示：- 2 - AOV 拓扑序列生成课程设计报告typedef structint datamax_vertex_num;/堆栈数组int to

5、p;/栈顶标志Stack;/顺序表类型但是如果需要实现一个AOV 网所有拓扑序列的生成则不止如此。在每找到一个符合要求的结点后入栈， 从而实现一种拓扑排序。在一趟拓扑排序结束后，应该进行恢复删除的结点和删除的弧， 并标记已经有过的序列，在恢复某几个个结点后进行下一次的拓扑排序。这里用到递归的思想。具体实现见下面的详细设计。三、详细设计和编码本次课程设计的重点在于输出AOV 网的所有拓扑序列，因此图的创建即输出之类的问题不做为重点，在此设计过程略过。对于拓扑排序算法流程图如图四所示：- 3 - AOV 拓扑序列生成课程设计报告实现该算法的具体编码如下：void topusort(Stack *L

6、,ALGraph *G,int i)/拓扑排序ListNode *P;int j,k;Soutput(L);Sinsert(L,i);/把顶点Vi 加入到栈中P=G-headi.firstarc;visitedi=1;/把排序过的点标记while(P)j=P-number;ruduj-; /把以 Vi 为头的终止结点入度减1P=P-next;if(L-top+1=G-vexnum)/判断栈中一种拓扑排序完成Soutput(L);printf(n);flag+;for(k=0;kvexnum;k+)/调用部分if(visitedk=0)&(ruduk=0)/如果 Vk 在此轮中未被访问过

7、且入度为0topusort(L,G,k);visitedi=0; /使 Vi 恢复为未访问P=G-headi.firstarc;while(P)j=P-number;ruduj+; /使 Vj 的入度恢复，加 1P=P-next;Sdelete(L);首先建立空栈， 并从第一个顶点开始进行拓扑排序。将该结点初始化为被访问过，并将图类的结点指针指向该编号的结点的表头数组 firstarc 域，把该顶点入栈后，将所有的以它为起点的弧都删掉， 即将弧的终点的入度都减一。 接着判断栈里面的数据个数是否和图顶点的个数一样，如果一样，则说明已经有一次拓扑排序完成，若不一样，则往下进行递归，再将符合条件的顶

8、点入栈， 直到一次拓扑排序完成的条件成立。 最后将顶点出栈， 恢复所有结点的入度，并准备下一趟拓扑排序。注意，在这里，可能再某一次拓扑排序完成后，所有的结点还没有来得及全部出栈，则发现了又可以入栈的情况如图一中的第二、四种排序就属于这种例子。四、上机调试这里我按照做课程设计的过程，将在其中遇到的问题和解决的办法都写在这里。1、课程设计开始，确定使用什么样的数据结构来存储图的时候，在邻接表和邻接矩阵之间进行徘徊。课本上使用的事邻接表，我当时想自己重新想，不按照课本上已设计好的来，但是在随后的操作中，发现在对于每个结点进行查找，删除等操作的时候才发现，用邻接矩阵很不方便，也正是在此才明白用邻接表的

9、优越性。- 4 - AOV 拓扑序列生成课程设计报告2、接下来就是创建图及输出图的一些函数的编写。这部分比较简单，除了一些语法错误外没有很严重的错误。这归功于以前在每次做实验的时候，这些基本的算法实现都有，直接按照这里的数据结构复制过来就行了。3、下面是本次课程设计的核心部分。eted_4236724d-324c-41f7-885d-7aa68e2f2d03-Numbered_2f6a0b55-a89b-4548-8dde-4cf7b7be7119$1）、在拓扑排序里面有必须设计一个数据结构来接受从图里面扫描出来没有入度且没有被访问过的结点。开始的时候对于该数据结构的选择很是犯难，这让开始一天

10、，程序毫无进展，想过用队列用栈用顺序表，但是思想都很混乱，在将以前写过的这些基础函数都用到这里还是不能解决问题。结果我想，这个数据结构到底有什么样的特点，要什么样的功能。基于该数据结构必须实现要将开始所有的符合条件的顶点保存起来，在判断保存的数据个数是否等于图的顶点个数后，才将所有的数据的输出，作为一次拓扑排序结束。在此判断符合栈的先进先出的特点，最终确定使用栈的数据结构。其实在这里对于栈到底是使用顺序栈还是链栈也是一个需要考虑的问题，一般链栈要比顺序栈要灵活，但是这里最终要用栈里面的元素个数判断是否一次拓扑排序结束，而顺序栈里面的栈顶元素正好有这个功能，所有这里选择用顺序栈。 2）、接下来就

11、是递归的具体实现了，开始的时候设计了一个计算入度的函数，但是后来发现这样做不好。第一、每次在删除顶点后都要计算入度，这样算法的性能里面时间和空间的复杂度都要大大的增加；第二，每次在计算入度的时候都要将图中所有的顶点都加进去，而在某些阶段，有许多的顶点已经相当于被删掉了，这样，失去了备份，连整个图都被破坏了程序会不稳定，健壮性得不到肯定。所以在这里使用了一个全局数组，用于存储每个顶点的入度，而不作为图的一个部分。这样在每次删除恢复顶点的时候都很简单。 3）、在这里遇到语法问题和很简单，大多使一些，参数没写，逗号没写等问题。仔细编译即便都得到解决了，但是下面的一些逻辑问题则用了我很多的时间去解决。

12、a、在删除以某个顶点为起点的弧时，没有用另外一个变量去代替形参 i, 导致出现混乱，有的顶点并没有作为第一个扫描对象而使许多排序情况没有。、在一次拓扑排序结束后，要恢复顶点的入度。在此开始没有想到要将该顶点的访问设为未访问，而至使只能输出一次拓扑排序。、在恢复某个单链表中所有的结点的入度的时候，要将该类型的指针先指向该表头数组的指针 firstarc 域 . 否则这部分的循环根本就没有运行。因为在前面指针 P 在删除弧的时候已经指空了。、在一般的情况都实现了过后有一个很严重的问题，就是在输入的图不是网的时候，无法判断。在最后想到如果不是AOV 网则不可能有拓扑排序在这里设一个全局变量count

13、 来接受拓扑排序的次数。若为0 则提示改图非法。4、 主要算法的时间和空间性能的分析。分析上述拓扑排序算法，如果有向图包含n 个顶点和e 条弧，则第一个for循环的时间复杂度为O(n). 在单链表中，查找邻接点的时间复杂度为O(e),e为图中边或弧的数目， 加上访问顶点的时间, 则每调用一次拓扑排序函数的时间复杂度为 O （ n+e）。算法的总时间复杂度取决于调用拓扑排序函数的次数。从空间性能上看，用到两个数组的辅助空间。以邻接表数据结构建立 AOV 网的时间复杂度为O(n) 。邻接表用到表头数组和链表，在单链表中插入一个结点时，需要运行while语句，所以插入单链表这部分算法的时间复杂度为O

14、(n) 。- 5 - AOV 拓扑序列生成课程设计报告5、主要的经验和体会。我觉的本此课程设计最大的收获就是学会按部就班的完成任务。首先想好用什么数据结构，主要的思想要明确的认定。然后选一个简单的例子，按照你选定的思想，一步一步的走程序，才能更早的发现程序还存在那些没有考虑到的缺陷。特别忌讳的是到写程序的时候，对主要思想和数据结构还不是很确定。最后在调试程序的阶段，这次我开始用设置断点的方法，一步一步看是否达到你要的理想结果，从而来找出程序中出错的地方。还有，一种方法也是用一个输出语句，分别放在程序的不同位置，通过输出结果，也可以快速判断出程序不能运行的是那一个语句了。从而方便你修改，快速得到

15、正确的结果。还有，这次调试的过程中，我表现的比以前要更有耐心，这也是一个很好的收获。还有一个更重要的体会就是，遇到不会的地方，我开始习惯到图书馆或是网上去找资料。这是一个很好的学习过程，它不仅仅是可以解决这个问题，关键是你会从找资料学习的过程中，会学好很多很多意想不到的知识。可能会比你手头上要学习的知识多得多。五、测试结果及其分析1、以图一为例（AOV 网）（ 1）、输入图， 结果如图五所示。在这里首先输入顶点数和边数，然后输入没条边的起点终点编号和权值。（ 2）、输出图的邻接矩阵。输入图过后按回车键显示图的邻接表，如图六所示。（ 3）、在显示完拓扑序列后按回车输出该图的所有拓扑排序序列，如图

16、七所示。- 6 - AOV 拓扑序列生成课程设计报告、在不循环使用程序的时候，程序全部运行结束，如图八。2、在给出的图不是AOV 网的时候提示出错。按图九所示的图，结果如图十所示。- 7 - AOV 拓扑序列生成课程设计报告六、用户使用说明本程序运行简单只要按照提示的步骤进行操作即可。要注意的是AOV网里面的每一条边都是有权值的， 虽然这个程序里面用不到，但是为了以后的扩展，我把权值也加入了，所以在输入边的时候需要注意。其他的都很简单明了。七、参考文献1.王昆仑，李红。数据结构与算法。北京：中国铁道出版社，2007 年 1 月。2.谭浩强。C程序设计。北京：清华大学出版社，2005 年 7 月

17、。3.陆宗骐。C/C+ 图像处理编程。北京：清华大学出版社，2005 年 1 月。4.谭浩强。C程序设计指导。北京：清华大学出版社，2005 年 7 月。5.曹衍龙，林瑞冲。C 语言实例解析。北京：人民邮电出版社，2005 年 3 月。八、附录#includestdio.h#includemalloc.h#includestdlib.h#define max_vertex_num 100 /顶点的最大个数typedef struct node/邻接表中的结点类型int number;/结点编号struct node *next;/指向下一个结点int info;/与表头结点边的信息ListNo

18、de;typedef struct/定义表头结点数组int number;/顶点信息ListNode *firstarc;/指向第一个邻接点AdjList;/表头结点类型typedef struct/邻接表类型AdjList headmax_vertex_num;/- 8 - AOV 拓扑序列生成课程设计报告int vexnum;/顶点个数表头数int edgnum;/边的个数ALGraph;typedef structint datamax_vertex_num;/堆栈数组int top;/栈顶标志Stack;/顺序表类型int rudumax_vertex_num;/定义一个存储每个顶点入

19、度的全局数组int visitedmax_vertex_num;/定义全局数组标志拓扑排序过程中是否访问过int flag=0;/接受拓扑排序的次数，若为0，则该图不是AOV 网ALGraph *create_AdjListGraph()ALGraph *T; ListNode *p; /定义指向结点的指针int i,j;/输入边是的起点和终点T=(ALGraph *)malloc(sizeof(ALGraph);/定义图printf(1、请输入顶点数:);scanf(%d,&T-vexnum);/输入顶点个数for(i=0;ivexnum;i+)/初始化表头结点数组T-headi.n

20、umber=i;/初始化结点编号rudui=0;/将每个节点的荼毒初始化为visitedi=0;T-headi.firstarc=NULL; /将表头结点数组的每个结点的指针域置空printf(2、请输入边数 :);scanf(%d,&T-edgnum);/输入边的个数printf(3、按起点终点权值的顺序一次输入边的序列:n);for(i=0;iedgnum;i+)printf(请输入第%d条边 :,i+1);p=(ListNode *)malloc(sizeof(ListNode);scanf(%d,&j);/输入这条边起始节点的编号scanf(%d,&p-numb

21、er);/输入这条边的终点的编号scanf(%d,&p-info);/输入这条边的权值printf(n);rudup-number+;/将插入边中结点的入度加1p-next=T-headj.firstarc;T-headj.firstarc=p;/将该结点插入到单链表中创建一条边return T;void print(ALGraph *T)/输出图的邻接表ListNode *p;int i;printf(表头数组 ( 该结点的入度 )与之有边的节点（该弧的权值）n);for(i=0;ivexnum;i+)printf(V%d（ %d）,T-headi.number,rudui);- 9

22、 - AOV 拓扑序列生成课程设计报告p=T-headi.firstarc;while(p)printf(-V%d(%d),p-number,p-info);p=p-next;printf(n);Stack *Setnull()/置栈空Stack *L;L=(Stack *)malloc(sizeof(Stack);L-top=-1;return(L);void Sinsert(Stack *L,int x)/入栈L-top=L-top+1;L-dataL-top=x;void Sdelete(Stack *L)/出栈L-top=L-top-1;void Soutput(Stack *L)/输

23、出栈中元素int i;for(i=0;itop+1;i+)printf(V%d ,L-datai);printf(n);void topusort(Stack *L,ALGraph *G,int i)/拓扑排序ListNode *P;int j,k;Soutput(L);Sinsert(L,i);/把顶点Vi 加入到顺序表中P=G-headi.firstarc;visitedi=1;/把排序过的点标记while(P)j=P-number;ruduj-; /把以 Vi 为头的终止结点入度减1P=P-next;if(L-top+1=G-vexnum)/判断顺序表中一种拓扑排序完成Soutput(L);printf(n);flag+;for(k=0;kvexnum;k+)/调用部分-10- AOV 拓扑序列生成课程设计报告if(visitedk=0)&(ruduk=0)/如果 Vk 在此轮中未被访问过且入度为0topusort(L,G,k);visitedi=0; /使 Vi 恢复为未访问P=G-headi.firstarc;while(P)j=P-number;ruduj+; /使 Vj 的入度恢复，加 1P=P-next;Sdelete(L);void caidan()printf(