数据结构图的遍历实验报告

实验报告课程名：数据结构（C语言版）实验名：图的遍历姓名：班级：学号：时间：2014.11.15一实验目的与要求1.掌握图的遍历的方法2.利用C语言实现图的遍历二实验内容•将一个图存储起来•对该图分别进行先深和先广遍历三实验结果与分析程序：#includestdlib.h#includestdio.h#defineINFINITY32767#defineMAX_VEX20//最大顶点个数#defineQUEUE_SIZE(MAX_VEX+1)//队列长度//usingnamespacestd;bool*visited;//访问标志数组,避免同一顶点多次访问/****图的邻接矩阵存储结构******/typedefstruct{char*vexs;//顶点向量intarcs[MAX_VEX][MAX_VEX];//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数}Graph;/*********队列类************/classQueue{public:voidInitQueue(){base=(int*)malloc(QUEUE_SIZE*sizeof(int));front=rear=0;}voidEnQueue(inte){base[rear]=e;rear=(rear+1)%QUEUE_SIZE;}voidDeQueue(int&e){e=base[front];front=(front+1)%QUEUE_SIZE;}public:int*base;intfront;intrear;};/*图G中查找元素c的位置*/intLocate(GraphG,charc){for(inti=0;iG.vexnum;i++)if(G.vexs[i]==c)returni;return-1;}/*创建无向网*/voidCreateUDN(Graph&G){inti,j,w,s1,s2;chara,b,temp;printf(输入顶点数和弧数:);scanf(%d%d,&G.vexnum,&G.arcnum);temp=getchar();//接收回车G.vexs=(char*)malloc(G.vexnum*sizeof(char));//分配顶点数目printf(输入%d个顶点.\n,G.vexnum);for(i=0;iG.vexnum;i++){//初始化顶点printf(输入顶点%d:,i);scanf(%c,&G.vexs[i]);temp=getchar();//接收回车}for(i=0;iG.vexnum;i++)//初始化邻接矩阵for(j=0;jG.vexnum;j++)G.arcs[i][j]=INFINITY;printf(输入%d条弧.\n,G.arcnum);for(i=0;iG.arcnum;i++){//初始化弧printf(输入弧%d:,i);scanf(%c%c%d,&a,&b,&w);//输入一条边依附的顶点和权值temp=getchar();//接收回车s1=Locate(G,a);s2=Locate(G,b);G.arcs[s1][s2]=G.arcs[s2][s1]=w;}}/*****图G中顶点k的第一个邻接顶点***********/intFirstVex(GraphG,intk){if(k=0&&kG.vexnum){//k合理for(inti=0;iG.vexnum;i++)if(G.arcs[k][i]!=INFINITY)returni;}return-1;}/************图G中顶点i的第j个邻接顶点的下一个邻接顶点**********/intNextVex(GraphG,inti,intj){if(i=0&&iG.vexnum&&j=0&&jG.vexnum){//i,j合理for(intk=j+1;kG.vexnum;k++)if(G.arcs[i][k]!=INFINITY)returnk;}return-1;}/*************深度优先遍历************/voidDFS(GraphG,intk){inti;if(k==-1){//第一次执行DFS时,k为-1for(i=0;iG.vexnum;i++)if(!visited[i])DFS(G,i);//对尚未访问的顶点调用DFS}else{visited[k]=true;printf(%c,G.vexs[k]);//访问第k个顶点for(i=FirstVex(G,k);i=0;i=NextVex(G,k,i))if(!visited[i])DFS(G,i);//对k的尚未访问的邻接顶点i递归调用DFS}}/****************广度优先遍历***************/voidBFS(GraphG){intk;QueueQ;//辅助队列QQ.InitQueue();for(inti=0;iG.vexnum;i++)if(!visited[i]){//i尚未访问visited[i]=true;printf(%c,G.vexs[i]);Q.EnQueue(i);//i入列while(Q.front!=Q.rear){Q.DeQueue(k);//队头元素出列并置为kfor(intw=FirstVex(G,k);w=0;w=NextVex(G,k,w))if(!visited[w]){//w为k的尚未访问的邻接顶点visited[w]=true;printf(%c,G.vexs[w]);Q.EnQueue(w);}}}}/***********主函数***************/voidmain(){inti;GraphG;CreateUDN(G);visited=(bool*)malloc(G.vexnum*sizeof(bool));printf(\n广度优先遍历:);for(i=0;iG.vexnum;i++)visited[i]=false;DFS(G,-1);printf(\n深度优先遍历:);for(i=0;iG.vexnum;i++)visited[i]=false;BFS(G);}图1.图的遍历程序运行结果