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

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

2、实现。2.C/ C+完成算法设计和程序设计并上机调试通过。3.撰写实验报告，提供实验结果和数据。4.写出算法设计小结和心得。四、 程序源代码：#in clude#defi ne MaxVerNum 50struct edge nodeint en dver;int in form;edge no de* edge next;struct vexnode char vertex;edge no de* edgeli nk;struct Graphvex node adjlistsMaxVerNum; int vexnum;int arcnum;/队列的定义及相关函数的实现struct Queue

3、Node页脚int n Data;QueueNode* n ext;；struct QueueListQueueNode* front;QueueNode* rear;；void En Queue(QueueList* Q,i nt e)QueueNode *q=new QueueNode; q-n Data=e;q- next=NULL; if(Q=NULL) return;if(Q-rear=NULL)Q_fron t=Q-rear=q;elseQ-rear- n ext=q; Q-rear=Q-rear- n ext;void DeQueue(QueueList* Q,i nt* e)i

4、f (Q=NULL) return;if (Q-fr on t=Q_rear)*e=Q-fro nt- nData;Q-fro nt=Q-rear=NULL;else*e=Q-fro nt- nData;Q-fron t=Q-fr ont-n ext;/创建图void CreatAdjList(Graph* G)int i,j,k;页脚edgenode* p1;edgenode* p2;cout请输入顶点数和边数: G-vex num G-arc num;cout开始输入顶点表:endl;for (i=0;ivex nu m;i+)cin G-adjlistsi.vertex;G-adjlis

5、tsi.edgeli nk=NULL;cout开始输入边表信息:endl;for (k=0;karc nu m;k+)cout请输入边对应的顶点：；cinij;p1=new edgenode;p1-e ndver=j;p1-edge next=G-adjlistsi.edgeli nk;G-adjlistsi.edgeli nk=p1;p2=new edgenode;p2-e ndver=i;p2-edge next=G-adjlistsj.edgeli nk;G-adjlistsj.edgeli nk=p2;/因为是无向图，所以有两次建立边表的过程/-void DFS(Graph *G,i

6、nt i,i nt visit)coutadjlistsi.vertexadjlistsi.edgeli nk;if(G-adjlistsi.edgeli nk&! visitp-e ndver)DFS(G,p-e ndver,visit);void DFStraversal(Graph *G,char c)/ 深度优先遍历cout该图的深度优先遍历结果为:endl;in t visitMaxVerNum;for(i nt i=0;ivex nu m;i+)深度优先遍历页脚visiti=O;全部初始化为 0,即未访问状态int m;for (i=0;ivex nu m;i+)if (G

7、-adjlistsi.vertex=c) 根据字符查找序号m=i;DFS(G,i,visit); break;/继续访问未被访问的结点for(i=0;ivex nu m;i+)if(visiti=0)DFS(G,i,visit);coutfro nt=Q-rear=NULL;En Queue(Q,v);while(Q-rear!=NULL)int e=0;DeQueue(Q, &e);coutadjlistse.vertexadjlistse.edgeli nk;if(p)int m=p-e ndver;if(m=0)En Queue(Q,m);while(visitm=0)p=p-e

8、dge next;if(p=NULL)break;广度优先遍历页脚m=p-e ndver;En Queue(Q,m);void BFStraversal(Graph *G,char c)cout该图的广度优先遍历结果为in t visitedMaxVerNum;for (i nt i=0;ivex nu m;i+)visitedi=0;int m;for (i=0;ivex nu m;i+)if (G-adjlistsi.vertex=c)m=i;BFS(G,i,visited); break;/继续访问未被访问的结点for(i=0;ivex nu m;i+)if(visitedi=0)BFS

9、(G,i,visited);coute ndl;void mai n()Graph * G=new Graph;CreatAdjList(G);char ch;cout ch;DFStraversal(G,ch);BFStraversal(G,ch);:1,1,1,噓优优边U0UVUKVU始度f度一.A-A-IA-入人A-A-囱m的-始E图开请举I1嚣Klldeo10nls三U-O6P IDpougpeX七 Elppouxe10nls】xugpIDpougpe-E04u二 u-匕pulu-pou6p10nls09EnNexel/l=ITOP0 pnQu軒rvWTHnl-go屈严K民严“dr土：

