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

第1页共7页数据结构实验报告实验四图的应用一、实验题目：图的应用——深度优先／广度优先搜索遍历二、实验内容：很多涉及图上操作的算法都是以图的遍历操作为基础的。试编写一个算法，实现图的深度优先和广度优先搜索遍历操作。要求：以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现连通无向图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。（注：学号为奇数的同学使用邻接矩阵存储结构实现，学号为偶数的同学使用邻接矩阵实现）提示：首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先、广度优先搜索遍历，并输出遍历的结果。三、程序源代码：#includestdio.h#includestdlib.h#defineMAX_VERTEX_NUM20#defineOVERFLOW-1intvisited[80];typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针}ArcNode;typedefstructVNode{intdata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;//图的当前顶点数和弧数}ALGraph;第2页共7页typedefstructQNode{intdata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;voidInitQueue(LinkQueue&q){//构造一个空队列qq.front=q.rear=(QueuePtr)malloc(sizeof(QNode));if(!q.front)exit(OVERFLOW);q.front-next=NULL;}voidEnQueue(LinkQueue&q,inte){//插入元素e为q的新的队尾元素QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);//存储分配失败p-data=e;p-next=NULL;q.rear-next=p;q.rear=p;}intDeQueue(LinkQueue&q){inte;//若队列不空，则删除q的队头元素，用e返回其值，并返回OK;否则返回ERROR第3页共7页if(q.front==q.rear)returnfalse;QueuePtrp;p=q.front-next;e=p-data;q.front-next=p-next;if(q.rear==p)q.rear=q.front;free(p);returne;}boolQueueEmpty(LinkQueue&q){//若队列q为空队列，则返回TRUE，否则返回FLASEif(q.front==q.rear)returntrue;elsereturnfalse;}intLocateVex(ALGraphG,intv){inti;for(i=0;iG.vexnum;i++)if(G.vertices[i].data==v)returni;}//用邻接表构造无向图voidCreateDG(ALGraph&G){inti,j,k;printf(输入图的顶点数和弧度:\n);scanf(%d%d,&G.vexnum,&G.arcnum);第4页共7页printf(输入顶点信息:\n);for(i=0;iG.vexnum;i++){scanf(%d,&G.vertices[i].data);G.vertices[i].firstarc=NULL;}printf(输入邻接点:\n);for(k=0;kG.arcnum;k++){charv1,v2;scanf(%d%d,&v1,&v2);i=LocateVex(G,v1);j=LocateVex(G,v2);structArcNode*s;s=(ArcNode*)malloc(sizeof(ArcNode));s-adjvex=j;s-nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=s;structArcNode*t;t=(ArcNode*)malloc(sizeof(ArcNode));t-adjvex=i;t-nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=t;}}voidDFSAL(ALGraphG,intv0){visited[v0]=1;第5页共7页printf(%5d,G.vertices[v0].data);structArcNode*p;intw;for(p=G.vertices[v0].firstarc;p;p=p-nextarc){w=p-adjvex;if(!visited[w])DFSAL(G,w);}}//深度优先搜索遍历voidDFSTraverse(ALGraphG){intv0;for(v0=0;v0G.vexnum;v0++)visited[v0]=0;//访问标志数组初始化//直到图中所有顶点都被访问到为止for(v0=0;v0G.vexnum;v0++)if(!visited[v0])DFSAL(G,v0);//对尚未访问的顶点调用DFSAL}//广度优先搜索遍历voidBFSTraverse(ALGraphG,LinkQueueq){intu,w;structArcNode*p;for(u=0;uG.vexnum;u++)visited[u]=0;//访问标志数组初始化InitQueue(q);for(u=0;uG.vexnum;u++)if(!visited[u]){printf(%5d,G.vertices[u].data);第6页共7页visited[u]=1;EnQueue(q,u);while(!QueueEmpty(q)){u=DeQueue(q);p=G.vertices[u].firstarc;while(p){w=p-adjvex;if(!visited[w]){visited[w]=1;printf(%5d,G.vertices[w].data);EnQueue(q,w);}//ifp=p-nextarc;}//while}//while}//if}//BFSTraverseintmain(){ALGraphG;LinkQueueq;CreateDG(G);printf(\n);printf(输出深度优先搜索序列：\n);DFSTraverse(G);printf(\n);printf(输出广度优先搜索序列：\n);BFSTraverse(G,q);第7页共7页printf(\n);return0;}四、测试结果：