输出DAG的所有拓扑排序序列

1、1/21/2输出DAG的所有拓扑排序序列1.课程设计内容与要求用字符文件提供数据建立DAG（有向无环图）合适的存储结构。编写程序，输出所有可能的拓扑排序序列。要求输出的拓扑排序结果用顶点序号或字母表示。输出结果需存于字符文件。输出结果中应显示全部拓扑排序序列的数目。如果DAG存在环（即拓扑排序失败），输出结果中应显示拓扑排序序列的数目为0。课程设计报告要求给出详细算法描述，在结论部分应分析算法的时间复杂度和空间复杂度，并给出分析的结果。2.程序设计报告2.1总体设计首先创建有向图邻接表，从文件中读取邻接表的顶点和边数，然后再读取临接矩阵的边，每读取一条边，都将其插入到邻接矩阵中。采用递归调用判

2、断该邻接矩阵是否为有向无环图（DAG），如果是则找出邻接矩阵中所有的拓扑排序，并打印到屏幕上。若含有环，则不打印结果。2.2详细数据结构设计采用结构体存储邻接表的表结点，该结构包含两个整型数据域和两个该结构体的指针域。其结构如下：typedefstructnodeinti,j;/弧的端点下标structnode*hlink;structnode*vlink;OLANode;采用结构体存储邻接表的头结点，该结构包含一个三个整型属于和两个表结点类型的指针域，其结构如下：typedefstructElemTpdata;/顶点数据（可选）InfoTpinfo;/顶点信息（可选）inti;/顶点下标OL

3、ANode*firstin;OLANode*firstout;OLHNode;采用结构体存储邻接表，该结构包含一个头结点数组，和两个整型数据域，其结构如下：typedefstructOLHNodehMAX_N;/头结点形成数组intn,e；/n：实际顶点数;e:边或弧的数目/Graphkindkind;/图类型（可选）OLGraph；采用队列存储入度为零的表结点，队列的结构体包含一个整型数组，三个整型数据域，其结构如下：typedefstructElemType*elem；intn；/队列容量intf；/队头指针intr；/队尾指针SqQueue；2.2详细算法设计该程序的核心算法是拓扑排序，

4、拓扑排序的算法如下：（1）、采用邻接表作为有向图的存储结构。（2）、用一个数组indegree0.n-1来保存各顶点的入度；（3）、为避免检测入度为0的顶点，设置l个队列Q存放入度为0的顶点。并设置另一个队列S存放当前已经遍历过的顶点。开始排序前，扫描indegree向量，将入度为0的顶点压入队列Q，每次输出入度为0的顶点时，只需要做出队操作即可。删除入度为0的顶点以及所有以它为尾的弧，只需要将该顶点的所有邻接至顶点的入度减1,若减到0则入队Q。队Q空时结束循环。（4）、当采用递归调用的方法输出所有拓扑排序时，每递归一层都新建一个队列Q保存当前入度为0的顶点，在while循环中删除入度为0的顶

5、点以及所有以它为尾的弧，只需要将该顶点的所有邻接至顶点的入度减1,若减到0则入队Q，此操作更新indegree数组。同时将遍历过的顶点入队S。更新完indegree数组，调用递归函数，直至遍历所有点或队列为空时结束递归。（5）、结束当前拓扑排序的递归时,判断是否遍历了所有点,若未遍历所有点,说明存在环,则不打印拓扑排序的结果。若遍历了所有点，则打印拓扑排序的结果（即队列S中的元素）。递归函数回溯至上一级，并删除队列S中的队尾元素。判读当前递归函数内队列Q是否为空，若不为空则继续while循环，调用递归函数进入下一层次递归。若为空则继续回溯。主要函数说明：voidinitQueue(SqQueu

6、e&q)/初始化队列voidclearQueue(SqQueue&q)/清空队列intempty(SqQueue&q)/判断队空intfull(SqQueue&q)/判断队满intinQueue(SqQueue&q,ElemTypee)/队头入队intdelTail(SqQueue&q)/删除队尾intoutQueue(SqQueue&q,ElemType&e)/队头出队，返回出队元素voidcrtGraph1(OLGraph&G)/构建有向图邻接表voidcopy(intindegree,intdegree,intn)/将数组indegree复制给degreevoidfun(OLGraphG

7、,SqQueueS,intindegree,intcount,int&n)/递归调用函数，判断是否为DAGintTopologicalSort_Stack(OLGraphG)/拓扑排序子程序,返回拓扑排序的种数3.程序测试报告测试用例1：(预期结果)文件输入的数据：(8,10)/矩阵的顶点个数各边数(0,1)/以下均为边(1,2)(2,3)(4,1)(4,2)(4,5)(5,6)(6,7)(6,3)(2,6)运行结果：运行结果：1/21/2hdhahdhdhdhdhdA-$2MSEEEEEGEcctfb-bcA-ffbbbbbbbb-Arx.fLtjZiK-LMAx4Ha,d.现o0-E2DL

