拓扑排序实验报告

《拓扑排序实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验题目：图的应用实验目的：（1）熟练掌握图的基本存储方法；（2）熟练掌握图的深度优先和广度优先搜索方法；（3）掌握AOV网和拓扑排序算法；（4）学握AOE网和关键路径°实验内容：拓扑排序。任意给定一个有向图，设计一个算法，对它进行拓扑排序。拓扑排序算法思想：a.在有向图中任选一个没有前趋的顶点输出；b.从图中删除该顶点和所有以它为尾的弧；c・重复上述a、b,直到全部顶点都已输出，此时，顶点输出序列即为一个拓朴有序序列；或者直到图小没有无前趋的顶点为止，此情形表明有向图屮存在环。设计分析：为实现对无权值有向图进行拓扑排序

2、，输出拓扑序列，先考虑如何存储这个有向图。拓扑排序的过程中要求找到入度为0的顶点，所以要采用邻接表来存储有向图，阳耍得到邻接表，则先要定义有向图的邻接矩阵结构，再把邻接矩阵转化成邻接表。在具体实现拓扑排序的函数小，根据规则，当某个顶点的入度为0（没有前驱顶点）时,就将此顶点输出，同时将该顶点的所有后继顶点的入度减I,为了避免重复检测入度为0的顶点，设立一个栈St,以存放入度为0的顶点。源程序代码：#include#include#defineMAXV10//最大顶点个数typedef

3、struct{intedges[MAXVJ[MAXVJ;//邻接矩阵的边数组intn;〃顶点数}MGraph;typedefstructANodestructANode*nextarc;JArcNode;typedefstruct{intno;intcount;ArcNode*firstarc;}VNode,AdjList[MAXVJ;typedefstruct{AdjListadjlist;intn;}ALGraph;//指向下一条弧的指针//顶点信息//顶点入度//指向第一条弧//邻接表//图的顶点数voidMatT

4、olist(MGraphg,ALGraph*&G){inti,j,n=g.n;ArcNode*p;G=(ALGraph*)maHoc(sizcof(ALGraph));for(i=0;iadjlist[iJ.firstarc=NULL;for(i=0;i=();j-)if(g.edges[i][j]!=O){p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->nextarc=G・>adjlist[i].flrsta

5、rc;G->adjlist[i].firstarc=p;}G->n=n;voidTopSort(ALGraph*G){inti,j,flag=O,a[MAXV];//栈St的指针为top//入度置初值为0//求所有顶点的入度intSt[MAXV],top二・1;ArcNode*p;for(i=0;in;i++)G->adjlist[i].count=0;for(i=0;in;i++)p=G->adjlist[i].firstarc;while(p!=NULL){G->adjlist[p->adjvex].

6、count++;p=p->nextarc;}for(i=0;in;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){t

7、op++;Stftop]=j;//入度为()的相邻顶点进栈}p=p->nextarc;//找下一个相邻顶点if(flagn)printf(”该图存在回路,不存在拓扑序列!“);elseprintf(”该图的一个拓扑序列为:”);for(i=0;i

8、anf(”％d",&g.n);printf(”请输入图的邻接矩阵:”);for(i=();ivg.n;i++)for(j=0;j