数据结构实验报告-图的遍历Word文档下载推荐.doc

数据结构实验报告-图的遍历Word文档下载推荐.doc

《数据结构实验报告-图的遍历Word文档下载推荐.doc》由会员分享，可在线阅读，更多相关《数据结构实验报告-图的遍历Word文档下载推荐.doc（4页珍藏版）》请在冰点文库上搜索。

#include<

stdio.h>

malloc.h>

#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;

arcnum=m;

for（i=0;

i<

n;

i++）

for（j=0;

j<

j++）

g->

arcs[i][j]=0;

while

（1）

{

printf（"

请输入一条边的两个顶点：

\n"

scanf（"

i,&

j）;

if（i==-1||j==-1）

break;

elseif（i==j||i>

=n||j>

=n）

{

printf（"

输入错误,请重新输入！

}

else

g->

arcs[i][j]=1;

g->

arcs[j][i]=1;

}

}

voidprintMG（MGraph*g）

inti,j;

for（i=0;

g->

vexnum;

i++）

{for（j=0;

printf（"

%d"

g->

arcs[i][j]）;

}

printf（"

main（）

intfg;

MGraph*g1;

g1=（MGraph*）malloc（sizeof（MGraph））;

1:

创建无向图的邻接矩阵\n\n"

creat_MGraph1（g1）;

\n此图的邻接矩阵为：

printMG（g1）;

2、邻接链表:

#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;

输入无向图的顶点数和边数:

scanf（"

e）;

for（i=1;

i<

=n;

i++）

{

visited[i]=0;

g[i].vertex=i;

g[i].next=NULL;

依次输入边:

=e;

i++）

scanf（"

start,&

end）;

p=（node*）malloc（sizeof（node））;

p->

vertex=end;

next=NULL;

q=&

g[start];

while（q->

next）

q=q->

next;

q->

next=p;

p1=（node*）malloc（sizeof（node））;

p1->

vertex=start;

q1=&

g[end];

while（qq->

q1=q1->

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（"

p->

vertex）;

que[rear++]=p->

vertex;

}

p=p->

front++;

}

intmain（）

creat（）;

bfs

（1）;

return0;

五．实验心得与体会：

（1）通过这次实验，使我基本上掌握了图的存储和遍历，让我弄清楚了如何用邻接矩阵和邻接链表对图进行存储

（2）深度优先遍历和广度优先遍历都有着各自的优点，通过程序逐步调试，可以慢慢的理解这两种遍历方法的内涵和巧妙之处。

（3）实验过程中，总体来说还算顺畅，但在编写过程中，要养成良好的编程习惯，以免出错后浪费大量的时间在查错上。