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

文档介绍：华北水利水电学院数据结构实验报告2010~2011学年第一学期2008级计算机专业班级:107学号:200810702姓名:文波实验四图的应用实验目的::以邻接矩阵或邻接表为存储结构,以用户指定的顶点为起始点,实现无向连通图的深度优先及广度优先搜索遍历,并输出遍历的结点序列。提示:首先,根据用户输入的顶点总数和边数,构造无向图,然后以用户输入的顶点为起始点,进行深度优先和广度优先遍历,并输出遍历的结果。实验要求:各班学号为单号的同学采用邻接矩阵实现,学号为双号的同学采用邻接表实现。C/C++完成算法设计和程序设计并上机调试通过。撰写实验报告,提供实验结果和数据。写出算法设计小结和心得。程序源代码:#include<>#defineMaxVerNum50structedgenode{ intendver; intinform; edgenode*edgenext;};structvexnode{ charvertex; edgenode*edgelink;};structGraph{ vexnodeadjlists[MaxVerNum]; intvexnum; um;};//队列的定义及相关函数的实现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<<"请输入顶点数和边数:"<<endl; cin>>G->vexnum>>G->um; cout<<"开始输入顶点表:"<<endl; for(i=0;i<G->vexnum;i++) { cin>>G->adjlists[i].vertex; G->adjlists[i].edgelink=NULL; } cout<<"开始输入边表信息:"<<endl; for(k=0;k<G->um;k++) { cout<<"请输入边<Vi,Vj>对应的顶点:"; 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<<G->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<<"该图的深度优先遍历结果为:"<<endl; intvisit[MaxVerNum]; for(inti=0;i<G->vexnum;i++) { visit[i]=0;//全部初始化为0,即未访问状态 } intm; for(i=0;i<G->vexnum;i++) {