有向图拓扑排序算法的实现

数据结构课程设计设计说明书有向图拓扑排序算法的实现学生姓名学号班级成绩指导教师魏佳计算机科学与技术系2010年2月22日数据结构课程设计评阅书题目有向图拓扑排序算法的实现学生姓名学号指导教师评语及成绩成绩：教师签名：年月日辩论教师评语及成绩成绩：教师签名：年月日教研室意见总成绩：室主任签名：年月日注：指导教师成绩60%，辩论成绩40%，总成绩合成后按五级制记入。课程设计任务书2010—2011学年第二学期专业：信息管理与信息系统学号：姓名：课程设计名称：数据结构课程设计设计题目：有向图拓扑排序算法的实现完成期限：自2011年2月22日至2011年3月4日共2周设计内容：用C/C++编写一个程序实现有向图的建立和排序。要求建立有向图的存储结构，从键盘输入一个有向图，程序能够自动进行拓扑排序。设计要求:1〕问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？〔而不是怎么做？〕限制条件是什么？确定问题的输入数据集合。2〕逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原那么划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义〔包括数据结构的描述和每个根本操作的功能说明〕，各个主要模块的算法，并画出模块之间的调用关系图；3〕详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，根本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和根本操作做出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；4〕程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时参加一些注解和断言，使程序中逻辑概念清楚；5〕程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；6〕结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析；7〕编写课程设计报告；以上要求中前三个阶段的任务完成后，先将设计说明数的草稿交指导老师面审，审查合格前方可进入后续阶段的工作。设计工作结束后，经指导老师验收合格后将设计说明书打印装订，并进行辩论。指导教师〔签字〕：教研室主任〔签字〕：批准日期：2011年2月21日摘要设计了一个对有向图进行拓扑排序的算法，该算法首先用邻接表构造有向图的存储结构，然后对此有向图进行拓扑排序，输出拓扑排序的结果。本算法采用VC++作为软件开发环境，以邻接表作为图的存储结构，将图中所有顶点排成一个线性序列，输出拓扑排序结果。该算法操作简单，易于用户操作接受。关键词：数据结构；有向图；拓扑排序目录TOC\o"1-3"\u1课题描述 12问题分析和任务定义 23逻辑设计 333.2抽象数据类型34详细设计 44.1C语言定义的相关数据类型44.2主要模块的伪码算法44.2.1主函数伪码算法：44.2.2邻接表伪码算法：44.2.3拓扑排序的伪码算法：54.3主函数流程图65程序编码 76程序调试与测试 137结果分析 168总结 17参考文献 181课题描述根根据设计要求运用c语言程序设计了一个对有向图进行拓扑排序的算法，该算法首先用邻接表构造有向图的存储结构，然后对此有向图进行拓扑排序，输出拓扑排序的结果。如给定一个有向无环图如所示。在此图中，从入度为0的顶点出发，删除此顶点和所有以它为尾的弧；重复直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。图1.1有向无环图开发工具：visualc++6.0。2问题分析和任务定义对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对由某个集合上的一个偏序得到该集合上的一个全序，这个操作就称之为拓扑排序。偏序集合中仅有局部成员之间颗比拟，而全序指集合中全体成员之间均可比拟，而由偏序定义得到拓扑有序的操作便是拓扑排序。一个表示偏序的有向图可用来表示一个流程图，通过抽象出来就是AOV-网，假设从顶点i到顶点j有一条有向路径，那么i是j的前驱，j是i的后继。假设〔i，j〕是一条弧，那么i是j的直接前驱；j是i的直接后继。在AOV-网中，不应该出现有向环，用拓扑排序就可以判断网中是否有环，假设网中所有顶点都在它的拓扑有序序列中，那么该AOV-网必定不存在环。3逻辑设计抽象数据类型ADTALGraph｛数据对象：D={V|V是具有相同特性的数据元素的集合，即顶点集}数据关系：R={<v,w>|v,w∈V,<v,w>表示顶点v到顶点w的弧}根本操作P:CreatGraphlist(ALGraph*G)初始条件：成对输入顶点集V中的点。操作结果：构造图G的邻接表。FindInDegree(ALGraphG,intindegree[])初始条件：图G的邻接表中存在结点V。操作结果：找到图中入度为0结点。Initgraph()操作结果：完成图形初始化。TopologicalSort(ALGraphG)初始条件：构造的有向图G已初始化。操作结果：对于有向图G根据邻接存储表进行拓扑排序。}4详细设计4.1C语言定义的相关数据类型#definemax_vextex_num20/*宏定义最大顶点个数*/#definestack_init_size100/*宏定义栈的存储空间大小*/typedefintElemType;typedefstructVNode/*邻接表头结点的类型*/{intdata;/*顶点信息,数据域*/}VNode,AdjList[MAX_VEXTEX_NUM];/*AdjList是邻接表类型*/typedefstruct{AdjListvertices;/*邻接表*/intvexnum,arcnum;/*图中顶点数vexn和边数arcn*/}ALGraph;/*图的类型*/typedefstruct//构建栈{ElemType*base;/*数据域*/ElemType*top;/*栈指针域*/intstacksize;}SqStack;4.2主要模块的伪码算法主函数伪码算法：开始{创立及输出邻接表CreatGraphlist(&G);输出排序后的输出序列TopologicalSort(G);}结束邻接表伪码算法：#defineMAX_VEXTEX_NUM20typedefstructVNode/*邻接表头结点的类型*/{intdata;/*顶点信息,数据域*/ArcNode*firstarc;/*指向第一条弧*/}VNode,AdjList[MAX_VEXTEX_NUM];/*AdjList是邻接表类型*/typedefstruct{AdjListvertices;/*邻接表*/intvexnum,arcnum;/*图中顶点数vexn和边数arcn*/}ALGraph;/*图的类型*/开始{定义一个指针P置i的初值为1邻接表中所有头结点指针置初值当i<=G-vexnum时自加，执行下面操作：输出数据域里的顶点信息使指针p指向顶点i第一条弧的头结点输出访问顶点使指针p指向顶点i的下一条弧的头结点类此循环到输出最后一个顶点}结束拓扑排序的伪码算法：开始{引入栈操作函数和入度操作函数访问邻接存储表中的顶点nIf该顶点入度为0顶点进栈循环操作到所有顶点入栈当栈不为空顶点出栈}结束4.3主函数流程图主函数流程图如图4.3所示：图4.3主函数程序流程图5程序编码#include<stdio.h>#include<stdlib.h>#definetrue1#definefalse0#defineMAX_VEXTEX_NUM20#defineM20#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10/*图的邻接表存储结构*/typedefstructArcNode/*弧结点结构类型*/{intadjvex;/*该弧指向的顶点的位置*/structArcNode*nextarc;/*指向下一条弧的指针*/}ArcNode;typedefstructVNode/*邻接表头结点类型*/{intdata;/*顶点信息*/ArcNode*firstarc;/*指向第一条依附于该点的弧的指针*/}VNode,AdjList[MAX_VEXTEX_NUM];/*AdjList为邻接表类型*/typedefstruct{AdjListvertices;intvexnum,arcnum;}ALGraph;/**/voidCreatGraph(ALGraph*G)/*通过用户交互产生一个图的邻接表*/{intm,n,i;ArcNode*p;printf("=======================================================");printf("\n输入顶点数:");scanf("%d",&G->vexnum); printf("\n输入边数:"); scanf("%d",&G->arcnum); printf("=======================================================");for(i=1;i<=G->vexnum;i++)/*初始化各顶点*/ {G->vertices[i].data=i;/*编写顶点的位置序号*/G->vertices[i].firstarc=NULL; }for(i=1;i<=G->arcnum;i++)/*记录图中由两点确定的弧*/ {printf("\n输入确定弧的两个顶点u，v:");scanf("%d%d",&n,&m);while(n<0||n>G->vexnum||m<0||m>G->vexnum) {printf("输入的顶点序号不正确请重新输入:");scanf("%d%d",&n,&m); }p=(ArcNode*)malloc(sizeof(ArcNode));/*开辟新的弧结点来存储用户输入的弧信息*/if(p==NULL) {printf("ERROR!");exit(1); }p->adjvex=m;/*该弧指向位置编号为m的结点*/p->nextarc=G->vertices[n].firstarc;/*下一条弧指向的是依附于n的第一条弧*/G->vertices[n].firstarc=p; }printf("=======================================================");printf("\n建立的邻接表为:\n");/*打印生成的邻接表〔以一定的格式〕*/for(i=1;i<=G->vexnum;i++) {printf("%d",G->vertices[i].data);for(p=G->vertices[i].firstarc;p;p=p->nextarc)printf("-->%d",p->adjvex);printf("\n"); }printf("=======================================================");}/**/typedefstruct/*栈的存储结构*/{int*base;/*栈底指针*/int*top;/*栈顶指针*/intstacksize;}SqStack;/**/voidInitStack(SqStack*S)/*初始化栈*/{S->base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));if(!S->base)/*存储分配失败*/{printf("ERROR!");exit(1);}S->top=S->base;S->stacksize=STACK_INIT_SIZE;}/**/voidPush(SqStack*S,inte)/*压入新的元素为栈顶*/{if(S->top-S->base>=S->stacksize){S->base=(int*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(int));/*追加新空间*/if(!S->base)/*存储分配失败*/ {printf("ERROR!");exit(1); }S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;}*S->top++=e;/*e作为新的栈顶元素*/}/**/intPop(SqStack*S,int*e)/*弹出栈顶，用e返回*/{if(S->top==S->base)/*栈为空*/{returnfalse;}*e=*--S->top;return0;}/**/intStackEmpty(SqStack*S)/*判断栈是否为空，为空返回1，不为空返回0*/{if(S->top==S->base)returntrue;elsereturnfalse;}/**/voidFindInDegree(ALGraphG,intindegree[])/*对各顶点求入度*/{inti;for(i=1;i<=G.vexnum;i++)/*入度赋初值0*/ {indegree[i]=0; }for(i=1;i<=G.vexnum;i++) {while(G.vertices[i].firstarc) {indegree[G.vertices[i].firstarc->adjvex]++; /*出度不为零，那么该顶点firstarc域指向的弧指向的顶点入度加一*/G.vertices[i].firstarc=G.vertices[i].firstarc->nextarc; } }}/**/voidTopoSort(ALGraphG){intindegree[M];inti,k,n;intcount=0;/*初始化输出计数器*/ArcNode*p;SqStackS;FindInDegree(G,indegree);InitStack(&S);for(i=1;i<=G.vexnum;i++) {printf("\n"); printf("indegree[%d]=%d\n",i,indegree[i]);/*输出入度*/ }printf("\n");for(i=1;i<=G.vexnum;i++)/*入度为0的入栈*/ {if(!indegree[i])Push(&S,i); }printf("=======================================================");printf("\n\n拓扑排序序列为:");while(!StackEmpty(&S))/*栈不为空*/ {Pop(&S,&n);/*弹出栈顶*/printf("%4d",G.vertices[n].data);/*输出栈顶并计数*/count++;for(p=G.vertices[n].firstarc;p!=NULL;p=p->nextarc)/*n号顶点的每个邻接点入度减一*/ {k=p->adjvex;if(!(--indegree[k]))/*假设入度减为零，那么再入栈*/ {Push(&S,k); } } }if(count<G.vexnum)/*输出顶点数小于原始图的顶点数，有向图中有回路*/ {printf("ERROR出现错误!"); }else {printf("排序成功!"); }}/**/main(void)/*编写主调函数以调用上述被调函数*/{ALGraphG;CreatGraph(&G);/*建立邻接表*/TopoSort(G);/*对图G进行拓扑排序*/ printf("\n\n");system("pause"); /*调用系统的dos命令：pause;显示:"按任意键继续..."*/return0;}6程序调试与测试〔1〕当为有向无环图：图6.1有向无环图输出结果如图6.2为：图6.2有向无环图的输出结果〔2〕当为有向有环图结构如图6.3所示：图6.3有向有环图结构输出结果如图6.4所示：图6.4有向有环图的输出〔3〕输入检验图如图6.5所示：图6.5检验图由邻接表定义可以得到上图的邻接表如图6.6所示：图6.6邻接表其中一种拓扑序列：2713465将图输入到程序中结果如图6.7所示：图6.8检验图的输出所得结果与预计结果一致。7结果分析对于算法的时间复杂度和空间复杂度，拓扑排序实际是对邻接表表示的图G进行遍历的过程，每次访问一个入度为零的顶点，假设图G中没有回路，那么需扫描邻接表中的所有边结点，在算法开始时，为建立入度数组D需访问表头向量中的所有边结点，算法的时间复杂度为O(n+e)。其次