实验十 图的拓扑排序问题.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三. 函数的功能说明及算法思路函数：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#include#includeGraph3.hvoid main()adjlist GL;int DMaxVertexNum;int i,n=6;InitAdjoin(GL);CreateAdjoin(GL,n);PrintAdjoin(GL,n);Toposort(GL,n);Graph3.hconst int MaxVertexNum=10;typedef struct Nodeint adjvex;struct Node *next;edgenode;typedef edgenode *adjlistMaxVertexNum;/初始化用邻接表表示的有向无权图void InitAdjoin(adjlist GL)for(int i=0;ic1;docinc1ic2jc3;p=new edgenode;p-adjvex=j;p-next=GLi;GLi=p;cinc1;if(c1=)break;while(c1=,);/输出用邻接表表示的有向无权图（即输出图的每条边）void PrintAdjoin(adjlist GL,int n)int i,j;edgenode *p;coutV=;for(i=0;in-1;i+)couti,;coutn-1endl;coutE=;for(i=0;iadjvex;couti,jnext;coutendl;/拓扑排序算法void Toposort(adjlist GL,int n)int i,j,k,top,m=0; /m用来统计拓扑序列中的顶点数edgenode *p;/定义存储图中每个顶点入度的一位整型数组dint *d=new intn;/初始化数组d中的每个元素值为0for(i=0;in;i+)di=0;/利用数组d中的对应元素统计出每个元素的入度for(i=0;iadjvex;dj+;p=p-next;/初始化用于链接入度为0的元素的栈的栈顶指针top为-1top=-1;/建立初始化栈for(i=0;in;i+)if(di=0)di=top;top=i;/每循环一次删除一个顶点及所有出边while(top!=-1)j=top; /j的值为一个入度为0的顶点序列top=dtop; /删除栈顶元素coutjadjvex; /vk是vj的一个出边邻接点dk-; /vk的入度减1if(dk=0) /把入度为0的元素进栈dk=top;top=k;p=p-nex