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

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

1、------------------------------------------作者xxxx------------------------------------------日期xxxx图的深度优先遍历和广度优先遍历【精品文档】华北水利水电学院数据结构实验报告2010～2011学年第一学期2008级计算机专业班级：107学号：200810702姓名：王文波实验四图的应用一、实验目的：1．掌握图的存储结构及其构造方法2．掌握图的两种遍历算法及其执行过程二、实验内容：以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现无向连通图的深度优先及广度优先搜索遍历

2、，并输出遍历的结点序列。提示：首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先和广度优先遍历，并输出遍历的结果。三、实验要求：1．各班学号为单号的同学采用邻接矩阵实现，学号为双号的同学采用邻接表实现。2．C/C++完成算法设计和程序设计并上机调试通过。3．撰写实验报告，提供实验结果和数据。4．写出算法设计小结和心得。四、程序源代码：#include#defineMaxVerNum50structedgenode{intendver;intinform;edgenode*edgenext;};struc

3、tvexnode{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

4、->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;}}//创建图【精品文档】【

5、精品文档】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<<"开始输入边表信息:"<arcnum;k++){cout<<"请输入边

6、>对应的顶点:";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;//因为是无向图，所以有两次建立边表的过程}}//----------------------------------------------------------

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