拓扑排序实验报告.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 拓扑排序是图论中的一个重要概念，主要用于有向无环图（DAG，Directed Acyclic Graph）。在这个实验中，目标是实现拓扑排序算法，它主要用于解决任务调度、依赖关系排序等问题。拓扑排序能够按照一定的顺序排列图中的顶点，使得对于任何一条有向边 (u, v)，顶点 u 总是在顶点 v 之前出现。 实验的目的分为四部分： 1. 掌握图的基本存储方法，包括邻接矩阵和邻接表。 2. 熟练运用深度优先搜索（DFS）和广度优先搜索（BFS）。 3. 学习AOV（Activity On Vertex，活动在顶点）网络，以及拓扑排序算法。 4. 了解AOE（Activity On Edge，活动在边）网络和关键路径。 在实现拓扑排序的过程中，首先需要选择合适的图数据结构。由于需要频繁查找入度为0的顶点，邻接表比邻接矩阵更适合。邻接表由一个数组和链表组成，数组的每个元素代表一个顶点，链表存储与其相连的所有顶点。 在拓扑排序算法中，首先初始化所有顶点的入度为0，然后遍历邻接表计算每个顶点的入度。接着，将入度为0的顶点放入栈中。每次从栈中弹出一个顶点并输出，同时更新其相邻顶点的入度（减1）。如果在遍历过程中发现一个入度为0的顶点，但栈已空，这说明图中可能存在环，因此拓扑排序无法完成。如果所有顶点都被输出，那么得到的序列就是一个有效的拓扑排序。 在提供的源程序代码中，`MatTolist` 函数将邻接矩阵转换为邻接表，方便后续的拓扑排序。`TopSort` 函数实现了拓扑排序的具体逻辑，包括初始化顶点入度、计算所有顶点的入度、将入度为0的顶点入栈，并在栈非空时进行顶点输出及入度更新。 总结来说，拓扑排序实验报告涵盖了图论的基本概念，包括图的存储方式、搜索方法以及特定的排序算法。通过这个实验，学生可以深入理解有向图的性质，并能应用到实际问题中解决依赖关系的排序。