欢迎来到天天文库
浏览记录
ID:14051129
大小:62.00 KB
页数:6页
时间:2018-07-25
《图的深度优先遍历和广度优先遍历》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、华北水利水电学院数据结构实验报告2010~2011学年第一学期2008级计算机专业班级:107学号:200810702姓名:王文波实验四图的应用一、实验目的:1.掌握图的存储结构及其构造方法2.掌握图的两种遍历算法及其执行过程二、实验内容:以邻接矩阵或邻接表为存储结构,以用户指定的顶点为起始点,实现无向连通图的深度优先及广度优先搜索遍历,并输出遍历的结点序列。提示:首先,根据用户输入的顶点总数和边数,构造无向图,然后以用户输入的顶点为起始点,进行深度优先和广度优先遍历,并输出遍历的结果。三、实验要求:
2、1.各班学号为单号的同学采用邻接矩阵实现,学号为双号的同学采用邻接表实现。2.C/C++完成算法设计和程序设计并上机调试通过。3.撰写实验报告,提供实验结果和数据。4.写出算法设计小结和心得。四、程序源代码:#include#defineMaxVerNum50structedgenode{intendver;intinform;edgenode*edgenext;};structvexnode{charvertex;edgenode*edgelink;};structGraph
3、{vexnodeadjlists[MaxVerNum];intvexnum;intarcnum;};//队列的定义及相关函数的实现structQueueNode第6页共6页{intnData;QueueNode*next;};structQueueList{QueueNode*front;QueueNode*rear;};voidEnQueue(QueueList*Q,inte){QueueNode*q=newQueueNode;q->nData=e;q->next=NULL;if(Q==NULL)r
4、eturn;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;第6页共6页cout<<"请输入顶点数和边数:"<>G->vexnum>>G->arcnum;cout<<"开始输入顶点表:"<vexnum;i++){cin>>G->adjlists[i].vertex;G->adjlists[i].edgelink=NULL;}cout<<"开始输入边表信息:"<6、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;//因为是无向图,所以有两次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]){DFS8、(G,p->endver,visit);}}voidDFStraversal(Graph*G,charc)//深度优先遍历{cout<<"该图的深度优先遍历结果为:"<vexnum;i++){visit[i]=0;//全部初始化为0,即未访问状态}第6页共6页intm;for(i=0;ivexnum;i++){if(G->adjlists[i].vertex==c
6、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;//因为是无向图,所以有两次
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
8、(G,p->endver,visit);}}voidDFStraversal(Graph*G,charc)//深度优先遍历{cout<<"该图的深度优先遍历结果为:"<vexnum;i++){visit[i]=0;//全部初始化为0,即未访问状态}第6页共6页intm;for(i=0;ivexnum;i++){if(G->adjlists[i].vertex==c
此文档下载收益归作者所有