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