实验十 图的拓扑排序问题
浙江大学城市学院实验报告
课程名称 数据结构与算法 实验项目名称 实验十 图的拓扑排序问题 实验成绩 指导老师（签名 ） 日期
一. 实验目的和要求
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 *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
#include
#include"Graph3.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;i
GL[i]=NULL;
}
//建立用邻接表表示的有向无权图（即通过输入图的每条边建立图的邻接表） void CreateAdjoin(adjlist GL,int n)
{
char c1,c2,c3;
int i,j;
edgenode *p;
cin>>c1;
do{
cin>>c1>>i>>c2>>j>>c3;
p=new edgenode;
p->adjvex=j;
p->next=GL[i];
GL[i]=p;
cin>>c1;
if(c1=='}')
break;
}while(c1==',');
}
//输出用邻接表表示的有向无权图（即输出图的每条边） void PrintAdjoin(adjlist GL,int n)
{
int i,j;
edgenode *p;
cout
for(i=0;i
cout
cout
cout
for(i=0;i
p=GL[i];
while(p){
j=p->adjvex;
cout'
p=p->next;
}
}
cout
}
//拓扑排序算法
void Toposort(adjlist GL,int n)
{
int i,j,k,top,m=0; //m用来统计拓扑序列中的顶点数 edgenode *p;
//定义存储图中每个顶点入度的一位整型数组d int *d=new int[n];
//初始化数组d 中的每个元素值为0
for(i=0;i
d[i]=0;
//利用数组d 中的对应元素统计出每个元素的入度 for(i=0;i
p=GL[i];
while(p!=NULL){
j=p->adjvex;
d[j]++;
p=p->next;
} } } //初始化用于链接入度为0的元素的栈的栈顶指针top 为-1 top=-1; //建立初始化栈 for(i=0;iadjvex; //vk是vj 的一个出边邻接点 d[k]--; //vk的入度减1 if(d[k]==0){ //把入度为0的元素进栈 d[k]=top; top=k; } p=p->next; //p指向vj 邻接点表的下一个结点 } } cout