拓扑排序实验报告.doc

《拓扑排序实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

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

3、邻接矩阵的边数组intn;//顶点数}MGraph;typedefstructANode{intadjvex;//该弧的终点位置structANode*nextarc;//指向下一条弧的指针}ArcNode;typedefstruct{intno;//顶点信息intcount;//顶点入度ArcNode*firstarc;//指向第一条弧}VNode,AdjList[MAXV];typedefstruct{AdjListadjlist;//邻接表intn;//图的顶点数}ALGraph;voidMatTolist(MGraphg,ALGraph*&G

4、){inti,j,n=g.n;ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;iadjlist[i].firstarc=NULL;for(i=0;i=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;}v

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

6、list[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(fl

7、agn)printf("该图存在回路，不存在拓扑序列!");else{printf("该图的一个拓扑序列为:");for(i=0;i

8、;j++)scanf("%d",&g.edges[i][j]);MatTolist(g,G);TopSort