实验五图的遍历.docxVIP

实验五图的基本操作实验目的与内容1.实验目的1、使学生可以巩固所学的有关图的基本知识。2、熟练掌握图的存储结构。3、熟练掌握图的两种遍历算法。2.实验内容[问题描述]　　对给定图，实现图的深度优先遍历和广度优先遍历。[基本要求]　　　以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。[测试数据]　　由学生依据软件工程的测试技术自己确定。二．程序设计1.总体设计#includeiostream.h#define MaxVerNum 20 struct Edgenode{int edgever;//该弧所指向的的顶点的信息int inform;//该边的信息Edgenode *edgenext; //指向下一条边的指针};struct Vexnode {char vertex; Edgenode *firstarc;};struct Graph {Vexnode AdjList[MaxVerNum];int vexnum,arcnum ;//图的当前顶点数和弧数};//队列的定义及相关函数的实现struct QueueNode{int nData;QueueNode* next;};struct QueueNode{QueueNode* front;QueueNode* rear;};void EnQueue(QueueList* Q,int e);//进队操作void DeQueue(QueueList* Q,int* e);//出队操作void CreatAdjList(Graph* G);//创建图void DFS(Graph *G,int i,int visit[]);//从第i个顶点出发递归的深度优先遍历图Gvoid DFStraversal(Graph *G,char c);//对图G作深度优先遍历void BFS(Graph* G,int v,int visit[]);//从第v个顶点出发递归的广度优先遍历图Gvoid BFStraversal(Graph *G,char c);//对图G作广度优先遍历2.详细设计定义结构体QueueNode、QueueNode，并完成队列的基本操作，利用队列先进先出的性质，在广度优先遍历时将队列作为辅助工具来完成广度优先遍历。void EnQueue(QueueList* Q,int e)函数实现进队操作，if-else语句完成函数的具体操作void DeQueue(QueueList* Q,int* e)函数实现出队操作，if-else语句完成函数的具体操作void CreatAdjList(Graph* G)函数用来完成创建图的操作，其中使用两次for循环语句第一次用循环语句输入顶点，第二次建立无向图中的边和表，流程图如图表1所示void DFS(Graph *G,int i,int visit[])函数是从第i个顶点出发递归的深度优先遍历图Gk=0kG-arcnumcout请输入边Vi,Vj对应的顶点:;cinij;p1=new Edgenode;p1-edgever=j;p1-edgenext=G-AdjList[i].firstarc;G-AdjList[i].firstarc=p1;p2=new Edgenode;p2-edgever=i;p2-edgenext=G-AdjList[j].firstarc;G-AdjList[j].firstarc=p2;truek++图表1void DFStraversal(Graph *G,char c)函数对图G作深度优先遍历，首先用for循环语句初始化辅助数组，且全部初始化为0，表示的状态为未访问。其次，用for循环语句根据字符查找序号，调用DFS()函数从第i个顶点出发递归的广度优先，流程图如图表2所示。最后再次使用for循环语句继续访问未被访问的结点，流程图如图表3所示i=0iG-arcnumtrueif (G-AdjList[i].vertex==c){m=i;DFS(G,i,visit);break;}i++i++if(visit[i]==0)DFS(G,i,visit);iG-arcnumi=0图表2图表3void BFS(Graph* G,int v,int visit[])函数从第v个顶点出发递归的广度优先遍历图G，使用辅助队列Q变量，在此函数中完成进队、出对操作。还定义一个visit[]数组，用来标记顶点是否被访问过。在while循环进行相关的入队和出队操作，if-else循环进行将没有访问过的顶点入队falseQ-rear!=NULLtrueint e=0;DeQueue(Q,e);coutG-AdjList[e].ver