实验五 图的基本操作.docx

实验五 图的基本操作一、实验目的1、使学生可以巩固所学的有关图的基本知识2、熟练掌握图的存储结构3、熟练掌握图的两种遍历算法二、实验内容[问题描述]对给定图，实现图的深度优先遍历和广度优先遍历[基本要求]以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历以用户指定的结点为起点，分别输出每种遍历下的结点访问序列测试数据】由学生依据软件工程的测试技术自己确定三.算法设计 1、主要思想：图的深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广假设初始状态是图中所有定点未曾被访问，则深度优先搜索可以从图中的某个顶点v 出发，访问此顶点，然后依次从 v 的未被访问的邻接点出发深度优先搜索遍历此图，直至图中所有和 v 有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问为止，所使用的为递归算法图的广度优先搜索遍历类似于树的按层次遍历的过程假设从图中某定点 v 出发，在访问了 v 之后依次访问 v 的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的定点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。

若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问为止，过程需要使用数组，非递归2、本程序包含三个模块1）创建图void CreatAdjList(Graph* G)2）深度优先搜索遍历void DFS(Graph *G,int i,int visit[])3）广度优先搜索遍历void BFS(Graph* G,int v,int visit[])void BFStraversal(Graph *G,char c)四.调试分析1.在遍历图时，对图中每个顶点至多调用一次 DFS 函数，因为一旦某个顶点被标志程已被访问，就不再从它出发进行搜索2.遍历图的过程实质上是对每个顶点查找其邻接点的过程其耗费的时间取决于所采用的存储结构3. 深度优先搜索遍历的时间复杂度和广度优先搜索遍历相同，两者不同之处仅仅在于对顶点的访问顺序不同五.实验结果构造图，输入关于图的数据，进行遍历的顶点开始深度优先搜索遍历和广度优先搜索遍历五、总结这次实验让我深刻的理解了用邻接表做存储结构时怎么构造无向图, 以及图的两种遍历方式是怎么实现, 本次试验采用的是邻接表的方式实现图的深度优先遍历和广度优先遍历。

对于深度优先遍历,主要是采用递归的方式,广度优先遍历借助队列来实现七.源程序（带注释）#includeusing namespace std;#define MaxVerNum 50struct edgenode{int endver;int inform;edgenode* edgenext;};struct vexnode{char vertex;edgenode* edgelink;};struct Graph{vexnode adjlists[MaxVerNum];int vexnum;int arcnum;};//队列的定义及相关函数的实现struct QueueNode{int nData;QueueNode* next;};struct QueueList{QueueNode* front;QueueNode* rear;};void EnQueue(QueueList* Q,int e){QueueNode *q=new QueueNode;q->nData=e;q->next=NULL;if(Q==NULL)return;if(Q->rear==NULL)Q->front=Q->rear=q;else{Q->rear->next=q;Q->rear=Q->rear->next;}}void DeQueue(QueueList* Q,int* e){if (Q==NULL)return;if (Q->front==Q->rear){*e=Q->front->nData;Q->front=Q->rear=NULL;}else{*e=Q->front->nData;Q->front=Q->front->next;}}//创建图void CreatAdjList(Graph* G){int i,j,k;edgenode* p1;edgenode* p2;cout>G->vexnum>>G->arcnum;coutvexnum;i++){cin>>G->adjlists[i].vertex;G->adjlists[i].edgelink=NULL;}coutarcnum;k++){cout对应的顶点:";cin>>i>>j;p1=new edgenode;p1->endver=j;p1->edgenext=G->adjlists[i].edgelink;G->adjlists[i].edgelink=p1;p2=new edgenode;p2->endver=i;p2->edgenext=G->adjlists[j].edgelink;G->adjlists[j].edgelink=p2;//因为是无向图，所以有两次建立边表的过程}}//--------------------------------深度优先遍历void DFS(Graph *G,int i,int visit[]){coutadjlists[i].vertexadjlists[i].edgelink;if(G->adjlists[i].edgelink&&!visit[p->endver]){DFS(G,p->endver,visit);}}void DFStraversal(Graph *G,char c)//深度优先遍历{coutvexnum;i++){visit[i]=0;//全部初始化为 0，即未访问状态}int m;for (int i=0;ivexnum;i++){if (G->adjlists[i].vertex==c)//根据字符查找序号{m=i;DFS(G,i,visit);break;}}//继续访问未被访问的结点for(int i=0;ivexnum;i++){if(visit[i]==0)DFS(G,i,visit);}coutfront=Q->rear=NULL;EnQueue(Q,v);while(Q->rear!=NULL){int e=0;DeQueue(Q,&e);coutadjlists[e].vertexadjlists[e].edgelink;if(p){int m=p->endver;if(m==0){EnQueue(Q,m);while(visit[m]==0){p=p->edgenext;if(p==NULL)break;m=p->endver;EnQueue(Q,m);}}}}}void BFStraversal(Graph *G,char c){coutvexnum;i++){visited[i]=0;}int m;for (int i=0;ivexnum;i++){if (G->adjlists[i].vertex==c){m=i;BFS(G,i,visited);break;}}//继续访问未被访问的结点for(int i=0;ivexnum;i++){if(visited[i]==0)BFS(G,i,visited);}cout>ch;DFStraversal(G,ch);BFStraversal(G,ch);return 0;}。