数据结构实验报告-图的遍历.doc
《数据结构实验报告-图的遍历.doc》由会员分享，可在线阅读，更多相关《数据结构实验报告-图的遍历.doc（4页珍藏版）》请在冰点文库上搜索。
数据结构实验报告
实验：
图的遍历
一、实验目的：
1、理解并掌握图的逻辑结构和物理结构——邻接矩阵、邻接表
2、掌握图的构造方法
3、掌握图的邻接矩阵、邻接表存储方式下基本操作的实现算法
4、掌握图的深度优先遍历和广度优先原理
二、实验内容：
1、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接矩阵存储改图。
2、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接表存储该图
3、深度优先遍历第一步中构造的图G，输出得到的节点序列
4、广度优先遍历第一部中构造的图G，输出得到的节点序列
三、实验要求：
1、无向图中的相关信息要从终端以正确的方式输入；
2、具体的输入和输出格式不限；
3、算法要具有较好的健壮性，对错误操作要做适当处理；
4、程序算法作简短的文字注释。
四、程序实现及结果：
1、邻接矩阵：
#include
#include
#defineVERTEX_MAX30
#defineMAXSIZE20
typedefstruct
{
intarcs[VERTEX_MAX][VERTEX_MAX];
intvexnum,arcnum;
}MGraph;
voidcreat_MGraph1（MGraph*g）
{inti,j,k;
intn,m;
printf（"请输入顶点数和边数:
"）;
scanf（"%d%d",&n,&m）;
g->vexnum=n;
g->arcnum=m;
for（i=0;ifor（j=0;jg->arcs[i][j]=0;
while
（1）
{
printf（"请输入一条边的两个顶点：
\n"）;
scanf（"%d%d",&i,&j）;
if（i==-1||j==-1）
break;
elseif（i==j||i>=n||j>=n）
{
printf（"输入错误,请重新输入！
\n"）;
}
else
{
g->arcs[i][j]=1;
g->arcs[j][i]=1;
}
}
}
voidprintMG（MGraph*g）
{
inti,j;
for（i=0;ivexnum;i++）
{for（j=0;jvexnum;j++）
printf（"%d",g->arcs[i][j]）;
printf（"\n"）;
}
printf（"\n"）;
}
main（）
{
inti,j;
intfg;
MGraph*g1;
g1=（MGraph*）malloc（sizeof（MGraph））;
printf（"1:
创建无向图的邻接矩阵\n\n"）;
creat_MGraph1（g1）;
printf（"\n此图的邻接矩阵为：
\n"）;
printMG（g1）;
}
2、邻接链表:
#include
#include
#defineMAX_SIZE10
typedefstructnode{
intvertex;
structnode*next;
}node,adjlist[MAX_SIZE];
adjlistg;
intvisited[MAX_SIZE+1];
intque[MAX_SIZE+1];
voidcreat（）
{
intn,e;
inti;
intstart,end;
node*p,*q,*pp,*qq;
printf（"输入无向图的顶点数和边数:
"）;
scanf（"%d%d",&n,&e）;
for（i=1;i<=n;i++）
{
visited[i]=0;
g[i].vertex=i;
g[i].next=NULL;
}
printf（"依次输入边:
\n"）;
for（i=1;i<=e;i++）
{
scanf（"%d%d",&start,&end）;
p=（node*）malloc（sizeof（node））;
p->vertex=end;
p->next=NULL;
q=&g[start];
while（q->next）
q=q->next;
q->next=p;
p1=（node*）malloc（sizeof（node））;
p1->vertex=start;
p1->next=NULL;
q1=&g[end];
while（qq->next）
q1=q1->next;
q1->next=p1;
}
}
voidbfs（intvi）
{
intfront,rear,v;
node*p;
front=0;
rear=1;
visited[vi]=1;
que[0]=vi;
printf（"%d",vi）;
while（front!
=rear）
{
v=que[front];
p=g[v].next;
while（p）
{
if（!
visited[p->vertex]）
{
visited[p->vertex]=1;
printf（"%d",p->vertex）;
que[rear++]=p->vertex;
}
p=p->next;
}
front++;
}
}
intmain（）
{
creat（）;
bfs
（1）;
printf（"\n"）;
return0;
}
五．实验心得与体会：
（1）通过这次实验，使我基本上掌握了图的存储和遍历，让我弄清楚了如何用邻接矩阵和邻接链表对图进行存储
（2）深度优先遍历和广度优先遍历都有着各自的优点，通过程序逐步调试，可以慢慢的理解这两种遍历方法的内涵和巧妙之处。
（3）实验过程中，总体来说还算顺畅，但在编写过程中，要养成良好的编程习惯，以免出错后浪费大量的时间在查错上。
升级会员 