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

《实验四图的应用深度优先／广度优先搜索遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、矩阵实现）提示：首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先、广度优先搜索遍历，并输出遍历的结果。三、程序源代码：#include#definemax100intvisited[max];typedefstructArcNode{intadjvex;structArcNode*nextarc;}ArcNode;typedefstructVNode{chardata;ArcNode*firstarc;}VNode,AdjList[max];typedefstruct

3、{AdjListvertices;intvexnum,arcnum;第7页共7页}ALGraph;typedefstructQNode{chardata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;intInitQueue(LinkQueue&Q){Q.front=Q.rear=newQNode;if(!Q.front)return0;Q.front->next=NULL;return1;}intQueue

4、Empty(LinkQueue&Q){if(Q.front==Q.rear)return1;elsereturn0;}intEnQueue(LinkQueue&Q,chare){QNode*p;p=newQNode;if(!p)return0;第7页共7页p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;return1;}charDeQueue(LinkQueue&Q,int&e){QNode*p;if(Q.front==Q.rear)return0;p=Q.front->next;e=p

5、->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;delete(p);return1;}intLocateVex(ALGraphG,intv){inti;for(i=0;v!=G.vertices[i].data&&i=G.vexnum)return-1;returni;}voidCreatGraph(ALGraph&G){intk,i,j;ArcNode*p,*q;cout<<"请输入顶点总数：";cin>>G.vexnum;第7

6、页共7页cout<<"请输入边数：";cin>>G.arcnum;charv1,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=newArcNode;q=newArcNode;p->adjvex=j;p

7、->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p;q->adjvex=i;q->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=q;}}intFirstAdjVex(ALGraphG,intv){if(!G.vertices[v].firstarc)return0;returnG.vertices[v].firstarc->adjvex;}第7页共7页intNextAdjVex(ALGraphG,intv,i

8、ntw){ArcNode*p;p=G.vertices[v].firstarc;while(p&&p->adjvex!=w)p=p->nextarc;if(!p->nextarc)return-1;elsereturnp->nexta