实验五图的遍历及其应用实现

《实验五图的遍历及其应用实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验五图的遍历及其应用实现一、实验目的1.熟悉图常用的存储结构。2.掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现。3.会用图的遍历解决简单的实际问题。二、实验内容键盘上输入图的顶点和边的信息，建立图的邻接表存储结构，然后以深度优先搜索和广度优先搜索遍历该图，并输出起对应的遍历序列.试设计程序实现上述图的类型定义和基本橾作，完成上述功能。该程序包括图类型以及每一种橾作的具体的函数定义和主函数。三、实验步骤(-)、程序所需尖文件已经预处理宏定义和结构体定义如下#include#d

2、efineMaxVerNum100structedgenode{intendver;intinform;edgenode*edgenext;}；structvexnode{charvertex;edgenode*edgelink;}；structGraph{vexnodeadjlists[MaxVerNum];intvexnum;intarcnum;}；1、队列的定义及相关函数的实现structQueueNode{intnData;QueueNode*next;}；structQueueList{QueueNode

3、*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

4、==Q->rear){*e=Q->front->nData;Q->front=Q->rear=NULL;}else{*e=Q->front->nData;Q->front=Q->front->next;2、创建无向图voidCreatAdjList(Graph*G){inti,j,k;edgenode*p1:edgenode*p2;cout<<"请输入顶点数和边数:"<vexnum»G->arcnum;cout<<"开始输入顶点表:*’<

5、i++){cin»G->adjlists[i].vertex;G->adjlists[i].edgelink=NULL;}cout<<"开始输入边表信息:'’<arcnum;k++){cout<<"请输入边对应的顶点:"；cin»i»j;p1=newedgenode;p1->endver=j;p1->edgenext=G->adjlists[i].edgelink;G->adjlists[i].edgelink=p1;p2=newedgenode;p2->endv

6、er=i;p2->edgenext=G->adjlists[j].edgelink;G->adjlists[j].edgelink=p2;//因为是无向图，所以有两次建立边表的过程3、深度优先遍历voidDFS(Graph*G，inti，intvisit[]){cout«G->adjlists[i].vertex«"u;visit[i]=1:edgenode*p=newedgenode;p=G->adjlists[i].edgelink;if(G->adjlists[i].edgelink&&!visit[p->e

7、ndver]){DFS(G,p->endver,visit);}}voidDFStraversal(Graph*G,charc)//深度优先遍历{cout<<"该图的深度优先遍历结果为:"<adjlists[i].vertex==c)//根据字符査找序号m=i;DFS(G,i,visi

8、t);break;}}//继续访问未被访问的结点for(i=0;ifront=Q->rear=NULL;E