实验五图的基本操作一、实验目的1、使学生可以巩固所学的有关图的基本知识。

2、熟练掌握图的存储结构。

3、熟练掌握图的两种遍历算法。

二、实验内容[问题描述]对给定图，实现图的深度优先遍历和广度优先遍历。

[基本要求]以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。

以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。

【测试数据】由学生依据软件工程的测试技术自己确定。

三、实验前的准备工作1、掌握图的相关概念。

2、掌握图的逻辑结构和存储结构。

3、掌握图的两种遍历算法的实现。

四、实验报告要求1、实验报告要按照实验报告格式规范书写。

2、实验上要写出多批测试数据的运行结果。

3、结合运行结果，对程序进行分析。

五、算法设计1、程序所需头文件已经预处理宏定义和结构体定义如下#include<iostream.h>#define MaxVerNum 100struct edgenode{int endver;int inform;edgenode* edgenext;};struct vexnode{char vertex;edgenode* edgelink;};struct Graph{vexnode adjlists[MaxVerNum];int vexnum;int arcnum;};2、创建无向图void CreatAdjList(Graph* G){int i,j,k;edgenode* p1;edgenode* p2;cout<<"请输入顶点数和边数:"<<endl;cin>>G->vexnum>>G->arcnum;cout<<"开始输入顶点表:"<<endl;for (i=0;i<G->vexnum;i++){cin>>G->adjlists[i].vertex;G->adjlists[i].edgelink=NULL;}cout<<"开始输入边表信息:"<<endl;for (k=0;k<G->arcnum;k++){cout<<"请输入边<Vi,Vj>对应的顶点:";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;//因为是无向图，所以有两次建立边表的过程}}3、深度优先遍历void DFS(Graph *G,int i,int visit[]){cout<<G->adjlists[i].vertex<<" ";visit[i]=1;edgenode *p=new edgenode;p=G->adjlists[i].edgelink;if(G->adjlists[i].edgelink&&!visit[p->endver]){DFS(G,p->endver,visit);}}void DFStraversal(Graph *G,char c)//深度优先遍历{cout<<"该图的深度优先遍历结果为:"<<endl;int visit[MaxVerNum];for(int i=0;i<G->vexnum;i++){visit[i]=0;//全部初始化为0，即未访问状态}int m;for (i=0;i<G->vexnum;i++){if (G->adjlists[i].vertex==c)//根据字符查找序号{m=i;DFS(G,i,visit);break;}}//继续访问未被访问的结点for(i=0;i<G->vexnum;i++){if(visit[i]==0)DFS(G,i,visit);}cout<<endl;}4、广度优先遍历void BFS(Graph* G,int v,int visit[]){QueueList *Q=new QueueList;Q->front=Q->rear=NULL;EnQueue(Q,v);while(Q->rear!=NULL){int e=0;DeQueue(Q,&e);cout<<G->adjlists[e].vertex<<" ";visit[e]=1;edgenode* p=new edgenode;p=G->adjlists[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){cout<<"该图的广度优先遍历结果为:"<<endl; int visited[MaxVerNum];for (int i=0;i<G->vexnum;i++){visited[i]=0;}int m;for (i=0;i<G->vexnum;i++){if (G->adjlists[i].vertex==c){m=i;BFS(G,i,visited);break;}}//继续访问未被访问的结点for(i=0;i<G->vexnum;i++){if(visited[i]==0)BFS(G,i,visited);}cout<<endl;}六、调试与测试测试数据，如图：七、总结通过做这次实验，发现自己在数据结构这门课中还有很多不足有很多知识还没掌握，所以在写程序的时候出现了很多的错误，及还有很多的知识不以灵活运用。

C++没有掌握好，所以这次做本次实验还是吃力，刚开始完全没有思路，后来经过查找资料，在自己的努力下和同学的帮助下，终于完了本次实验，此次实验发现的自己的不足，在以后的学习中，我会更加的努力。

八、源代码#include<iostream.h>#define MaxVerNum 100struct 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<<"请输入顶点数和边数:"<<endl;cin>>G->vexnum>>G->arcnum;cout<<"开始输入顶点表:"<<endl;for (i=0;i<G->vexnum;i++){cin>>G->adjlists[i].vertex;G->adjlists[i].edgelink=NULL;}cout<<"开始输入边表信息:"<<endl;for (k=0;k<G->arcnum;k++){cout<<"请输入边<Vi,Vj>对应的顶点:";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[]){cout<<G->adjlists[i].vertex<<" ";visit[i]=1;edgenode *p=new edgenode;p=G->adjlists[i].edgelink;if(G->adjlists[i].edgelink&&!visit[p->endver]){DFS(G,p->endver,visit);}}void DFStraversal(Graph *G,char c)//深度优先遍历{cout<<"该图的深度优先遍历结果为:"<<endl;int visit[MaxVerNum];for(int i=0;i<G->vexnum;i++){visit[i]=0;//全部初始化为0，即未访问状态}int m;for (i=0;i<G->vexnum;i++){if (G->adjlists[i].vertex==c)//根据字符查找序号{m=i;DFS(G,i,visit);break;}}//继续访问未被访问的结点for(i=0;i<G->vexnum;i++){if(visit[i]==0)DFS(G,i,visit);}cout<<endl;}//广度优先遍历void BFS(Graph* G,int v,int visit[]){QueueList *Q=new QueueList;Q->front=Q->rear=NULL;EnQueue(Q,v);while(Q->rear!=NULL){int e=0;DeQueue(Q,&e);cout<<G->adjlists[e].vertex<<" ";visit[e]=1;edgenode* p=new edgenode;p=G->adjlists[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){cout<<"该图的广度优先遍历结果为:"<<endl; int visited[MaxVerNum];for (int i=0;i<G->vexnum;i++){visited[i]=0;}int m;for (i=0;i<G->vexnum;i++){if (G->adjlists[i].vertex==c){m=i;BFS(G,i,visited);break;}}//继续访问未被访问的结点for(i=0;i<G->vexnum;i++){if(visited[i]==0)BFS(G,i,visited);}cout<<endl;}void main(){Graph * G=new Graph; CreatAdjList(G);char ch;cout<<"请输入开始遍历的顶点:"; cin>>ch;DFStraversal(G,ch); BFStraversal(G,ch);}。