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

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

2、>#include<stdlib.h>#defineMAX_VERTEX_NUM20#defineOVERFLOW-1intvisited80;typedefstructArcNodeintadjvex;/该弧所指向的顶点的位置structArcNode*nextarc;指向下一条弧的指针ArcNode;typedefstructVNodeintdata;顶点信息ArcNode*firstarc;指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;typedefstructAdjListvertices;intvexnum,arcnum;图的

3、当前顶点数和弧数ALGraph;typedefstructQNodeintdata;structQNode*next;QNode,*QueuePtr;typedefstructQueuePtrfront;/队头指针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)

4、插入元素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;否则返回ERRORif(q.front=q.rear)returnfalse;QueuePtrp;p=q.front->next;e=p->data;q.front->next=

5、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;i<G.vexnum;i+)if(G.verticesi.data=v)returni;用邻接表构造无向图voidCreateDG(ALGraph&G)inti,j,k;printf("

6、;输入图的顶点数和弧度：n");scanf("%d%d",&G.vexnum,&G.arcnum);printf("输入顶点信息：n");for(i=0;i<G.vexnum;i+)(scanf("%d",&G.verticesi.data);G.verticesi.firstarc=NULL;printf("输入邻接点：n");for(k=0;k<G.arcnum;k+)(charv1,v2;scanf("%d%d",&v1,&v2

7、);i=LocateVex(G,v1);j=LocateVex(G,v2);structArcNode*s;s=(ArcNode*)malloc(sizeof(ArcNode);s->adjvex=j;s->nextarc=G.verticesi.firstarc;G.verticesi.firstarc=s;structArcNode*t;t=(ArcNode*)malloc(sizeof(ArcNode);t->adjvex=i;t->nextarc=G.verticesj.firstarc;G.verticesj.firstarc=t;voidDFSAL(ALGr

8、aphG,intv0)(visitedv0=1;printf("%5d",G.verticesv0.data);structArcNode*p;intw;for(p=G.verticesv0.firstarc;p;p=p->nextarc)w=p->adjvex;if(!visitedw)DFSAL(G,w);/深度优先搜索遍历voidDFSTraverse(ALGraphG)intv0;for(v0=0;v0<G.vexnum;v0+)visitedv0=0;访问标志数组初始化直到图中所有顶点都被访问到为止for(v0=0;v0<G.vexnum;

9、v0+)if(!visitedv0)DFSAL(G,v0);/对尚未访问的顶点调用DFSAL/广度优先搜索遍历voidBFSTraverse(ALGraphG,LinkQueueq)intu,w;structArcNode*p;for(u=0;u<G.vexnum;u+)visitedu=0;访问标志数组初始化InitQueue(q);for(u=0;u<G.vexnum;u+)if(!visitedu)printf("%5d",G.verticesu.data);visitedu=1;EnQueue(q,u);while(!QueueEmpty(q)u=DeQ

10、ueue(q);p=G.verticesu.firstarc;while(p)w=p->adjvex;if(!visitedw)visitedw=1;printf("%5d",G.verticesw.data);EnQueue(q,w);/ifp=p->nextarc;/while/while/ifBFSTraverseintmain()ALGraphG;LinkQueueq;CreateDG(G);printf("n");printf("输出深度优先搜索序列：n");DFSTraverse(G);printf("n");printf("输出广度优先搜索序列：n