图的深度优先遍历和广度优先遍历

《图的深度优先遍历和广度优先遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、华北水利水电学院数据结构实验报告2010～2011学年第一学期2008级计算机专业班级：107学号：200810702姓名：王文波实验四图的应用一、实验目的：1．掌握图的存储结构及其构造方法2．掌握图的两种遍历算法及其执行过程二、实验内容：以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现无向连通图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。提示：首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先和广度优先遍历，并输出遍历的结果。三、实验要求：1．各班学号为单号的同学采用邻接矩阵实现，学号为双号的同

2、学采用邻接表实现。2．C/C++完成算法设计和程序设计并上机调试通过。3．撰写实验报告，提供实验结果和数据。4．写出算法设计小结和心得。四、程序源代码：#include#defineMaxVerNum50structedgenode{intendver;intinform;edgenode*edgenext;};structvexnode{charvertex;edgenode*edgelink;};structGraph{vexnodeadjlists[MaxVerNum];intvexnum;intarcnum;};//队列的定

3、义及相关函数的实现structQueueNode第13页共13页{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->ne

4、xt;}}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;第13页共13页cout<<"请输入顶点数和边数:"<>G->vexnum>>

5、G->arcnum;cout<<"开始输入顶点表:"<vexnum;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].e

6、dgelink=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

7、=newedgenode;p=G->adjlists[i].edgelink;if(G->adjlists[i].edgelink&&!visit[p->endver]){DFS(G,p->endver,visit);}}voidDFStraversal(Graph*G,charc)//深度优先遍历{cout<<"该图的深度优先遍历结果为:"<vexnum;i++){visit[i]=0;//全部初始化为0，即未访问状态}第13页共13页intm;for(i=0;i

8、vexnum;i++){if(G->adjlists[i].ver