拓扑排序实习报告

数据结构课程设计实习报告题目：拓扑排序班级：学号：姓名：2008年6月23日至6月27日实习报告[题目]拓扑排序。建立有向无环图，并输出拓扑的序列。[基本要求]输入顶点数和边，输出图的拓扑的序列。一．问题分析及任务定义对一个有向无环图(DirectedAcyclicGraph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若u，v∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(TopoiSicaiOrder)的序列，简称拓扑序列。拓扑排序演示：注意：①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。②若图中存在有向环，则不可能使顶点满足拓扑次序。③一个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）存储结构:采用链接表来存储图中的各条边的关系，链接表采用结点和链接点，其结构体分别如下所示：typedefstructedgenode//邻接点{intadjvex;//邻接点的序号structedgenode*next;}Vertex;typedefstruct//结点{intdata;//结点的入度Vertex*link;}Adjlist;Typedefstruct{Adjlistvertices[MAXVEX];//邻接表表中结点数组定义intvexnum,edgenum;//vexnum表示顶点数，edgenum表示边数}ALGraph;定义各个结点：typedefstructvexnodeadjlist[MAXVEX];建立邻接表例如一个有向图的结构为：V1V2V3V4V6V5V6其邻接表的形式如下：第一列的数为各顶点的原始度数。（2）主要算法基本思想。输出拓扑序列：先输出入度为0的顶点，再改变其他顶点的入度；循环以上步骤。具体实现方法：初始r为0（r为每次对全部结点搜索后度数为0的结点个数），对邻接表的各结点进行搜索，当结点的入度不为0，使r加1；当结点的入度为0，使此结点的度数减1，输出此结点的值，m加1（m为输出顶点的个数），再把此结点的各个邻接点的入度减1。接着按上面的步骤一样进行，直到r==n，即结点的入度都不为0。最后如果mn,即输出的个数少于顶点数则说明网中有环。（3)设计表示法(1)函数调用关系如图所示。021230∧∧∧∧∧34245552∧(2)函数接口说明。（1．voidLianJieBiao(adjlistg,intn,inte)/*建立顶点的链接表,先初始化各结点的度数为0，尾为空，再提示输入相关的一条边的两个顶点，要是输入的数字有误提示重新输入，把这条边的终点的结点的度数加1，再把这条边的终点的结点链结到起点上，重复操作。最后打印输出各顶点的起始度数。*/（2．voidBianLi(adjlistg,intn)/*通过已建立的链接表来遍历图，利用for()语句把每个结点的链结点打印输出，以此来遍历图，每行最后用^表示结束。*/（3.voidTuoPuPaiXv(adjlistadj,intn)/*输出拓扑排序的结果,具体实现方法：初始r为0（r为每次对全部结点搜索后度数为0的结点个数），对链接表的各结点进行搜索，当结点的入度不为0，使r加1；当结点的入度为0，使此结点的度数减1，输出此结点的值，m加1（m为输出顶点的个数），再把此结点的各个链接点的入度减1。接着按上面的步骤一样进行，直到r==n，即结点的入度都不为0。最后如果mn,即输出的个数少于顶点数则说明网中有环。*/（4．main()/*先输入结点数和边数，接着依次调用LianJieBiao(adjlistg,intn,inte)，BianLi(adjlistg,intn)，TuoPuPaiXv(adjlistadj,intn)三个函数。*/4．实现注释（1．输入的顶点数和边数应大于0，输入边的时候避免输入（1，1）之类的环。（2．输入的顶点个数最大值为30（3．为方便起见，输入的顶点用整型5．调试报告调试实验时，应逐步调用函数，先调试LianJieBiao(g,vex,edge);再调试BianLi(g,vex);接着调试TuoPuPaiXv(g,vex);最后调试整段代码，这样改错时方便点。另外，上机前的静态检查不能忽视；程序的调试过程可暂时多加一些输出语句以便及时查看一下中间运行情况，并对程序规格说明作少量调整和改动。main()LianJieBiao_create()BianLi()TuoPuPaiXv()6。算法改善为避免每次选入度为0的顶点时扫描整个存储空间，可设一个栈或队列暂存所有入度为零的顶点。在开始排序前，扫描对应的存储空间，将人度为零的顶点均入栈(队)。以后每次选人度为零的顶点时，只需做出栈(队)操作即可。1）此思想方法：该方法的每一步均是输出当前无后继(即出度为0)的顶点。对于一个DAG，按此方法输出的序列是逆拓扑次序。因此设置一个栈(或向量)T来保存输出的顶点序列，即可得到拓扑序列。若T是栈，则每当输出顶点时，只需做人栈操作，排序完成时将栈中顶点依次出栈即可得拓扑序列。若T是向量，则将输出的顶点从T[n-1]开始依次从后往前存放，即可保证T中存储的顶点是拓扑序列。算法的抽象描述为：NonSuccFirstTopSort(G){//优先输出无后继的顶点while(G中有出度为0的顶点)do{从G中选一出度为0的顶点v且输出v；从G中删去v及v的所有人边}if(输出的顶点数目|V(G)|)Error(G中存在有向环，排序失败!)；}2）算法求精在对该算法求精时，可用逆邻接表作为G的存储结构。设置一个向量outdegree[0..n-1]或在逆邻接表的顶点表结点中增加1个出度域来保存各顶点当前的出度；设置一个栈或队列来暂存所有出度为零的顶点。除了增加一个栈或向量T来保存输出的顶点序列外，该算法完全类似于NonPreFirstTopSort，具体算法【参见练习】。利用深度优先遍历对DAG拓扑排序当从某顶点v出发的DFS搜索完成时，v的所有后继必定均已被访问过(想像它们均已被删除)，此时的v相当于是无后继的顶点，因此在DFS算法返回之前输出顶点v即可得到DAG的逆拓扑序列。其中第一个输出的顶点必是无后继(出度为0)的顶点，它应是拓扑序列的最后一个顶点。若希望得到的不是逆拓扑序列，同样可增加T来保存输出的顶点。若假设T是栈，并在DFSTraverse算法的开始处将T初始化，利用DFS求拓扑序列的抽象算法可描述为：voidDFSTopSort(G，i，T){//在DisTraverse中调用此算法，i是搜索的出发点，T是栈intj；visited[i]=TRUE；//访问ifor(所有i的邻接点j)//即i，j∈E(G)if(!visited[j])DFSTopSort(G，j，T)；//以上语句完全类似于DFS算法Push(&T，i)；//从i出发的搜索已完成，输出i}只要将深度优先遍历算法DFSTraverse中对DFS的调用改为对DFSTopSort的调用，即可求得拓扑序列T。其具体算法不难从上述抽象算法求精后得到。若G是一个DAG，则用DFS遍历实现的拓扑排序与NonSuccFirstTopSort算法完全类似；但若C中存在有向环，则前者不能正常工作。7程序清单#includestdio.h#includemalloc.h#defineMAXVEX30//定义顶点的最大个数typedefstructedgenode//邻接点{intadjvex;//邻接点的序号structedgenode*next;}Vertex;typedefstruct//结点{intdata;//结点的入度Vertex*link;}Adjlist;typedefstruct{Adjlistvertices[MAXVEX];intvexnum,edgenum;//vexnum表示顶点数，edgenum表示边数}ALGraph;ALGraphLinJieBiao_creat(ALGraphg,intn,inte)//建立顶点的邻接表{inti,s,d;Vertex*p;for(i=1;i=n;i++)//创建邻接表的结点{g.vertices[i].link=NULL;//结点的尾为空g.vertices[i].data=0;//入度为0}for(i=1;i=e;i++){printf(\n第%d条边=\n\t起点序号，终点序号:,i);scanf(%d%d,&s,&d);//输入有边的2个点while(s==d||sn||dn)//s==d有环{printf(输入错误，请重新输入\n);printf(\n第%d条边=\n\t起点序号，终点序号:,i);scanf(%d%d,&s,&d);}g.vertices[d].data++;//入度加1p=(Vertex*)malloc(sizeof(Vertex));p-adjvex=d;/*把终点的顶点邻接到起点的顶点*/p-next=g.vertices[s].link;g.vertices[s].link=p;}printf(各顶点的原始度数\n);for(i=1;i=n;i++)printf(结点%d的度数为：%d\n,i,g.vertices[i].data);//输出各顶点的起始度数returng;}voidBianLi(ALGraphg,intn)//通过已建立的邻接表来遍历图{inti;Vertex*p;printf(遍历图的结果如下:\n);for(i=1;i=n;i++){printf(%d=,i);//邻接表中的一个结点p=g.vertices[i].link;//邻接表中一个结点的第一个邻接点while(p!=NULL)//一个顶点的全部邻接点{if(p-next!=NULL)printf(%d--,p-adjvex);elseprintf(%d,p-adjvex);p=p-next;//下一个邻接点}printf(^\n);//结束符号}}voidTuoPuPaiXu(ALGraphg,intn)//输出拓扑排序的结果{intm,i,k,r;Vertex*q;m=0;printf(拓扑排序结果为：\n);while(rn)//当一次遍历后全部的顶点入度为0时，退出循环{r=0;//r表示全部顶点一次遍历后，顶点的度数不为0的顶点数for(i=1;i=n;i++)if(g.vertices[i].data==0)//g.vertices[i]的入度为0时{g.vertices[i].data--;m++;//输出的个数加1if(mn)printf(%d-,i);elseprintf(%d,i);q=g.vertices[i].link;//q指向adj[i]的下一个邻接点while(q!=NULL)//一个顶点的全部邻接点的读书减1{k=q-adjvex;g.vertices[k].data--;q=q-next;}}else//当g.vertices[i]的入度不为0时，r++{r++;}}if(mn)printf(网中有环!\n);//当输出的个数小于顶点的