图的基本操作实验报告.docx

图的基本操作实验报告.docx

《图的基本操作实验报告.docx》由会员分享，可在线阅读，更多相关《图的基本操作实验报告.docx（16页珍藏版）》请在冰点文库上搜索。

图的基本操作实验报告

实验五图的基本操作

一、实验目的

1、使学生可以巩固所学的有关图的基本知识。

2、熟练掌握图的存储结构。

3、熟练掌握图的两种遍历算法。

二、实验内容

[问题描述]

　　对给定图，实现图的深度优先遍历和广度优先遍历。

[基本要求]

　　　以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。

以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。

【测试数据】

　　由学生依据软件工程的测试技术自己确定。

三、实验前的准备工作

1、掌握图的相关概念。

2、掌握图的逻辑结构和存储结构。

3、掌握图的两种遍历算法的实现。

四、实验报告要求

1、实验报告要按照实验报告格式规范书写。

2、实验上要写出多批测试数据的运行结果。

3、结合运行结果，对程序进行分析。

五、算法设计

1、程序所需头文件已经预处理宏定义和结构体定义如下

#include

#defineMaxVerNum100

structedgenode

{

intendver;

intinform;

edgenode*edgenext;

};

structvexnode

{

charvertex;

edgenode*edgelink;

};

structGraph

{

vexnodeadjlists[MaxVerNum];

intvexnum;

intarcnum;

};

2、创建无向图

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;

//因为是无向图，所以有两次建立边表的过程

}

}

3、深度优先遍历

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<

}

4、广度优先遍历

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<

}

六、调试与测试

测试数据，如图：

七、总结

通过做这次实验，发现自己在数据结构这门课中还有很多不足有很多知识还没掌握，所以在写程序的时候出现了很多的错误，及还有很多的知识不以灵活运用。

C++没有掌握好，所以这次做本次实验还是吃力，刚开始完全没有思路，后来经过查找资料，在自己的努力下和同学的帮助下，终于完了本次实验，此次实验发现的自己的不足，在以后的学习中，我会更加的努力。

八、源代码

#include

#defineMaxVerNum100

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

}

THANKS

致力为企业和个人提供合同协议，策划案计划书，学习课件等等

打造全网一站式需求

欢迎您的下载，资料仅供参考