拓扑排序实验报告

实验题目：图的应用实验目的：（1）熟练掌握图的基本存储方法；（2）熟练掌握图的深度优先和广度优先搜索方法；（3）掌握AOV网和拓扑排序算法；（4）掌握AOE网和关键路径。实验内容：拓扑排序。任意给定一个有向图，设计一个算法，对它进行拓扑排序。拓扑排序算法思想：a.在有向图中任选一个没有前趋的顶点输出；b.从图中删除该顶点和所有以它为尾的弧；c.重复上述a、b，直到全部顶点都已输出，此时，顶点输出序列即为一个拓朴有序序列；或者直到图中没有无前趋的顶点为止，此情形表明有向图中存在环。设计分析：为实现对无权值有向图进行拓扑排序，输出拓扑序列，先考虑如何存储这个有向图。拓扑排序的过程中要求找到入度为0的顶点，所以要采用邻接表来存储有向图，而要得到邻接表，则先要定义有向图的邻接矩阵结构，再把邻接矩阵转化成邻接表。在具体实现拓扑排序的函数中，根据规则，当某个顶点的入度为0（没有前驱顶点）时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1，为了避免重复检测入度为0的顶点，设立一个栈St，以存放入度为0的顶点。源程序代码：#includestdio.h#includestdlib.h#defineMAXV10//最大顶点个数typedefstruct{intedges[MAXV][MAXV];//邻接矩阵的边数组intn;//顶点数}MGraph;typedefstructANode{intadjvex;//该弧的终点位置structANode*nextarc;//指向下一条弧的指针}ArcNode;typedefstruct{intno;//顶点信息intcount;//顶点入度ArcNode*firstarc;//指向第一条弧}VNode,AdjList[MAXV];typedefstruct{AdjListadjlist;//邻接表intn;//图的顶点数}ALGraph;voidMatTolist(MGraphg,ALGraph*&G){inti,j,n=g.n;ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;in;i++)G-adjlist[i].firstarc=NULL;for(i=0;in;i++)for(j=n-1;j=0;j--)if(g.edges[i][j]!=0){p=(ArcNode*)malloc(sizeof(ArcNode));p-adjvex=j;p-nextarc=G-adjlist[i].firstarc;G-adjlist[i].firstarc=p;}G-n=n;}voidTopSort(ALGraph*G){inti,j,flag=0,a[MAXV];intSt[MAXV],top=-1;//栈St的指针为topArcNode*p;for(i=0;iG-n;i++)//入度置初值为0G-adjlist[i].count=0;for(i=0;iG-n;i++)//求所有顶点的入度{p=G-adjlist[i].firstarc;while(p!=NULL){G-adjlist[p-adjvex].count++;p=p-nextarc;}}for(i=0;iG-n;i++)if(G-adjlist[i].count==0)//入度为0的顶点进栈{top++;St[top]=i;}while(top-1)//栈不为空时循环{i=St[top];top--;//出栈a[flag++]=i;//输出顶点p=G-adjlist[i].firstarc;//找第一个相邻顶点while(p!=NULL){j=p-adjvex;G-adjlist[j].count--;if(G-adjlist[j].count==0){top++;St[top]=j;//入度为0的相邻顶点进栈}p=p-nextarc;//找下一个相邻顶点}}if(flagG-n)printf(该图存在回路，不存在拓扑序列!\n);else{printf(该图的一个拓扑序列为:);for(i=0;iflag;i++)printf(%d,a[i]);printf(\n);}}voidmain(){inti,j;MGraphg;ALGraph*G;G=(ALGraph*)malloc(sizeof(ALGraph));printf(请输入图的顶点数:);scanf(%d,&g.n);printf(请输入图的邻接矩阵:\n);for(i=0;ig.n;i++)for(j=0;jg.n;j++)scanf(%d,&g.edges[i][j]);MatTolist(g,G);TopSort(G);}测试用例：对图7-1所示的有向图进行拓扑排序的测试结果如下：图7-1图7-2程序执行界面，提示输入图的顶点数，输入之后又提示输入其邻接矩阵，对图7-1所示的有向图的邻接矩阵输入如图7-2所示。图7-3由于进栈出战的顶点顺序已由程序代码本身决定了，所以最终结果只能输出该有向图的一个拓扑序列，如图7-3所示。对图7-4所示的有向图进行拓扑排序，由于图中存在回路，则无法得到拓扑序列，如图7-5所示。014253图7-4图7-5实验总结：本次试验通过对有向图进行拓扑排序，我了解了有向图的邻接矩阵和邻接表的存储结构以及它们之间的相互转化，更重要的的是学会了对有向图的拓扑排序算法，其中也将之前学过的栈结合起来，巧妙的找到了一个拓扑序列，可不足的是，该算法只能找到这一条拓扑序列，但是我相信通过完成了这次试验后我会改进算法而能将图的所有的拓扑序列找出来。0123