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

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

1、数据结构实验报告实验四图的应用一、实验题目：图的应用——深度优先／广度优先搜索遍历二、实验内容：很多涉及图上操作的算法都是以图的遍历操作为基础的。试编写一个算法，实现图的深度优先和广度优先搜索遍历操作。要求：以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现连通无向图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。（注：学号为奇数的同学使用邻接矩阵存储结构实现，学号为偶数的同学使用邻接矩阵实现）提示：首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先、广度优先

2、搜索遍历，并输出遍历的结果。三、程序源代码：#include#include#defineMAX_VERTEX_NUM20#defineOVERFLOW-1intvisited[80];typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针}ArcNode;typedefstructVNode{intdata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶

3、点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;//图的当前顶点数和弧数}ALGraph;typedefstructQNode{intdata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;voidInitQueue(LinkQueue&q){//

4、构造一个空队列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;

5、q.rear=p;}intDeQueue(LinkQueue&q){inte;//若队列不空，则删除q的队头元素，用e返回其值，并返回OK;否则返回ERRORif(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

6、，否则返回FLASEif(q.front==q.rear)returntrue;elsereturnfalse;}intLocateVex(ALGraphG,intv){inti;for(i=0;i

7、顶点信息:");for(i=0;i

8、->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].first