10、JLaiBYUM*!产1. EiMr理鲁益15wrvjm-x笛巳常2工-2r:二P:-TB W二s1 乍董Jtk.r-t-T 一星、*鼻-雷一kn二|/|帑二ri殳S匸-k =U2 _srrs &Ji.-wlM:WCFfa.J二；書Kttlkr獻*麻袪唸fXzl卫n Data=e;q- next=NULL;if(Q=NULL)return;if(Q-rear=NULL)Q_fron t=Q-rear=q;elseQ-rear- n ext=q; Q-rear=Q-rear- n ext;void DeQueue(QueueList* Q,i nt* e)if (Q=NULL)retur

11、n;if (Q-fr on t=Q-rear)*e=Q-fro nt- nData;页脚Q-fro nt=Q-rear=NULL;else*e=Q-fro nt- nData;Q-fron t=Q-fr ont-n ext;/创建图void CreatAdjList(Graph* G)int i,j,k;edgenode* p1;edgenode* p2;printf(请输入顶点数和边数:n);scan f(%d%d,&G-vex num,&G-arcnum); printf(开始输入顶点表:n);for (i=0;ivex nu m);i+)fflush(stdin); 清空

12、缓存sca nf(%c,&G-adjlistsi.vertex); getchar();/吸收回车字符 G-adjlistsi.edgeli nk=NULL;printf(开始输入边表信息:n);for (k=0;karc nu m;k+)printf(请输入边对应的顶点:n); scanf(%d%d, &i,&j);p1=new edgenode;p1-e ndver=j;p1-edge next=G-adjlistsi.edgeli nk;G-adjlistsi.edgeli nk=p1;p2=new edgenode;页脚p2-e ndver=i;p2-edge

13、next=G-adjlistsj.edgeli nk;G-adjlistsj.edgeli nk=p2;/因为是无向图，所以有两次建立边表的过程/-void DFS(Graph *G,i nt i,i nt visit)prin tf(%c ,G-adjlistsi.vertex);visiti=1;edge node *p=new edge no de;p=G-adjlistsi.edgeli nk;if(G-adjlistsi.edgeli nk&!visitp-e ndver)DFS(G,p-e ndver,visit);void DFStraversal(Graph *G,ch

14、ar c)/ 深度优先遍历printf(该图的深度优先遍历结果为：”)；in t visitMaxVerNum;for(i nt i=0;ivex nu m;i+)visiti=0;全部初始化为 0,即未访问状态int m;for (i=0;ivex nu m;i+)if (G-adjlistsi.vertex=c)/ 根据字符查找序号m=i;DFS(G,i,visit);break;深度优先遍历页脚/继续访问未被访问的结点for(i=0;ivex nu m;i+)if(visiti=O)DFS(G,i,visit);prin tf(n);/-voidBFS(Graph* G,i nt v,i

15、 nt visit)QueueList *Q=new QueueList;Q-fro nt=Q-rear=NULL;En Queue(Q,v);while(Q-rear!=NULL)int e=0;DeQueue(Q, &e);prin tf(%c ”,G-adjlistse.vertex); visite=1;edge no de* p=new edge no de;p=G-adjlistse.edgeli nk;if(p)int m=p-e ndver;if(m=0)En Queue(Q,m);while(visitm=0)p=p-edge next; if(p=NULL)brea

16、k;m=p-e ndver;En Queue(Q,m);广度优先遍历页脚void BFStraversal(Graph *G,char c)printf(该图的广度优先遍历结果为：”);in t visitedMaxVerNum;for (int i=0;ivex nu m;i+)visitedi=0;int m;for (i=0;ivex nu m;i+)if (G-adjlistsi.vertex=c)m=i;BFS(G,i,visited);break;/继续访问未被访问的结点for(i=0;ivex nu m;i+)if(visitedi=0)BFS(G,i,visited);printf();void DispAdjList(Graph *G)int i, z;edgenode* p;printf(”图的邻接表表示如下：n);for (i=0;ivex nu m;i+)prin tf(%d,%3c=,i,G-adjlistsi.vertex);p=G-adjl