8、2L测试用例2：(存在环时)文件输入：(8,10)(0,1)(1,2)(2,3)(4,1)(2,4)(4,5)(5,6)(6,7)(6,3)(2,6)图的结构：4.结论测试用例一分析：如图所示，共有十四种拓扑排序结果1/21/2时间复杂度分析：初始化indegree数组：n+e次循环输出各顶点入读：n次循环每次查询入度为0的顶点并入队：n次循环输出所有顶点：e次循环时间复杂度为：T(n,e)=Q(n+e)空间复杂度分析：递归的深度：n空间复杂度为：S(n)=Q(n)5.源程序附录#include#include#include#include#defineMAX_N20/最大顶点数#defin

9、eQueue_size20typedefintElemTp;typedefintElemType;typedefcharInfoTp;/表结点结构typedefstructnode/doublew;/弧的权重（可选）/InfoTpinfo;/弧的信息（可选）inti,j;/弧的端点下标structnode*hlink;structnode*vlink;OLANode;/头结点结构typedefstructElemTpdata;/顶点数据（可选）InfoTpinfo;/顶点信息（可选）inti;/顶点下标OLANode*firstin;OLANode*firstout;OLHNode;/十字链表

10、结构typedefstructOLHNodehMAX_N;/头结点形成数组intn,e；/n：实际顶点数;e：边或弧的数目/Graphkindkind;/图类型（可选）OLGraph;typedefstructElemType*elem;intn;/队列容量1/21/21/2intf;/队头指针intr;/队尾指针SqQueue;/初始化队列voidinitQueue(SqQueue&q)q.n=Queue_size;q.r=q.f=-1;/初始化指针q.elem=(ElemType*)malloc(q.n*sizeof(ElemType);/清空队列voidclearQueue(SqQueu

11、e&q)q.r=q.f=-1;/*r=f=-1n-1区间的任一整数均可*/判断队空intempty(SqQueue&q)returnq.f=q.r;/判断队满intfull(SqQueue&q)return(q.r+1)%q.n=(q.f+q.n)%q.n;/队尾入队intinQueue(SqQueue&q,ElemTypee)if(q.r+1)%q.n=(q.f+q.n)%q.n)printf(队满n);exit(0);q.r=(q.r+1)%q.n;q.elemq.r=e;return1;/入队成功返回1/删除队尾intdelTail(SqQueue&q)if(q.r=q.f)printf

12、(队空n);exit(0);q.r=(q.r-1)%q.n;return1;/入队成功返回1/队头出队intoutQueue(SqQueue&q,ElemType&e)if(q.r=q.f)printf(队空n);exit(0);q.f=(q.f+1)%q.n;e=q.elemq.f;return1;/出队成功返回1/构建有向图邻接表voidcrtGraph1(OLGraph&G)inti,j,k;FILE*f;charc=a;if(f=fopen(input.txt,r)=NULL)printf(文件打开失败!n);exit(0);if(!f)return;fscanf(f,(%d,%d)n

13、,&G.n,&G.e);/读入顶点数和弧数for(i=0;iG.n;i+)G.hi.i=i;/初始化顶点序号G.=c;c+;G.hi.firstin=G.hi.firstout=NULL;for(k=0;kG.e;k+)建立e个表结点fscanf(f,(%d,%d)n,&i,&j);/读入弧的始点和终点序号OLANode*pr,*p,*q=newOLANode;q-i=i;q-j=j;q-hlink=q-vlink=NULL;/水平链表按弧头序号升序pr=NULL;p=G.hi.firstout;while(p&p-jhlink;if(pr=NULL)q-hlink=p;G.hi

14、.firstout=q;elsepr-hlink=q;q-hlink=p;/垂直链表按弧尾序号升序pr=NULL;p=G.hi.firstin;while(p&p-ivlink;if(pr=NULL)q-vlink=p;G.hi.firstin=q;elsepr-vlink=q;q-vlink=p;/建立表结点循环结束fclose(f);/函数结束/将数组indegree复制给degreevoidcopy(intindegree,intdegree,intn)for(inti=0;in;i+)degreei=indegreei;fun(G,S,indegree,count,n);1/21/2/

15、递归函数voidfun(OLGraphG,SqQueueS,intindegree,intcount,int&n)inti;if(count=G.n)n+;cout第n种情况:；while(!empty(S)outQueue(S,i);coutG.t;coutendl;return;SqQueueQ;OLANode*p;initQueue(Q);for(i=0;ihlink)-degreep-j;fun(G,S,degree,count,n);deletedegree;count-;delTail(S);clearQueue(Q);拓扑排序，返回true,表示拓扑排序成功；返回false表示有环intTopologicalSort_Stack(OLGraphG)/首先创建并初始化indegree数组int*indegree=newintG.n;inti,count=0;intn=0;OLANode*p;SqQueueS;for(i=0;iG.n;i+)indegreei=0;给indegree数组赋值，并输出各个顶点的入度coutendlAOV网络的边:endl;for(i=0;ihlink)indegr