实验十 图的拓扑排序问题

浙江大学城市学院实验报告课程名称数据结构与算法实验项目名称实验十图的拓扑排序问题学生姓名专业班级学号实验成绩指导老师（签名）日期实验目的和要求掌握拓扑排序概念。理解并能实现拓扑排序算法（采用邻接表表示图）。二.实验内容编写用邻接表表示有向无权图时图的基本操作的实现函数，主要包括：①初始化用邻接表表示的有向无权图voidInitAdjoin(adjlistG);②建立用邻接表表示的有向无权图voidCreateAdjoin(adjlistG,intn)（即通过输入图的每条边建立图的邻接表）;③输出用邻接表表示的有向无权图voidPrintAdjoin(adjlistG,intn)（即输出图的每条边）。把邻接表的结构定义以及这些基本操作实现函数存放在头文件Graph3.h中。编写拓扑排序算法voidToposort(adjlistG,intn)（输入为图的邻接表，输出为相应的拓扑序列）。编写测试程序（即主函数），首先建立并输出有向无权图，然后进行拓扑排序。要求：把拓扑排序函数Toposort以及主函数存放在文件test10.cpp中。填写实验报告，实验报告文件取名为report10.doc。上传实验报告文件report10.doc与源程序文件test10.cpp及Graph3.h到Ftp服务器上自己的文件夹下。提示：邻接表边结点结构定义:typedefstructNode{intadjvex;//邻接点structNode*next;//指向下一个结点的指针}EdgeNode;邻接表定义:typedefEdgeNode*AdjList[MAXVEXNUM];测试数据如下：2231540三.函数的功能说明及算法思路包括每个函数的功能说明，及一些重要函数的算法实现思路voidInitAdjoin(adjlistG)初始化用邻接表表示的有向无权图voidCreateAdjoin(adjlistG,intn)通过输入图的每条边建立图的邻接表voidPrintAdjoin(adjlistG,intn)输出图的每条边voidToposort(adjlistG,intn)输入为图的邻接表，输出为相应的拓扑序列四.实验结果与分析五.心得体会记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。【附录源程序】Test10.cpp#include<stdlib.h>#include<iostream.h>typedefstructNode{intadjvex;//邻接点structNode*next;//指向下一个结点的指针}EdgeNode;constintMAXVEXNUM=10;typedefEdgeNode*adjlist[MAXVEXNUM];#include"Graph3.h"voidmain(){ intn; cout<<"输入图的顶点个数:"; cin>>n; adjlistG; InitAdjoin(G); CreateAdjoin(G,n); PrintAdjoin(G,n); cout<<"拓扑排序"<<endl; Toposort(G,n);}Graph3.hvoidToposort(adjlistG,intn){ inti,j,k,top,m=0; EdgeNode*p; int*d=newint[n]; for(i=0;i<n;i++) d[i]=0; for(i=0;i<n;i++){ p=G[i]; while(p){ d[p->adjvex]++; p=p->next; } } top=-1; for(i=0;i<n;i++) if(d[i]==0){ d[i]=top; top=i; } while(top!=-1){ j=top; top=d[top]; cout<<j<<','; m++; p=G[j]; while(p!=NULL){ k=p->adjvex; d[k]--; if(d[k]==0){ d[k]=top; top=k; } p=p->next; } } cout<<endl; if(m<n) cout<<"Thenetworkhasacycle!"<<endl; delete[]d;}voidInitAdjoin(adjlistG){ for(inti=0;i<MAXVEXNUM;i++) G[i]=NULL;}voidCreateAdjoin(adjlistG,intn){ charc1,c2,c3; intv1,v2; EdgeNode*p; cout<<"输入边及关系:"<<endl; cin>>c1; do{ cin>>c1>>v1>>c2>>v2>>c3; p=newEdgeNode; p->adjvex=v2; p->next=G[v1]; G[v1]=p; cin>>c1; }while(c1!='}');}voidPrintAdjoin(adjlistG,intn){ inti; EdgeNode*p; cout<<"V={"; for(i=0;i<n;i++) cout<<i<<","; cout<<"}"<<endl; cout<<"E={"; for(i