图遍历的演示

《数据结构》课程实验报告 题目：图遍历的演示 班级： 姓名： 学号： 专业： 学院： 完成日期：需求分析问题描述：很多涉及图上操作的算法都是以图的遍历操作作为基础的。试写一个程序，演示在连通图的无向图上访问全部结点的操作。基本要求：以邻接多重表（选作内容邻接表）为存储结构，实现连通无向图的深度优先遍历和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集输入的形式和输入的范围：先输入顶点数N以及边数M，然后依次输入N个顶点，再按提示输入M条边的信息用（a-b3）类似的形式测试数据：教科书图7.33部分信息概要设计抽象数据类型图的定义：ADTGraph{数据对象V：V是具有相同特性的的数据元素的集合，成为顶点集。数据关系R:R=｛VR｝VR={<v,w>|v,wєV且P(v,w),<v,w>表示从v到w的弧，谓词P(v,w)定义了弧<v,w>的意义或信息}基本操作P：locatevex(G,mes)；初始条件：图G存在，mes和G中顶点有相同的特征。操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。createudn(&G)；初始条件：图G存在。操作结果：创建无向图。createdn(&G)；初始条件：图G存在。操作结果：创建有向图。createudg(&G)；初始条件：图G存在操作结果：创建无向网。createdg(&G)；初始条件：图G存在。操作结果：创建有向网。DFS(G,v)；初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。操作结果：深度优先搜索遍历图G，访问顶点时使用函数visit.BFS(G,v)；初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。操作结果：广度优先搜索遍历图G，访问顶点时使用函数 rear=(rear+1)%QUEUE_SIZE;//rear后移} voidDeQueue(int&e){//若队列不空，则删除对头元素，用e返回 e=base[front]; front=(front+1)%QUEUE_SIZE;} public:int*base;intfront;intrear;};查找定位函数intLocate(GraphG,charc){//图G中查找元素c的位置 for(inti=1;i<=G.vexnum;i++){if(G.vexs[i]==c) returni; } return-1;}初始化无向图函数voidCreateUDN(Graph&G){//创建无向图inti,j,w,s1,s2; chara,b,temp;cout<<"输入顶点的总数和边的总数:";cin>>G.vexnum>>G.arcnum;temp=getchar();//接收回车G.vexs=(char*)malloc(G.vexnum*sizeof(char));//分配顶点数目cout<<"输入"<<G.vexnum<<"个顶点分别为:"<<endl;for(i=1;i<=G.vexnum;i++){//初始化顶点cout<<"顶点:"<<i; cin>>&G.vexs[i]; temp=getchar(); }for(i=1;i<=G.vexnum;i++)//初始化邻接矩阵for(j=1;j<=G.vexnum;j++)G.arcs[i][j]=INFINITY;//16int类型，初始化边为无穷大cout<<"输入"<<G.arcnum<<"条边分别为:"<<endl;//读取边信息并初始化集合for(i=1;i<=G.arcnum;i++){//初始化边cout<<"边"<<i<<endl;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;}//无向}intFirstVex(GraphG,intk){//图G中顶点k的第一个邻接顶点 if(k>=1&&k<=G.vexnum){for(inti=1;i<=G.vexnum;i++)if(G.arcs[k][i]!=INFINITY) returni; }return-1;}intNextVex(GraphG,inti,intj){//图G中顶点i的第j个邻接顶点的下一个邻接顶点 if(i>=1&&i<=G.vexnum&&j>=1&&j<=G.vexnum){//i,j合理for(intk=j+1;k<=G.vexnum;k++)if(G.arcs[i][k]!=INFINITY) returnk; }return-1;}深度优先遍历及广度优先遍历函数voidDFS(GraphG,intk){//深度优先搜索inti; if(k==-1){//第一次执行DFS时,k为-1for(i=1;i<=G.vexnum;i++) if(!visited[i]) DFS(G,i); }//对尚未访问的顶点调用DFSelse{visited[k]=true;//访问第k个顶点cout<<G.vexs[k];for(i=FirstVex(G,k);i>=1;i=NextVex(G,k,i))if(!visited[i]) DFS(G,i); }}voidBFS(GraphG){//广度优先搜索intk;QueueQ;//辅助队列QQ.InitQueue();for(inti=0;i<=G.vexnum;i++)if(!visited[i]){//i尚未访问visited[i]=true; cout<<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; cout<<G.vexs[w];Q.EnQueue(w); } } } }主函数voidmain(){//主函数inti; GraphG; CreateUDN(G);//创建无向图visited=(bool*)malloc(G.vexnum*sizeof(bool));cout<<endl<<"深度优先搜索结果为:";for(i=1;i<=G.vexnum;i++){ visited[i]=false;//标志数组初始化为false DFS(G,-1);}cout<<endl<<"广度优先