数据结构实验6图的存储和遍历.docx
《数据结构实验6图的存储和遍历.docx》由会员分享，可在线阅读，更多相关《数据结构实验6图的存储和遍历.docx（13页珍藏版）》请在冰点文库上搜索。
数据结构实验6图的存储和遍历
实验6.1实现图的存储和遍历
一，实验目的
掌握图的邻接矩阵和邻接表存储以及图的邻接矩阵存储的递归遍历。
二，实验内容
6.1实现图的邻接矩阵和邻接表存储
编写一个程序，实现图的相关运算，并在此基础上设计一个主程序，完成如下功能：
（1）建立如教材图7.9所示的有向图G的邻接矩阵，并输出。
（2）由有向图G的邻接矩阵产生邻接表，并输出。
（3）再由
（2）的邻接表产生对应的邻接矩阵，并输出。
6.2实现图的遍历算法
（4）在图G的邻接矩阵存储表示基础上，输出从顶点V1开始的深度优先遍历序列（递归算法）。
（5）利用非递归算法重解任务（4）。
（6）在图G的邻接表存储表示基础上，输出从顶点V1开始的广度优先遍历序列。
三，源代码及结果截图
#include
#include
#include
#include
#include
#defineMAX_VERTEX_NUM20
typedefcharVRType;
typedefintInfoType;//存放网的权值
typedefcharVertexType;//字符串类型
typedefenum{DG,DN,AG,AN}GraphKind;//{有向图,有向网,无向图,无向网}
/*建立有向图的邻接矩阵*/
typedefstructArcCell
{
VRTypeadj;//VRType是顶点关系类型，对无权图用1或0表示是否相邻;对带权图则为权值类型
InfoType*info;//该弧相关信息的指针（可无）
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{
VertexTypevexs[MAX_VERTEX_NUM];//顶点向量
AdjMatrixarcs;//邻接矩阵
intvexnum,arcnum;;//图的当前顶点数和弧数
GraphKindkind;//图的种类标志
}MGraph;
/*顶点在顶点向量中的定位*/
intLocateVex（MGraph&M,VRTypev1）{
inti;
for（i=0;iif（v1==M.vexs[i]）returni;
return-1;
}
voidCreateGraph（MGraph&M）//建立有向图的邻接矩阵
{
inti,j,k,w;
VRTypev1,v2;
M.kind=DN;printf（"构造有向网:
\n"）;
printf（"\n输入图的顶点数和边数（以空格作为间隔）:
"）;
scanf（"%d%d",&M.vexnum,&M.arcnum）;
printf（"输入%d个顶点的值（字符）:
",M.vexnum）;
getchar（）;
for（i=0;i{
scanf（"%c",&M.vexs[i]）;
}
printf（"建立邻接矩阵:
\n"）;
for（i=0;ifor（j=0;j{
M.arcs[i][j].adj=0;
M.arcs[i][j].info=NULL;
}
printf（"请顺序输入每条弧（边）的权值、弧尾和弧头（以空格作为间隔）:
\n"）;
for（k=0;k{
cin>>w>>v1>>v2;
i=LocateVex（M,v1）;
j=LocateVex（M,v2）;
M.arcs[i][j].adj=w;
}
}
//按邻接矩阵方式输出有向图
voidPrintGraph（MGraphM）
{
inti,j;
printf（"\n输出邻接矩阵:
\n"）;
for（i=0;i{
printf（"%10c",M.vexs[i]）;
for（j=0;jprintf（"%2d",M.arcs[i][j].adj）;
printf（"\n"）;
}
}
//图的邻接表存储表示
typedefstructArcNode
{
intadjvex;//该弧所指向的顶点的位置
structArcNode*nextarc;//指向下一条弧的指针
InfoType*info;//网的权值指针）
}ArcNode;//表结点
typedefstructVNode
{
VertexTypedata;//顶点信息
ArcNode*firstarc;//第一个表结点的地址,指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];//头结点
typedefstruct
{
AdjListvertices;
intvexnum,arcnum;//图的当前顶点数和弧数
intkind;//图的种类标志
}ALGraph;
voidCreateMGtoDN（ALGraph&G,MGraph&M）{
//由有向图M的邻接矩阵产生邻接表
inti,j;
ArcNode*p;
G.kind=M.kind;
G.vexnum=M.vexnum;
G.arcnum=M.arcnum;
for（i=0;iG.vertices[i].data=M.vexs[i];
G.vertices[i].firstarc=NULL;//初始化指针
}
for（i=0;ifor（j=0;jif（M.arcs[i][j].adj）{
p=（ArcNode*）malloc（sizeof（ArcNode））;
p->adjvex=j;
p->nextarc=G.vertices[i].firstarc;
p->info=M.arcs[i][j].info;
G.vertices[i].firstarc=p;
}
}
voidCreateDNtoMG（MGraph&M,ALGraph&G）{
//由邻接表产生对应的邻接矩阵
inti,j;
ArcNode*p;
M.kind=GraphKind（G.kind）;
M.vexnum=G.vexnum;
M.arcnum=G.arcnum;
for（i=0;iM.vexs[i]=G.vertices[i].data;
for（i=0;ip=G.vertices[i].firstarc;
while（p）{
M.arcs[i][p->adjvex].adj=1;
p=p->nextarc;
}//while
for（j=0;jif（M.arcs[i][j].adj!
=1）
M.arcs[i][j].adj=0;
}//for
}
//输出邻接表
voidPrintDN（ALGraphG）{
inti;
ArcNode*p;
printf（"\n输出邻接表：
\n"）;
printf（"顶点:
\n"）;
for（i=0;iprintf（"%2c",G.vertices[i].data）;
printf（"\n弧:
\n"）;
for（i=0;ip=G.vertices[i].firstarc;
while（p）{
printf（"%c→%c（%d）\t",G.vertices[i].data,G.vertices[p->adjvex].data,p->info）;
p=p->nextarc;
}
printf（"\n"）;
}//for
}
intvisited[MAX_VERTEX_NUM];//访问标志数组（全局量）
void（*VisitFunc）（char*v）;//函数变量（全局量）
//从第v个顶点出发递归地深度优先遍历图G。
/*查找第1个邻接点*/
intFirstAdjVex（MGraph&M,intv）
{
intm;
for（m=0;mif（M.arcs[v][m].adj）
returnm;
return-1;
}
/*查找下一个邻接点*/
intNextAdjVex（MGraph&M,intv,intw）
{
intj;
for（j=w+1;jif（M.arcs[v][j].adj）
returnj;
return-1;
}
voidDFS（MGraph&M,intv）
{
intw;
printf（"%c",M.vexs[v]）;
visited[v]=1;
for（w=FirstAdjVex（M,v）;w>=0;w=NextAdjVex（M,v,w））//访问第W个顶点
if（!
visited[w]）//对v的尚未访问的邻接点w递归调用DFS
DFS（M,w）;
}
voidvisits（MGraph&M,int&v）
{
v=-1;
for（inti=0;iif（!
visited[i]）
v=i;
}
voidDFSTraverse（MGraph&M,intv）
{//对图M作深度优先遍历。
inti;
for（i=0;ivisited[i]=0;//访问标志数组初始化
while（v>=0&&v{
DFS（M,v）;
visits（M,v）;
}
}
voidBFSTraverse（MGraph&M,intv）//按广度优先非递归遍历图M
{
intqueue[MAX_VERTEX_NUM],front=0,rear=0;
inti,w,u;
for（i=0;ivisited[i]=0;
for（i=0;iif（!
visited[i]）
{
//visited[i]=1;
//printf（"%4c",M.vexs[v]）;
queue[rear]=i;
rear=（rear+1）%MAX_VERTEX_NUM;
while（front!
=rear）
{
u=queue[front];
cout<visited[u]=1;
front=（front+1）%MAX_VERTEX_NUM;
for（w=FirstAdjVex（M,u）;w>=0;w=NextAdjVex（M,u,w））
{
if（!
visited[w]）
{
visited[w]=1;
//printf（"%2c",M.vexs[w]）;
queue[rear]=w;
rear=（rear+1）%MAX_VERTEX_NUM;
}
}
}
cout<}
}
voidmain（）
{
MGraphM,N;
ALGraphG;
printf（"建立有向图的邻接矩阵：
\n"）;
CreateGraph（M）;
PrintGraph（M）;
printf（"\n由有向图M的邻接矩阵产生邻接表:
\n"）;
CreateMGtoDN（G,M）;
PrintDN（G）;
printf（"\n由邻接表产生对应的邻接矩阵:
\n"）;
CreateDNtoMG（N,G）;
PrintGraph（N）;
printf（"深度优先搜索的结果:
\n"）;
DFSTraverse（M,0）;
cout<printf（"广度优先搜索的结果:
\n"）;
BFSTraverse（M,0）;
printf（"\n"）;
}
结果截图
四，实验小结
1、邻接矩阵是表示顶点之间相互关系的矩阵，用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有关联。
2、图的遍历是按照某种搜索方法沿着图的边访问图的所有顶点，使每个顶点仅被访问一次。
对于无向图，深度优先搜索和广度优先搜索需要队列进行访问。
3、深度优先搜索遍历和广度优先搜索用邻接矩阵表示图时，时间复杂度均为O（n^2）.
升级会员 