图的基本操作 实验报告

《图的基本操作 实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验五图的基本操作一、实验目的1、使学生可以巩固所学的有关图的基本知识。2、熟练掌握图的存储结构。3、熟练掌握图的两种遍历算法。二、实验内容[问题描述]　　对给定图，实现图的深度优先遍历和广度优先遍历。[基本要求]　　　以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。【测试数据】　　由学生依据软件工程的测试技术自己确定。三、实验前的准备工作1、掌握图的相关概念。2、掌握图的逻辑结构和存储结构。3、掌握图的两种遍历算法的实现。四、实验报告要求1、实验报

2、告要按照实验报告格式规范书写。2、实验上要写出多批测试数据的运行结果。3、结合运行结果，对程序进行分析。五、算法设计1、程序所需头文件已经预处理宏定义和结构体定义如下#include#defineMaxVerNum100structedgenode{intendver;intinform;edgenode*edgenext;};structvexnode{charvertex;edgenode*edgelink;};structGraph{vexnodeadjlists[MaxVerNum];i

3、ntvexnum;intarcnum;};2、创建无向图voidCreatAdjList(Graph*G){inti,j,k;edgenode*p1;edgenode*p2;cout<<"请输入顶点数和边数:"<>G->vexnum>>G->arcnum;cout<<"开始输入顶点表:"<vexnum;i++){cin>>G->adjlists[i].vertex;G->adjlists[i].edgelink=NULL;}cout<<"开始输入边表信息:"<<

4、endl;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;//因为是无向图，所以有

5、两次建立边表的过程}}1、深度优先遍历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<<

6、"该图的深度优先遍历结果为:"<vexnum;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);

7、}cout<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->

8、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<<"该图的广度优先遍历结果为:"<