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

问题描述：若用有向网表示网页的链接网络，其中顶点表示某个网页，有向弧表示网页之间的链接关系。试设计一个网络蜘蛛系统，分别以广度优先和深度优先的策略抓取网页。需求分析：本程序要求采用利用图实现广度优先搜索。首先输入顶点的数量，然后是各顶点对应的字母，再输入各条弧（权值都置为1）。在Dos界面输出从首个顶点开始的广度优先遍历序列。测试数据 输入输入顶点数和弧数:89输入8个顶点.输入顶点0:a输入顶点1:b输入顶点2:c输入顶点3:d输入顶点4:e输入顶点5:f输入顶点6:g输入顶点7:h输入9条弧.输入弧0:ab1输入弧1:bd1输入弧2:be1输入弧3:dh1输入弧4:eh1输入弧5:ac1输入弧6:cf1输入弧7:cg1输入弧8:fg1输出广度优先遍历:abdhecfg深度优先遍历:abcdefgh二、概要设计：抽象数据类型：图的定义：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：CreateGraph(&G,V,VR)初始条件：V是图的顶点集，VR是图中弧的集合

操作结果：按V和VR的定义构造图GFirstAdjVex(G,v)初始条件：图G存在,v是G中某个顶点操作结果：返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回“空”NextAdjVex(G,v,w)初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点操作结果：返回v的（相对于w的）下一个邻接顶点，若w是v的最后一个邻接点，则返回“空”visit(G,k)初始条件：图G存在操作结果：访问图G中的第K个节点Locate(G,c)初始条件：图G存在操作结果：访问图G中的c顶点DFS(G,v)初始条件：图G存在操作结果：以图G中的第v个节点为起点深度优先访问图GBFS(G)初始条件：图G存在操作结果：广度优先访问图G

}ADTGraph算法的基本思想：（1）图的特点是没有首尾之分，所以算法的参数要指定访问的第一个顶点。（2）对图的遍历路径有可能构成一个回路，从而造成死循环，所以算法设计要考虑遍历路径可能出现的死循环问题。（3）一个顶点可能和若干个顶点都是邻接顶点，要使一个顶点的所有邻接顶点按照某种次序被访问。深度优先搜索遍历连通图的深度优先遍历递归算法可描述为：（1）访问顶点vi并标记顶点vi为已访问；（2）查找顶点v的第一个邻接顶点vj；（3）若顶点v的邻接顶点vj存在，则继续执行，否则算法结束；（4）若顶点vj尚未被访问，则深度优先遍历递归访问顶点vj；（5）查找顶点vi的邻接顶点vj的下一个邻接顶点，转到步骤（3）。当寻找顶点vi的邻接顶点vj成功时继续进行，当寻找顶点vi的邻接顶点vj失败时回溯到上一次递归调用的地方继续进行。为了在遍历过程中便于区分顶点是否被访问，需附设访问标志数组visited[]，其初值为0，一旦某个顶点被访问，则其相应的分量置为1。广度优先遍历算法： 需要一个队列以保持访问过的顶点的顺序，以便按顺序访问这些顶点邻接顶点。连通图的广度优先遍历算法为：（1）访问初始顶点v并标记顶点v为已访问；（2）顶点v入队列；（3）当队列非空时则继续执行，否则算法结束；（4）出队列取得队头顶点u；（5）查找顶点u的第一个邻接顶点w；（6）若顶点u的邻接顶点w不存在，则转到步骤（3），否则执行后序语句：①若顶点w尚未被访问，则访问顶点w并标记顶点w为已访问；②顶点w入队列；③查找顶点u的邻接顶点w后的下一个邻接顶点，转到步骤（6）。程序的流程程序由三个模块组成：（1）主程序模块：包括图的创建，邻接点的查找和顶点的查找（2）数据保存中间变量模块：实现用数组代替队列存取（3）元素结构单元模块：定义图每个元素的结构三、详细设计1．元素类型，图类型typedefstruct{char*vexs;//顶点向量intarcs[MAX_VEX][MAX_VEX];//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数}Graph,*GP;2．根据图的特点，G即为该图的名称，该程序的基本操作具体实现如下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;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<<"输入顶点："<<endl;for(i=0;i<G.vexnum;i++){//初始化顶点 cout<<"输入顶点"<<i<<":";cin>>G.vexs[i];temp=getchar();//接收回车}for(i=0;i<G.vexnum;i++)//初始化邻接矩阵for(j=0;j<G.vexnum;j++)G.arcs[i][j]=INFINITY;cout<<"输入弧:"<<endl;for(i=0;i<G.arcnum;i++){//初始化弧cout<<"输入弧"<<i<<":";cin>>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&&k<G.vexnum){//k合理for(inti=0;i<G.vexnum;i++)if(G.arcs[k][i]!=INFINITY)returni;}return-1;}//图G中顶点i的第j个邻接顶点的下一个邻接顶点intNextVex(GraphG,inti,intj){if(i>=0&&i<G.vexnum&&j>=0&&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=0;i<G.vexnum;i++)if(!visited[i])DFS(G,i);//对尚未访问的顶点调用DFS}else{visited[k]=true;cout<<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;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);}}}}3．主程序中，直接调用main函数其大概流程图为，具体代码实现如下：voidmain(){inti;GraphG;CreateUDN(G);visited=(bool*)malloc(G.vexnum*sizeof(bool));cout<<"广度优先遍历:";for(i=0;i<G.vexnum;i++)visited[i]=false;DFS(G,-1);cout<<endl;cout<<"深度优先遍历:";for(i=0;i<G.vexnum;i++)visited[i]=false;BFS(G);cout<<endl;}算法的时空分析:对于具有n个顶点e条边的无向图，当图采用邻接矩阵存储时，BFS算法的总时间为O（）。输入和输出的格式： 输入：输入定点数和弧数：mn输入定点：输入弧：输出：广度优先遍历：深度优先遍历：四、调试分析略。五、测试结果本实验的测试结果截图如下：分析：如右图所示六、用户使用说明（可选）1、本程序的运行环境为windows操作系统，执行文件为tu.exe2、运行程序时提示输入数据并且输入数据然后回车就可以继续输入相应数据，最后即可得到结果。七、实验心得（可选）本次实验设计内容比较多，虽然实验过程中多次出现问题，但通过多次调试最终得到解决。并且通过本次试验，对图的建立有了更深入的了解，对书上的代码进行了实现，熟悉并掌握了BFS、DFS算法，以及图的两种存储结构，对图结构的计算与运用有了进一步的体会。附录（实验代码）：#include<iostream>#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;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<<"输入顶点："<<endl;for(i=0;i<G.vexnum;i++){//初始化顶点 cout<<"输入顶点"<<i<<":";cin>>G.vexs[i];temp=getchar();//接收回车}for(i=0;i<G.vexnum;i++)//初始化邻接矩阵for(j=0;j<G.vexnum;j++)G.arcs[i][j]=INFINITY;cout<<"输入弧:"<<endl;for(i=0;i<G.arcnum;i++){//初始化弧cout<<"输入弧"<<i<<":";cin>>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&&k<G.vexnum){//k合理for(inti=0;i<G.vexnum;i++)if(G.arcs[k][i]!=INFINITY)returni;}return-1;}//图G中顶点i的第j个邻接顶点的下一个邻接顶点intNextVex(GraphG,inti,intj){if(i>=0&&i<G.vexnum&&j>=0&&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=0;i<G.vexnum;i++)if(!visited[i])DFS(G,i);//对尚未访问的顶点调用DFS}else{visited[k]=true;cout<<G.vexs[k];//访问第k个顶点for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))if(!visited[i])DFS(G,i);//对k的尚未访问的邻接