资源描述：
《实验五 图的遍历.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、实验五图的基本操作一、实验目的与内容1.实验目的1、使学生可以巩固所学的有关图的基本知识。2、熟练掌握图的存储结构。3、熟练掌握图的两种遍历算法。2.实验内容[问题描述] 对给定图，实现图的深度优先遍历和广度优先遍历。[基本要求] 以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。[测试数据] 由学生依据软件工程的测试技术自己确定。二．程序设计1.总体设计#include#defineMaxVerNum20struct
2、Edgenode{intedgever;//该弧所指向的的顶点的信息intinform;//该边的信息Edgenode*edgenext;//指向下一条边的指针};structVexnode{charvertex;Edgenode*firstarc;};structGraph{VexnodeAdjList[MaxVerNum];intvexnum,arcnum;//图的当前顶点数和弧数};//队列的定义及相关函数的实现structQueueNode{intnData;QueueNode*next;};structQu
3、eueNode{QueueNode*front;QueueNode*rear;};voidEnQueue(QueueList*Q,inte);//进队操作voidDeQueue(QueueList*Q,int*e);//出队操作voidCreatAdjList(Graph*G);//创建图voidDFS(Graph*G,inti,intvisit[]);//从第i个顶点出发递归的深度优先遍历图GvoidDFStraversal(Graph*G,charc);//对图G作深度优先遍历voidBFS(Graph*G,in
4、tv,intvisit[]);//从第v个顶点出发递归的广度优先遍历图GvoidBFStraversal(Graph*G,charc);//对图G作广度优先遍历2.详细设计l定义结构体QueueNode、QueueNode，并完成队列的基本操作，利用队列先进先出的性质，在广度优先遍历时将队列作为辅助工具来完成广度优先遍历。lvoidEnQueue(QueueList*Q,inte)函数实现进队操作，if-else语句完成函数的具体操作lvoidDeQueue(QueueList*Q,int*e)函数实现出队操作，if
5、-else语句完成函数的具体操作lvoidCreatAdjList(Graph*G)函数用来完成创建图的操作，其中使用两次for循环语句第一次用循环语句输入顶点，第二次建立无向图中的边和表，流程图如图表1所示lvoidDFS(Graph*G,inti,intvisit[])函数是从第i个顶点出发递归的深度优先遍历图Gk=0karcnumcout<<"请输入边对应的顶点:";cin>>i>>j;p1=newEdgenode;p1->edgever=j;p1->edgenext=G->AdjList
6、[i].firstarc;G->AdjList[i].firstarc=p1;p2=newEdgenode;p2->edgever=i;p2->edgenext=G->AdjList[j].firstarc;G->AdjList[j].firstarc=p2;truek++图表1lvoidDFStraversal(Graph*G,charc)函数对图G作深度优先遍历，首先用for循环语句初始化辅助数组，且全部初始化为0，表示的状态为未访问。其次，用for循环语句根据字符查找序号，调用DFS()函数从第i个顶点出发递归
7、的广度优先，流程图如图表2所示。最后再次使用for循环语句继续访问未被访问的结点，流程图如图表3所示i=0iarcnumtrueif(G->AdjList[i].vertex==c){m=i;DFS(G,i,visit);break;}i++i++if(visit[i]==0)DFS(G,i,visit);iarcnumi=0图表2图表3lvoidBFS(Graph*G,intv,intvisit[])函数从第v个顶点出发递归的广度优先遍历图G，使用辅助队列Q变量，在此函数中完成进队、出对操作。还定义
8、一个visit[]数组，用来标记顶点是否被访问过。在while循环进行相关的入队和出队操作，if-else循环进行将没有访问过的顶点入队falseQ->rear!=NULLtrueinte=0;DeQueue(Q,&e);cout<AdjList[e].vertex<<"";visit[e]=1;Edgenode*p=newEdgeno
