实验四图的应用深度优先／广度优先搜索遍历

实验四图的应用深度优先／广度优先搜索遍历实验四图的应用深度优先／广度优先搜索遍历华北水利水电学院数据结构实验报告 2012,2013学年第一学期 2010级计算机科学与技术专业班级: 201013432 学号: 201013432 姓名: 蔡启林实验四图的应用一、实验题目: 图的应用——深度优先,广度优先搜索遍历二、实验内容: 很多涉及图上操作的算法都是以图的遍历操作为基础的。试编写一个算法，实现图的深度优先和广度优先搜索遍历操作。要求:以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现连通无向...

实验四图的应用深度优先／广度优先搜索遍历华北水利水电学院数据结构实验报告 2012,2013学年第一学期 2010级计算机科学与技术专业班级: 201013432 学号: 201013432 姓名: 蔡启林实验四图的应用一、实验题目: 图的应用——深度优先,广度优先搜索遍历二、实验内容 : 很多涉及图上操作的算法都是以图的遍历操作为基础的。试编写一个算法，实现图的深度优先和广度优先搜索遍历操作。要求:以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现连通无向图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。(注:学号为奇数的同学使用邻接矩阵存储结构实现，学号为偶数的同学使用邻接矩阵实现) 提示:首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先、广度优先搜索遍历，并输出遍历的结果。三、程序源代码: #include #define max 100 int visited[max]; typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode { char data; ArcNode *firstarc; }VNode,AdjList[max]; typedef struct { AdjList vertices; int vexnum,arcnum; 第 1 页共 7 页 }ALGraph; typedef struct QNode { char data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue; int InitQueue(LinkQueue &Q) { Q.front=Q.rear=new QNode; if(!Q.front)return 0; Q.front->next=NULL; return 1; } int QueueEmpty(LinkQueue &Q) { if(Q.front==Q.rear) return 1; else return 0; } int EnQueue(LinkQueue &Q,char e) { QNode *p; p=new QNode; if(!p)return 0; 第 2 页共 7 页 p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return 1; } char DeQueue(LinkQueue &Q,int &e) { QNode *p; if(Q.front==Q.rear)return 0; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p)Q.rear=Q.front; delete(p); return 1; } int LocateVex(ALGraph G,int v) { int i; for(i=0;v!=G.vertices[i].data&&i=G.vexnum) return -1; return i; } void CreatGraph(ALGraph &G) { int k,i,j; ArcNode *p,*q; cout<<"请输入顶点总数:"; cin>>G.vexnum; 第 3 页共 7 页 cout<<"请输入边数:"; cin>> G.arcnum; char v1,v2; cout<<"输入顶点信息:"; for(i=0;i>G.vertices[i].data; G.vertices[i].firstarc=NULL; } cout<<"请输入边的信息"<>v1>>v2; i=LocateVex(G,v1); j=LocateVex(G,v2); p=new ArcNode; q=new ArcNode; p->adjvex=j; p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p; q->adjvex=i; q->nextarc=G.vertices[j].firstarc; G.vertices[j].firstarc=q; } } int FirstAdjVex(ALGraph G,int v) { if(!G.vertices[v].firstarc) return 0; return G.vertices[v].firstarc->adjvex; } 第 4 页共 7 页 int NextAdjVex(ALGraph G,int v,int w) { ArcNode *p; p=G.vertices[v].firstarc; while(p&&p->adjvex!=w) p=p->nextarc; if(!p->nextarc) return -1; else return p->nextarc->adjvex; } void DFS(ALGraph G,int v) { int w; visited[v]=1; cout<=0;w=NextAdjVex(G,v,w)) if(!visited[w]) DFS(G,w); } void BFSTraverse(ALGraph G ) { int v,w,u;LinkQueue Q; for(v=0;v=0;w=NextAdjVex(G,v,w)) if(!visited[w]) { visited[w]=1; cout<>ch; for(i=0;i 小结 (包括收获、心得体会、存在的问题及解决问题的方法、建议等) 注:内容一律使用宋体五号字，单倍行间距这次实验让我深刻的理解了用邻接表做存储结构时怎么构造无向图，以及图的两种遍历方式是怎么实现，本次试验采用的是邻接表的方式实现图的深度优先遍历和广度优先遍历。对于深度优先遍历，主要是采用递归的方式，广度优先遍历借助队列来实现。试验本身问题不是太大，但要注意输入的问题，什么时候用空格，什么时候用回车，这一点是需要注意的，因为一旦数据的输入有问题，结果当然也就不可能正确了。只有正确的输入数据，建立图，才能得出正确的遍历结，在进行这个程序的编写时，遇到了种种的问题，首先定位函数不太会写，纠结半天，寻求同学的帮助才解决，还有就是在创建无向图的时候，没有考虑其无向的特征，才耗费了许久的时间。另外就是在深度优先遍历时，找该点的邻接点函数不会写，之后仔细看了算法后，才明白是寻找依附于该点的第一条指针的顶点信息，再查看该点的下一个指针，并判断其顶点信息不为空，这才解决一大难题。当然大问题是解决了，但是在进行广度优先遍历时，遇到了问题，就是广度优先遍历的前半部分是正确的，但后半部分是错误的或者有的是正确的，但是复杂的就是错误的，仔细检查了半天，才发现是元素出队列时与进队列的字母表示的不一样，才会造成这样的结果。这也警告我们在编写程序时，要格外的小心，一个小疏忽就会让程序无法运行或者是运行错误～第 7 页共 7 页

                    本文档为【实验四图的应用深度优先／广度优先搜索遍历】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

实验四图的应用深度优先／广度优先搜索遍历

你可能还喜欢