实验十 图的拓扑排序问题

《实验十 图的拓扑排序问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、浙江大学城市学院实验报告课程名称数据结构与算法实验项目名称实验十图的拓扑排序问题实验成绩指导老师（签名）日期一.实验目的和要求1.掌握拓扑排序概念。2.理解并能实现拓扑排序算法（采用邻接表表示图）。二.实验内容1、编写用邻接表表示有向无权图时图的基本操作的实现函数，主要包括：①初始化用邻接表表示的有向无权图voidInitAdjoin(adjlistG);②建立用邻接表表示的有向无权图voidCreateAdjoin(adjlistG,intn)（即通过输入图的每条边建立图的邻接表）;③输出用邻接表表示的有向无权图voidPrintAdjoin(adjlistG,intn)（即输出图的每条边）

2、。把邻接表的结构定义以及这些基本操作实现函数存放在头文件Graph3.h中。2、编写拓扑排序算法voidToposort(adjlistG,intn)（输入为图的邻接表，输出为相应的拓扑序列）。3、编写测试程序（即主函数），首先建立并输出有向无权图，然后进行拓扑排序。要求：把拓扑排序函数Toposort以及主函数存放在文件test10.cpp中。4、填写实验报告，实验报告文件取名为report10.doc。5、上传实验报告文件report10.doc与源程序文件test10.cpp及Graph3.h到Ftp服务器上自己的文件夹下。提示：邻接表边结点结构定义:typedefstructNode{

3、intadjvex;//邻接点structNode*next;//指向下一个结点的指针}EdgeNode;邻接表定义:typedefEdgeNode*AdjList[MAXVEXNUM];测试数据如下：5231540三.函数的功能说明及算法思路函数：voidInitAdjoin(adjlistGL)功能：初始化用邻接表表示的有向无权图函数：voidCreateAdjoin(adjlistGL,intn)功能：建立用邻接表表示的有向无权图（即通过输入图的每条边建立图的邻接表）函数：voidPrintAdjoin(adjlistGL,intn)功能：输出用邻接表表示的有向无权图（即输出图的每条边）

4、函数：voidToposort(adjlistGL,intn)功能：拓扑排序思路：1）输入AOV网，n为顶点个数；2）在AOV网中选一个没有直接前驱（即入度为0）的顶点，并输出之；3）从图中删除该顶点，同时删除所有它发出的有向边（出边）；4）重复以上2）、3）步，直到：①全部顶点均已输出，则拓扑序列形成；②或图中还有为输出顶点，但它们都有直接前驱，则输出“网中存在回路”。四.实验结果与分析五.心得体会【附录----源程序】test10.cpp5#include#include"Graph3.h"voidmain(){adjlistGL;intD[MaxVertexNum

5、];inti,n=6;InitAdjoin(GL);CreateAdjoin(GL,n);PrintAdjoin(GL,n);Toposort(GL,n);}Graph3.hconstintMaxVertexNum=10;typedefstructNode{intadjvex;structNode*next;}edgenode;typedefedgenode*adjlist[MaxVertexNum];//初始化用邻接表表示的有向无权图voidInitAdjoin(adjlistGL){for(inti=0;i

6、向无权图（即通过输入图的每条边建立图的邻接表）voidCreateAdjoin(adjlistGL,intn){charc1,c2,c3;inti,j;edgenode*p;cin>>c1;do{cin>>c1>>i>>c2>>j>>c3;p=newedgenode;p->adjvex=j;p->next=GL[i];5GL[i]=p;cin>>c1;if(c1=='}')break;}while(c1==',');}//输出用邻接表表示的有向无权图（即输出图的每条边）voidPrintAdjoin(adjlistGL,intn){inti,j;edgenode*p;cout<<"V={";f

7、or(i=0;iadjvex;cout<<'<'<'<<',';p=p->next;}}cout<<'}'<