数据结构实验报告图实验.docx
《数据结构实验报告图实验.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告图实验.docx（11页珍藏版）》请在冰点文库上搜索。
数据结构实验报告图实验
图实验
一，邻接矩阵的实现
1.实验目的
（1）掌握图的逻辑结构
（2）掌握图的邻接矩阵的存储结构
（3）验证图的邻接矩阵存储及其遍历操作的实现
2.实验内容
（1）建立无向图的邻接矩阵存储
（2）进行深度优先遍历
（3）进行广度优先遍历
3．设计与编码
MGraph.h
#ifndefMGraph_H
#defineMGraph_H
constintMaxSize=10;
template
classMGraph
{
public:
MGraph（DataTypea[],intn,inte）;
~MGraph（）{
}
voidDFSTraverse（intv）;
voidBFSTraverse（intv）;
private:
DataTypevertex[MaxSize];
intarc[MaxSize][MaxSize];
intvertexNum,arcNum;
};
#endif
MGraph.cpp
#include
usingnamespacestd;
#include"MGraph.h"
externintvisited[MaxSize];
template
MGraph:
:
MGraph（DataTypea[],intn,inte）
{
inti,j,k;
vertexNum=n,arcNum=e;
for（i=0;ivertex[i]=a[i];
for（i=0;ifor（j=0;jarc[i][j]=0;
for（k=0;k{
cout<<"Pleaseentertwovertexsnumberofedge:
";
cin>>i>>j;
arc[i][j]=1;
arc[j][i]=1;
}
}
template
voidMGraph:
:
DFSTraverse（intv）
{
cout<visited[v]=1;
for（intj=0;jif（arc[v][j]==1&&visited[j]==0）
DFSTraverse（j）;
}
template
voidMGraph:
:
BFSTraverse（intv）
{
intQ[MaxSize];
intfront=-1,rear=-1;
cout<visited[v]=1;
Q[++rear]=v;
while（front!
=rear）
{
v=Q[++front];
for（intj=0;jif（arc[v][j]==1&&visited[j]==0）{
cout<visited[j]=1;
Q[++rear]=j;
}
}
}
MGraph_main.cpp
#include
usingnamespacestd;
#include"MGraph.h"
externintvisited[MaxSize];
template
MGraph:
:
MGraph（DataTypea[],intn,inte）
{
inti,j,k;
vertexNum=n,arcNum=e;
for（i=0;ivertex[i]=a[i];
for（i=0;ifor（j=0;jarc[i][j]=0;
for（k=0;k{
cout<<"Pleaseentertwovertexsnumberofedge:
";
cin>>i>>j;
arc[i][j]=1;
arc[j][i]=1;
}
}
template
voidMGraph:
:
DFSTraverse（intv）
{
cout<visited[v]=1;
for（intj=0;jif（arc[v][j]==1&&visited[j]==0）
DFSTraverse（j）;
}
template
voidMGraph:
:
BFSTraverse（intv）
{
intQ[MaxSize];
intfront=-1,rear=-1;
cout<visited[v]=1;
Q[++rear]=v;
while（front!
=rear）
{
v=Q[++front];
for（intj=0;jif（arc[v][j]==1&&visited[j]==0）{
cout<visited[j]=1;
Q[++rear]=j;
}
}
}
4.运行与测试
5.总结与心得
通过该实验的代码编写与调试，熟悉了邻接矩阵在图结构中的应用，在调试过程中遇到很多的问题，在解决问题过程中也使我的写代码能力得到提升
二，邻接表的实现
1.实验目的
（1）掌握图的逻辑结构
（2）掌握图的邻接表存储结构
（3）验证图的邻接表存储及其遍历操作的实现
2.实验内容
（1）建立一个有向图的邻接表存储结构
（2）对建立的有向图进行深度优先遍历
（3）对建立的有向图进行广度优先遍历
3.设计与编码
ALGraph.h
#ifndefALGraph_H
#defineALGraph_H
constintMaxSize=10;
structArcNode
{
intadjvex;
ArcNode*next;
};
template
structVertexNode
{
DataTypevertex;
ArcNode*firstedge;
};
template
classALGraph
{
public:
ALGraph（DataTypea[],intn,inte）;
~ALGraph（）;
voidDFSTraverse（intv）;
voidBFSTraverse（intv）;
private:
VertexNodeadjlist[MaxSize];
intvertexNum,arcNum;
};
#endif
ALGraph.cpp
#include
usingnamespacestd;
#include"ALGraph.h"
externintvisited[MaxSize];
template
ALGraph:
:
ALGraph（DataTypea[],intn,inte）
{
ArcNode*s;
inti,j,k;
vertexNum=n;arcNum=e;
for（i=0;i{
adjlist[i].vertex=a[i];
adjlist[i].firstedge=NULL;
}
for（k=0;k{
cout<<"Pleaseentertheedgeoftheserialnumberoftwovertices:
";
cin>>i>>j;
s=newArcNode;s->adjvex=j;
s->next=adjlist[i].firstedge;
adjlist[i].firstedge=s;
}
}
template
ALGraph:
:
~ALGraph（）
{
ArcNode*p=NULL;
for（inti=0;i{
p=adjlist[i].firstedge;
while（p!
=NULL）
{
adjlist[i].firstedge=p->next;
deletep;
p=adjlist[i].firstedge;
}
}
}
template
voidALGraph:
:
DFSTraverse（intv）
{
ArcNode*p=NULL;intj;
cout<visited[v]=1;
p=adjlist[v].firstedge;
while（p!
=NULL）
{
j=p->adjvex;
if（visited[j]==0）DFSTraverse（j）;
p=p->next;
}
}
template
voidALGraph:
:
BFSTraverse（intv）
{
intQ[MaxSize];
intfront=-1,rear=-1;
ArcNode*p=NULL;
cout<while（front!
=rear）
{
v=Q[++front];
p=adjlist[v].firstedge;
while（p!
=NULL）
{
intj=p->adjvex;
if（visited[j]==0）{
cout<}
p=p->next;
}
}
}
ALGraph_main.cpp
#include
usingnamespacestd;
#include"ALGraph.cpp"
intvisited[MaxSize]={0};
intmain（）
{
charch[]={'A','B','C','D','E'};
inti;
ALGraphALG（ch,5,6）;
for（i=0;ivisited[i]=0;
cout<<"Depth-firsttraversesequenceis:
";
ALG.DFSTraverse（0）;
cout<for（i=0;ivisited[i]=0;
cout<<"Breadth-firsttraversesequenceis:
";
ALG.BFSTraverse（0）;
cout<return0;
}
4.运行与调试
5.总结与心得
通过该实验，掌握了图的邻接表存储结构
升级会员 