图的深度优先遍历和广度优先遍历

1、华北水利水电学院 数据结构 实验报告20 10 20 11 学年 第 一 学期 2008级 计算机 专业班级： 107 学号： 200810702 姓名： 王文波 实验四 图的应用一、 实验目的：1掌握图的存储结构及其构造方法2掌握图的两种遍历算法及其执行过程二、 实验内容：以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现无向连通图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。提示：首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先和广度优先遍历，并输出遍历的结果。三、 实验要求：1 各班学号为单号的同学采用邻接矩阵实现，学号为双号的同

2、学采用邻接表实现。2 C/ C+完成算法设计和程序设计并上机调试通过。3 撰写实验报告，提供实验结果和数据。4 写出算法设计小结和心得。四、 程序源代码：#include<iostream.h>#define MaxVerNum 50 struct edgenodeint endver;int inform;edgenode* edgenext; ;struct vexnode char vertex;edgenode* edgelink;struct Graph vexnode adjlistsMaxVerNum;int vexnum;int arcnum;/队列的定义及相关函数

3、的实现struct QueueNodeint 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;elseQ->rear->next=q;Q->rear=Q->rear->nex

4、t;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<<"请输入顶点数和边数:"<

5、<endl;cin>>G->vexnum>>G->arcnum;cout<<"开始输入顶点表:"<<endl;for (i=0;i<G->vexnum;i+)cin>>G->adjlistsi.vertex;G->adjlistsi.edgelink=NULL;cout<<"开始输入边表信息:"<<endl;for (k=0;k<G->arcnum;k+)cout<<"请输入边<Vi,Vj&

6、gt;对应的顶点:"cin>>i>>j;p1=new edgenode;p1->endver=j;p1->edgenext=G->adjlistsi.edgelink;G->adjlistsi.edgelink=p1;p2=new edgenode;p2->endver=i;p2->edgenext=G->adjlistsj.edgelink;G->adjlistsj.edgelink=p2;/因为是无向图，所以有两次建立边表的过程/-深度优先遍历void DFS(Graph *G,int i,int visit

7、)cout<<G->adjlistsi.vertex<<" "visiti=1;edgenode *p=new edgenode;p=G->adjlistsi.edgelink;if(G->adjlistsi.edgelink&&!visitp->endver)DFS(G,p->endver,visit);void DFStraversal(Graph *G,char c)/深度优先遍历cout<<"该图的深度优先遍历结果为:"<<endl;int visitM

8、axVerNum;for(int i=0;i<G->vexnum;i+)visiti=0;/全部初始化为0，即未访问状态int m;for (i=0;i<G->vexnum;i+)if (G->adjlistsi.vertex=c)/根据字符查找序号m=i;DFS(G,i,visit);break;/继续访问未被访问的结点for(i=0;i<G->vexnum;i+)if(visiti=0)DFS(G,i,visit);cout<<endl;/-广度优先遍历void BFS(Graph* G,int v,int visit)QueueLis

9、t *Q=new QueueList;Q->front=Q->rear=NULL;EnQueue(Q,v);while(Q->rear!=NULL)int e=0;DeQueue(Q,&e);cout<<G->adjlistse.vertex<<" "visite=1;edgenode* p=new edgenode;p=G->adjlistse.edgelink;if(p)int m=p->endver;if(m=0)EnQueue(Q,m);while(visitm=0)p=p->edgenext

10、;if(p=NULL)break;m=p->endver;EnQueue(Q,m);void BFStraversal(Graph *G,char c)cout<<"该图的广度优先遍历结果为:"<<endl;int visitedMaxVerNum;for (int i=0;i<G->vexnum;i+)visitedi=0;int m;for (i=0;i<G->vexnum;i+)if (G->adjlistsi.vertex=c)m=i;BFS(G,i,visited);break;/继续访问未被访问的结点f

11、or(i=0;i<G->vexnum;i+)if(visitedi=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);五、 程序运行情况（写出输入数据及运行结果）六、 小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）注：内容一律使用宋体五号字，单倍行间距本次试验采用的

12、是邻接表的方式实现图的深度优先遍历和广度优先遍历。对于深度优先遍历，主要是采用递归的方式，广度优先遍历借助队列来实现。试验本身问题不是太大，但要注意输入的问题，什么时候用空格，什么时候用回车，这一点是需要注意的，因为一旦数据的输入有问题，结果当然也就不可能正确了。只有正确的输入数据，建立图，才能得出正确的遍历结果。#include "stdio.h"#define MaxVerNum 50 struct edgenodeint endver;int inform;edgenode* edgenext; ;struct vexnode char vertex;edgenode

13、* edgelink;struct Graph vexnode adjlistsMaxVerNum;int vexnum;int arcnum;/队列的定义及相关函数的实现struct QueueNodeint 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=NU

14、LL)Q->front=Q->rear=q;elseQ->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(

15、Graph* G)int i,j,k;edgenode* p1;edgenode* p2;printf("请输入顶点数和边数:n");scanf("%d%d",&G->vexnum,&G->arcnum);printf("开始输入顶点表:n");for (i=0;i<(G->vexnum);i+)fflush(stdin);/清空缓存scanf("%c",&G->adjlistsi.vertex);getchar();/吸收回车字符G->adjlistsi

16、.edgelink=NULL;printf("开始输入边表信息:n");for (k=0;k<G->arcnum;k+)printf("请输入边<Vi,Vj>对应的顶点:n");scanf("%d%d",&i,&j);p1=new edgenode;p1->endver=j;p1->edgenext=G->adjlistsi.edgelink;G->adjlistsi.edgelink=p1;p2=new edgenode;p2->endver=i;p2->e

17、dgenext=G->adjlistsj.edgelink;G->adjlistsj.edgelink=p2;/因为是无向图，所以有两次建立边表的过程/-深度优先遍历void DFS(Graph *G,int i,int visit)printf("%c ",G->adjlistsi.vertex);visiti=1;edgenode *p=new edgenode;p=G->adjlistsi.edgelink;if(G->adjlistsi.edgelink&&!visitp->endver)DFS(G,p->e

18、ndver,visit);void DFStraversal(Graph *G,char c)/深度优先遍历printf("该图的深度优先遍历结果为:");int visitMaxVerNum;for(int i=0;i<G->vexnum;i+)visiti=0;/全部初始化为0，即未访问状态int m;for (i=0;i<G->vexnum;i+)if (G->adjlistsi.vertex=c)/根据字符查找序号m=i;DFS(G,i,visit);break;/继续访问未被访问的结点for(i=0;i<G->vexnum

19、;i+)if(visiti=0)DFS(G,i,visit);printf("n");/-广度优先遍历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);printf("%c ",G->adjlistse.vertex);visite=1;edgenode* p=new edgenode;p=G->adjlistse.edgelink;if(p)int m=p->endver;if(m=0)EnQueue(Q,m);while(visitm=0)p=p->edgenext;if(p=NULL)break;m=p->endver;EnQueue(Q,m);void BFStraversal(Graph *G,char c)printf("该图的广度优先遍历结果为:");int visitedMaxVerNum;for (int i=0;i<G->vexnum;i+)visitedi=0;int m;for (i=0;i<G->