实验10 图的拓扑排序问题,蓝礼巍.doc

浙江大学城市学院实验报告课程名称 数据结构与算法 实验项目名称 实验十 图的拓扑排序问题 学生姓名 蓝礼巍 专业班级 学号 实验成绩 指导老师（签名 ） 日期 一. 实验目的和要求1. 掌握拓扑排序概念。2. 理解并能实现拓扑排序算法（采用邻接表表示图）。二. 实验内容1、 编写用邻接表表示有向无权图时图的基本操作的实现函数，主要包括：初始化用邻接表表示的有向无权图 void InitAdjoin(adjlist G); 建立用邻接表表示的有向无权图 void CreateAdjoin (adjlist G, int n) （即通过输入图的每条边建立图的邻接表）; 输出用邻接表表示的有向无权图void PrintAdjoin (adjlist G, int n) （即输出图的每条边）。把邻接表的结构定义以及这些基本操作实现函数存放在头文件Graph3.h中。2、 编写拓扑排序算法 void Toposort( adjlist G, int n) （输入为图的邻接表，输出为相应的拓扑序列）。 3、 编写测试程序（即主函数），首先建立并输出有向无权图，然后进行拓扑排序。要求： 把拓扑排序函数Toposort以及主函数存放在文件test10.cpp中。4、 填写实验报告，实验报告文件取名为report10.doc。5、 上传实验报告文件report10.doc与源程序文件test10.cpp及Graph3.h到Ftp服务器上自己的文件夹下。提示：邻接表边结点结构定义:typedef struct Node int adjvex; /邻接点 struct Node *next; /指向下一个结点的指针 EdgeNode;邻接表定义:typedef EdgeNode *AdjListMAXVEXNUM; 测试数据如下：231540三. 函数的功能说明及算法思路 包括每个函数的功能说明，及一些重要函数的算法实现思路四. 实验结果与分析包括运行结果截图等五. 心得体会记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。【附录-源程序】Cpp#include#include#include#include#includetypedef int VertexType;typedef int WeightType;const int MaxVertexNum=20;typedef struct Node int adjvex; /邻接点 struct Node *next; /指向下一个结点的指针 edgenode;typedef edgenode *adjlistMaxVertexNum; #includetest10.hvoid Toposort( adjlist G, int n)/编写拓扑排序算法 int i,j,k,top,m=0;edgenode *p;int *d=new intn;for(i=0;in;i+)di=0;for(i=0;iadjvex;dj+;p=p-next;top=-1;for(i=0;in;i+)if(di=0)di=top;top=i;while(top!=-1)j=top;top=dtop;coutjadjvex;dk-;if(dk=0)dk=top;top=k;p=p-next;coutendl;if(mn)coutThe network has a cycle!endl;delete d;void main()char str100=(0,2),(1,2),(1,3),(1,4),(2,3),(2,5),(3,5),(4,5);adjlist g;InitAdjoin(g);int n=6;CreateAdjoin (g, n,str);cout邻接表表示的有向无权图为：endl;PrintAdjoin (g,n);cout拓扑排序为：endl;Toposort( g,n);H/*1、编写用邻接表表示有向无权图时图的基本操作的实现函数，主要包括：初始化用邻接表表示的有向无权图 void InitAdjoin(adjlist G); 建立用邻接表表示的有向无权图 void CreateAdjoin (adjlist G, int n) （即通过输入图的每条边建立图的邻接表）; 输出用邻接表表示的有向无权图void PrintAdjoin (adjlist G, int n) （即输出图的每条边）。把邻接表的结构定义以及这些基本操作实现函数存放在头文件Graph3.h中。2、编写拓扑排序算法 void Toposort( adjlist G, int n) （输入为图的邻接表，输出为相应的拓扑序列）。 3、编写测试程序（即主函数），首先建立并输出有向无权图，然后进行拓扑排序。要求： 把拓扑排序函数Toposort以及主函数存放在文件test10.cpp中。*/void InitAdjoin(adjlist G)/初始化用邻接表表示的有向无权图for(int i=0;ic1;dosinc1ic2jc3;p=new edgenode;p-adjvex=j;p-next=Gi;Gi=p;sinc1;while(c1=,);void PrintAdjoin (adjlist G, int n)/输出用邻接表