图的基础操作实验报告.doc
文本预览下载声明
实验五 图的基本操作
一、实验目的
1、使学生可以巩固所学的有关图的基本知识。
2、熟练掌握图的存储结构。
3、熟练掌握图的两种遍历算法。
二、实验内容
[问题描述]
[基本要求]
以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。
【测试数据】 由学生依据软件工程的测试技术自己确定。
1、掌握图的相关概念。
2、掌握图的逻辑结构和存储结构。
3、掌握图的两种遍历算法的实现。
四、实验报告要求
1、实验报告要按照实验报告格式规范书写。
2、实验上要写出多批测试数据的运行结果。
3、结合运行结果，对程序进行分析。
五、算法设计
程序所需头文件已经预处理宏定义#includeiostream.h
#define MaxVerNum 100
struct edgenode
{
int endver;
int inform;
edgenode* edgenext;
};
struct vexnode
{
char vertex;
edgenode* edgelink;
};
struct Graph
{
vexnode adjlists[MaxVerNum];
int vexnum;
int arcnum;
};
创建无向图
void CreatAdjList(Graph* G)
{
int i,j,k;
edgenode* p1;
edgenode* p2;
cout请输入顶点数和边数:endl;
cinG-vexnumG-arcnum;
cout开始输入顶点表:endl;
for (i=0;iG-vexnum;i++)
{
cinG-adjlists[i].vertex;
G-adjlists[i].edgelink=NULL;
}
cout开始输入边表信息:endl;
for (k=0;kG-arcnum;k++)
{
cout请输入边Vi,Vj对应的顶点:;
cinij;
p1=new edgenode;
p1-endver=j;
p1-edgenext=G-adjlists[i].edgelink;
G-adjlists[i].edgelink=p1;
p2=new edgenode;
p2-endver=i;
p2-edgenext=G-adjlists[j].edgelink;
G-adjlists[j].edgelink=p2;
//因为是无向图，所以有两次建立边表的过程
}
}
深度优先遍历
void DFS(Graph *G,int i,int visit[])
{
coutG-adjlists[i].vertex ;
visit[i]=1;
edgenode *p=new edgenode;
p=G-adjlists[i].edgelink;
if(G-adjlists[i].edgelink!visit[p-endver])
{
DFS(G,p-endver,visit);
}
}
void DFStraversal(Graph *G,char c)//深度优先遍历
{
cout该图的深度优先遍历结果为:endl;
int visit[MaxVerNum];
for(int i=0;iG-vexnum;i++)
{
visit[i]=0;//全部初始化为0，即未访问状态
}
int m;
for (i=0;iG-vexnum;i++)
{
if (G-adjlists[i].vertex==c)//根据字符查找序号
{
m=i;
DFS(G,i,visit);
break;
}
}
//继续访问未被访问的结点
for(i=0;iG-vexnum;i++)
{
if(visit[i]==0)
DFS(G,i,visit);
}
coutendl;
}
广度优先遍历
void BFS(Graph* G,int v,int visit[])
{
QueueList *Q=new QueueList;
Q-front=Q-rear=NULL;
EnQueue(Q,v);
while(Q-rear!=NULL)
{
int e=0;
DeQueue(Q,e);
coutG-adjlists[e].vertex ;
visit[e]=1;
edgenode* p=new edgenode;
p=G-adjlists[e].edgelink;
if(p)
{
int m=p-endver;
if(m==0)
{
EnQueue(
显示全部