拓扑排序实验报告.doc

实验题目： 图的应用 实验目的： （1）熟练掌握图的基本存储方法； （2）熟练掌握图的深度优先和广度优先搜索方法； （3）掌握AOV网和拓扑排序算法； （4）掌握AOE网和关键路径。 实验内容： 拓扑排序。 任意给定一个有向图，设计一个算法，对它进行拓扑排序。拓扑排序算法思想：a. 在有向图中任选一个没有前趋的顶点输出；b.从图中删除该顶点和所有以它为尾的 弧；c.重复上述a、b，直到全部顶点都已输出，此时，顶点输出序列即为一个拓朴 有序序列；或者直到图中没有无前趋的顶点为止，此情形表明有向图中存在环。 设计分析： 为实现对无权值有向图进行拓扑排序，输出拓扑序列，先考虑如何存储这个有向图。拓 扑排序的过程中要求找到入度为0的顶点，所以要采用邻接表来存储有向图，而要得到邻 接表，则先要定义有向图的邻接矩阵结构，再把邻接矩阵转化成邻接表。 在具体实现拓扑排序的函数中，根据规则，当某个顶点的入度为0（没有前驱顶点）时， 就将此顶点输出，同时将该顶点的所有后继顶点的入度减1，为了避免重复检测入度为0 的顶点，设立一个栈St，以存放入度为0的顶点。 源程序代码： #include<stdio.h> #include<stdlib.h> #define MAXV 10 // 最大顶点个数 typedef struct { int edges[MAXV][MAXV]; // 邻接矩阵的边数组 int n; // 顶点数 }MGraph; typedef struct ANode { int adjvex; // 该弧的终点位置 struct ANode * nextarc; // 指向下一条弧的指针 }ArcNode; typedef struct { int no; // 顶点信息 int count; // 顶点入度 ArcNode * firstarc; // 指向第一条弧 }VNode, AdjList[MAXV]; typedef struct { AdjList adjlist; // 邻接表 int n; // 图的顶点数 }ALGraph; void MatTolist(MGraph g, ALGraph * &G) { int i, j, n=g.n; ArcNode * p; G = (ALGraph *)malloc(sizeof(ALGraph)); for (i=0; i<n; i++) G->adjlist[i].firstarc = NULL; for (i=0; i<n; 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; } void TopSort(ALGraph * G) { int i,j,flag=0,a[MAXV]; int St[MAXV], top = -1; // 栈St的指针为top ArcNode * p; for (i=0; i<G->n; i++) // 入度置初值为0 G->adjlist[i].count = 0; for (i=0; i<G->n; i++) // 求所有顶点的入度 { p=G->adjlist[i].firstarc; while (p!=NULL) { G->adjlist[p->adjvex].count++; p=p->nextarc; } } for (i=0; i<G->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 (flag<G->n) printf("该图存在回路，不存在拓扑序列!\n"); else { printf("该图的一个拓扑序列为:"); for(i=0; i<flag; i++) printf("%d