图的深度优先遍历和广度优先遍历.docx
《图的深度优先遍历和广度优先遍历.docx》由会员分享，可在线阅读，更多相关《图的深度优先遍历和广度优先遍历.docx（19页珍藏版）》请在冰点文库上搜索。
图的深度优先遍历和广度优先遍历
华北水利水电学院数据结构实验报告
2010～2011学年第一学期2008级计算机专业
班级：
107学号：
200810702姓名：
王文波
实验四图的应用
一、实验目的：
1．掌握图的存储结构及其构造方法
2．掌握图的两种遍历算法及其执行过程
二、实验内容：
以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现无向连通图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。
提示：
首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先和广度优先遍历，并输出遍历的结果。
三、实验要求：
1．各班学号为单号的同学采用邻接矩阵实现，学号为双号的同学采用邻接表实现。
2．C/C++完成算法设计和程序设计并上机调试通过。
3．撰写实验报告，提供实验结果和数据。
4．写出算法设计小结和心得。
四、程序源代码：
#include
#defineMaxVerNum50
structedgenode
{
intendver;
intinform;
edgenode*edgenext;
};
structvexnode
{
charvertex;
edgenode*edgelink;
};
structGraph
{
vexnodeadjlists[MaxVerNum];
intvexnum;
intarcnum;
};
//队列的定义及相关函数的实现
structQueueNode
{
intnData;
QueueNode*next;
};
structQueueList
{
QueueNode*front;
QueueNode*rear;
};
voidEnQueue（QueueList*Q,inte）
{
QueueNode*q=newQueueNode;
q->nData=e;
q->next=NULL;
if（Q==NULL）
return;
if（Q->rear==NULL）
Q->front=Q->rear=q;
else
{
Q->rear->next=q;
Q->rear=Q->rear->next;
}
}
voidDeQueue（QueueList*Q,int*e）
{
if（Q==NULL）
return;
if（Q->front==Q->rear）
{
*e=Q->front->nData;
Q->front=Q->rear=NULL;
}
else
{
*e=Q->front->nData;
Q->front=Q->front->next;
}
}
//创建图
voidCreatAdjList（Graph*G）
{
inti,j,k;
edgenode*p1;
edgenode*p2;
cout<<"请输入顶点数和边数:
"<cin>>G->vexnum>>G->arcnum;
cout<<"开始输入顶点表:
"<for（i=0;ivexnum;i++）
{
cin>>G->adjlists[i].vertex;
G->adjlists[i].edgelink=NULL;
}
cout<<"开始输入边表信息:
"<for（k=0;karcnum;k++）
{
cout<<"请输入边对应的顶点:
";
cin>>i>>j;
p1=newedgenode;
p1->endver=j;
p1->edgenext=G->adjlists[i].edgelink;
G->adjlists[i].edgelink=p1;
p2=newedgenode;
p2->endver=i;
p2->edgenext=G->adjlists[j].edgelink;
G->adjlists[j].edgelink=p2;
//因为是无向图，所以有两次建立边表的过程
}
}
//-------------------------------------------------------------深度优先遍历
voidDFS（Graph*G,inti,intvisit[]）
{
cout<adjlists[i].vertex<<"";
visit[i]=1;
edgenode*p=newedgenode;
p=G->adjlists[i].edgelink;
if（G->adjlists[i].edgelink&&!
visit[p->endver]）
{
DFS（G,p->endver,visit）;
}
}
voidDFStraversal（Graph*G,charc）//深度优先遍历
{
cout<<"该图的深度优先遍历结果为:
"<intvisit[MaxVerNum];
for（inti=0;ivexnum;i++）
{
visit[i]=0;//全部初始化为0，即未访问状态
}
intm;
for（i=0;ivexnum;i++）
{
if（G->adjlists[i].vertex==c）//根据字符查找序号
{
m=i;
DFS（G,i,visit）;
break;
}
}
//继续访问未被访问的结点
for（i=0;ivexnum;i++）
{
if（visit[i]==0）
DFS（G,i,visit）;
}
cout<}
//-------------------------------------------------------------广度优先遍历
voidBFS（Graph*G,intv,intvisit[]）
{
QueueList*Q=newQueueList;
Q->front=Q->rear=NULL;
EnQueue（Q,v）;
while（Q->rear!
=NULL）
{
inte=0;
DeQueue（Q,&e）;
cout<adjlists[e].vertex<<"";
visit[e]=1;
edgenode*p=newedgenode;
p=G->adjlists[e].edgelink;
if（p）
{
intm=p->endver;
if（m==0）
{
EnQueue（Q,m）;
while（visit[m]==0）
{
p=p->edgenext;
if（p==NULL）
break;
m=p->endver;
EnQueue（Q,m）;
}
}
}
}
}
voidBFStraversal（Graph*G,charc）
{
cout<<"该图的广度优先遍历结果为:
"<intvisited[MaxVerNum];
for（inti=0;ivexnum;i++）
{
visited[i]=0;
}
intm;
for（i=0;ivexnum;i++）
{
if（G->adjlists[i].vertex==c）
{
m=i;
BFS（G,i,visited）;
break;
}
}
//继续访问未被访问的结点
for（i=0;ivexnum;i++）
{
if（visited[i]==0）
BFS（G,i,visited）;
}
cout<}
voidmain（）
{
Graph*G=newGraph;
CreatAdjList（G）;
charch;
cout<<"请输入开始遍历的顶点:
";
cin>>ch;
DFStraversal（G,ch）;
BFStraversal（G,ch）;
}
五、程序运行情况（写出输入数据及运行结果）
六、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）
注：
内容一律使用宋体五号字，单倍行间距
本次试验采用的是邻接表的方式实现图的深度优先遍历和广度优先遍历。
对于深度优先遍历，主要是采用递归的方式，广度优先遍历借助队列来实现。
试验本身问题不是太大，但要注意输入的问题，什么时候用空格，什么时候用回车，这一点是需要注意的，因为一旦数据的输入有问题，结果当然也就不可能正确了。
只有正确的输入数据，建立图，才能得出正确的遍历结果。
#include"stdio.h"
#defineMaxVerNum50
structedgenode
{
intendver;
intinform;
edgenode*edgenext;
};
structvexnode
{
charvertex;
edgenode*edgelink;
};
structGraph
{
vexnodeadjlists[MaxVerNum];
intvexnum;
intarcnum;
};
//队列的定义及相关函数的实现
structQueueNode
{
intnData;
QueueNode*next;
};
structQueueList
{
QueueNode*front;
QueueNode*rear;
};
voidEnQueue（QueueList*Q,inte）
{
QueueNode*q=newQueueNode;
q->nData=e;
q->next=NULL;
if（Q==NULL）
return;
if（Q->rear==NULL）
Q->front=Q->rear=q;
else
{
Q->rear->next=q;
Q->rear=Q->rear->next;
}
}
voidDeQueue（QueueList*Q,int*e）
{
if（Q==NULL）
return;
if（Q->front==Q->rear）
{
*e=Q->front->nData;
Q->front=Q->rear=NULL;
}
else
{
*e=Q->front->nData;
Q->front=Q->front->next;
}
}
//创建图
voidCreatAdjList（Graph*G）
{
inti,j,k;
edgenode*p1;
edgenode*p2;
printf（"请输入顶点数和边数:
\n"）;
scanf（"%d%d",&G->vexnum,&G->arcnum）;
printf（"开始输入顶点表:
\n"）;
for（i=0;i<（G->vexnum）;i++）
{
fflush（stdin）;//清空缓存
scanf（"%c",&G->adjlists[i].vertex）;
getchar（）;//吸收回车字符
G->adjlists[i].edgelink=NULL;
}
printf（"开始输入边表信息:
\n"）;
for（k=0;karcnum;k++）
{
printf（"请输入边对应的顶点:
\n"）;
scanf（"%d%d",&i,&j）;
p1=newedgenode;
p1->endver=j;
p1->edgenext=G->adjlists[i].edgelink;
G->adjlists[i].edgelink=p1;
p2=newedgenode;
p2->endver=i;
p2->edgenext=G->adjlists[j].edgelink;
G->adjlists[j].edgelink=p2;
//因为是无向图，所以有两次建立边表的过程
}
}
//-------------------------------------------------------------深度优先遍历
voidDFS（Graph*G,inti,intvisit[]）
{
printf（"%c",G->adjlists[i].vertex）;
visit[i]=1;
edgenode*p=newedgenode;
p=G->adjlists[i].edgelink;
if（G->adjlists[i].edgelink&&!
visit[p->endver]）
{
DFS（G,p->endver,visit）;
}
}
voidDFStraversal（Graph*G,charc）//深度优先遍历
{
printf（"该图的深度优先遍历结果为:
"）;
intvisit[MaxVerNum];
for（inti=0;ivexnum;i++）
{
visit[i]=0;//全部初始化为0，即未访问状态
}
intm;
for（i=0;ivexnum;i++）
{
if（G->adjlists[i].vertex==c）//根据字符查找序号
{
m=i;
DFS（G,i,visit）;
break;
}
}
//继续访问未被访问的结点
for（i=0;ivexnum;i++）
{
if（visit[i]==0）
DFS（G,i,visit）;
}
printf（"\n"）;
}
//-------------------------------------------------------------广度优先遍历
voidBFS（Graph*G,intv,intvisit[]）
{
QueueList*Q=newQueueList;
Q->front=Q->rear=NULL;
EnQueue（Q,v）;
while（Q->rear!
=NULL）
{
inte=0;
DeQueue（Q,&e）;
printf（"%c",G->adjlists[e].vertex）;
visit[e]=1;
edgenode*p=newedgenode;
p=G->adjlists[e].edgelink;
if（p）
{
intm=p->endver;
if（m==0）
{
EnQueue（Q,m）;
while（visit[m]==0）
{
p=p->edgenext;
if（p==NULL）
break;
m=p->endver;
EnQueue（Q,m）;
}
}
}
}
}
voidBFStraversal（Graph*G,charc）
{
printf（"该图的广度优先遍历结果为:
"）;
intvisited[MaxVerNum];
for（inti=0;ivexnum;i++）
{
visited[i]=0;
}
intm;
for（i=0;ivexnum;i++）
{
if（G->adjlists[i].vertex==c）
{
m=i;
BFS（G,i,visited）;
break;
}
}
//继续访问未被访问的结点
for（i=0;ivexnum;i++）
{
if（visited[i]==0）
BFS（G,i,visited）;
}
printf（""）;
}
voidDispAdjList（Graph*G）
{
inti,z;
edgenode*p;
printf（"图的邻接表表示如下:
\n"）;
for（i=0;ivexnum;i++）
{
printf（"[%d,%3c]=>",i,G->adjlists[i].vertex）;
p=G->adjlists[i].edgelink;
while（p!
=NULL）
{
z=p->endver;
printf（"%c->",G->adjlists[z].vertex）;
p=p->edgenext;
}
printf（"∧\n"）;
}
}
voidmain（）
{
Graph*G=newGraph;
CreatAdjList（G）;
DispAdjList（G）;
charch;
printf（"请输入开始遍历的顶点:
"）;
getchar（）;
scanf（"%c",&ch）;
DFStraversal（G,ch）;
BFStraversal（G,ch）;
}
升级会员 