实验10 图的拓扑排序问题,蓝礼巍
- 格式：doc
- 大小：65.33 KB
- 文档页数：6
浙江大学城市学院实验报告
课程名称数据结构与算法
实验项目名称实验十图的拓扑排序问题
学生姓名蓝礼巍专业班级学号
实验成绩指导老师（签名）日期
一.实验目的和要求
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];
测试数据如下：
三. 函数的功能说明及算法思路
包括每个函数的功能说明，及一些重要函数的算法实现思路
四. 实验结果与分析
包括运行结果截图等
五. 心得体会
记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。
【附录----源程序】
Cpp
#include<iostream.h>
#include<stdlib.h>
#include<strstrea.h>
#include<string.h>
#include<stdio.h>
typedef int VertexType;
typedef int WeightType;
const int MaxVertexNum=20;
typedef struct Node{
int adjvex; //邻接点
struct Node *next; //指向下一个结点的指针
} edgenode;
typedef edgenode *adjlist[MaxVertexNum];
#include"test10.h"
void Toposort( adjlist G, int n)//编写拓扑排序算法{
int i,j,k,top,m=0;
edgenode *p;
int *d=new int[n];
for(i=0;i<n;i++)
d[i]=0;
for(i=0;i<n;i++)
{
p=G[i];
while(p!=NULL)
{
j=p->adjvex;
d[j]++;
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<<"The network has a cycle!"<<endl;
delete []d;
}
void main()
{
char
str[100]="{(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;i<MaxVertexNum;i++)
G[i]=NULL;
}
void CreateAdjoin (adjlist G, int n,char *s)// 建立用邻接表表示的有向无权图
{
istrstream sin(s);
char c1,c2,c3;
int i,j;
edgenode *p;
sin>>c1;
do{
sin>>c1>>i>>c2>>j>>c3;
p=new edgenode;
p->adjvex=j;
p->next=G[i];
G[i]=p;
sin>>c1;
}while(c1==',');
}
void PrintAdjoin (adjlist G, int n)//输出用邻接表表示的有向无权图{
int i,j;
edgenode *p;
cout<<"V={";
for(i=0;i<n-1;i++)
cout<<i<<',';
cout<<n-1<<'}'<<endl;
cout<<"E={";
for(i=0;i<n;i++)
{
p=G[i];
while(p)
{
j=p->adjvex;
cout<<'<'<<i<<','<<j<<'>'<<',';
p=p->next;
}
}
cout<<'}'<<endl;
}。
