实验十 图的拓扑排序问题.docVIP

浙江大学城市学院实验报告 课程名称 数据结构与算法 实验项目名称 实验十 图的拓扑排序问题 实验成绩 指导老师（签名 ） 日期 实验目的和要求 掌握拓扑排序概念。 理解并能实现拓扑排序算法（采用邻接表表示图）。 二. 实验内容 编写用邻接表表示有向无权图时图的基本操作的实现函数，主要包括：①初始化用邻接表表示的有向无权图 void InitAdjoin(adjlist G); ②建立用邻接表表示的有向无权图 void CreateAdjoin (adjlist G, int n) （即通过输入图的每条边建立图的邻接表）; ③输出用邻接表表示的有向无权图void PrintAdjoin (adjlist G, int n) （即输出图的每条边）。把邻接表的结构定义以及这些基本操作实现函数存放在头文件Graph3.h中。 编写拓扑排序算法 void Toposort( adjlist G, int n) （输入为图的邻接表，输出为相应的拓扑序列）。 编写测试程序（即主函数），首先建立并输出有向无权图，然后进行拓扑排序。 要求： 把拓扑排序函数Toposort以及主函数存放在文件test10.cpp中。 填写实验报告，实验报告文件取名为report10.doc。 上传实验报告文件report10.doc与源程序文件test10.cpp及Graph3.h到Ftp服务器上自己的文件夹下。 提示： 邻接表边结点结构定义: typedef struct Node{ int adjvex; //邻接点 struct Node *next; //指向下一个结点的指针 } EdgeNode; 邻接表定义: typedef EdgeNode *AdjList[MAXVEXNUM]; 测试数据如下： 三. 函数的功能说明及算法思路 函数：void InitAdjoin(adjlist GL) 功能：初始化用邻接表表示的有向无权图 函数：void CreateAdjoin(adjlist GL,int n) 功能：建立用邻接表表示的有向无权图（即通过输入图的每条边建立图的邻接表） 函数：void PrintAdjoin(adjlist GL,int n) 功能：输出用邻接表表示的有向无权图（即输出图的每条边） 函数：void Toposort(adjlist GL,int n) 功能：拓扑排序 思路： 1）输入AOV网，n为顶点个数； 2）在AOV网中选一个没有直接前驱（即入度为0）的顶点，并输出之； 3）从图中删除该顶点，同时删除所有它发出的有向边（出边）； 4）重复以上2）、3）步，直到： ①全部顶点均已输出，则拓扑序列形成； ②或图中还有为输出顶点，但它们都有直接前驱，则输出“网中存在回路”。 四. 实验结果与分析 五. 心得体会 【附录----源程序】 test10.cpp #includeiostream.h #includeGraph3.h void main() { adjlist GL; int D[MaxVertexNum]; int i,n=6; InitAdjoin(GL); CreateAdjoin(GL,n); PrintAdjoin(GL,n); Toposort(GL,n); } Graph3.h const int MaxVertexNum=10; typedef struct Node{ int adjvex; struct Node *next; }edgenode; typedef edgenode *adjlist[MaxVertexNum]; //初始化用邻接表表示的有向无权图 void InitAdjoin(adjlist GL) { for(int i=0;iMaxVertexNum;i++) GL[i]=NULL; } //建立用邻接表表示的有向无权图（即通过输入图的每条边建立图的邻接表） void CreateAdjoin(adjlist GL,int n) { char c1,c2,c3; int i,j; edgenode *p; cinc1; do{ cinc1ic2jc3; p=new edgenode; p-adjvex=j; p-next=GL[i]; GL[i]=p; cinc1; i