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

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

2、h>#include<stdlib.h>#define MAX_VERTEX_NUM 20#define OVERFLOW -1int visited80;typedef struct ArcNodeint adjvex; /该弧所指向的顶点的位置struct ArcNode *nextarc; /指向下一条弧的指针ArcNode;typedef struct VNodeint data; /顶点信息ArcNode *firstarc; /指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vert

3、ices; int vexnum,arcnum;/图的当前顶点数和弧数ALGraph;typedef struct QNodeint data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;/队头指针QueuePtr rear;/队尾指针LinkQueue;void InitQueue(LinkQueue &q)/构造一个空队列qq.front=q.rear=(QueuePtr)malloc(sizeof(QNode);if(!q.front) exit(OVERFLOW);q.front->nex

4、t=NULL;void EnQueue(LinkQueue &q,int e) /插入元素e为q的新的队尾元素QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p) exit(OVERFLOW);/存储分配失败p->data=e;p->next=NULL;q.rear->next=p;q.rear=p;int DeQueue(LinkQueue &q)int e;/若队列不空，则删除q的队头元素，用e返回其值，并返回OK;否则返回ERRORif(q.front=q.rear) return false;QueueP

5、tr p;p=q.front->next;e=p->data;q.front->next=p->next;if(q.rear=p) q.rear=q.front;free(p);return e; bool QueueEmpty(LinkQueue &q) /若队列q为空队列，则返回TRUE，否则返回FLASEif(q.front=q.rear) return true;else return false;int LocateVex(ALGraph G,int v)int i;for(i=0;i<G.vexnum;i+)if(G.verticesi.dat

6、a=v)return i;/用邻接表构造无向图void CreateDG(ALGraph &G)int i,j,k;printf("输入图的顶点数和弧度: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")

7、;for(k=0;k<G.arcnum;k+)char v1,v2;scanf("%d %d",&v1,&v2);i=LocateVex(G,v1);j=LocateVex(G,v2);struct ArcNode *s;s=(ArcNode *)malloc(sizeof(ArcNode);s->adjvex=j;s->nextarc=G.verticesi.firstarc;G.verticesi.firstarc=s;struct ArcNode *t;t=(ArcNode *)malloc(sizeof(ArcNode);t->

8、;adjvex=i;t->nextarc=G.verticesj.firstarc;G.verticesj.firstarc=t;void DFSAL(ALGraph G,int v0)visitedv0=1;printf("%5d",G.verticesv0.data); struct ArcNode *p;int w;for(p=G.verticesv0.firstarc;p;p=p->nextarc)w=p->adjvex;if(!visitedw)DFSAL(G,w);/深度优先搜索遍历void DFSTraverse(ALGraph G)int

9、v0;for(v0=0;v0<G.vexnum;v0+) visitedv0=0; /访问标志数组初始化/直到图中所有顶点都被访问到为止for(v0=0;v0<G.vexnum;v0+)if(!visitedv0)DFSAL(G,v0); /对尚未访问的顶点调用DFSAL/广度优先搜索遍历void BFSTraverse(ALGraph G,LinkQueue q) int u,w; struct ArcNode *p;for(u=0;u<G.vexnum;u+) visitedu=0; /访问标志数组初始化InitQueue(q);for(u=0;u<G.vexnum

10、;u+)if(!visitedu)printf("%5d",G.verticesu.data);visitedu=1;EnQueue(q,u);while(!QueueEmpty(q)u=DeQueue(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/if/BFSTraverseint main()ALGraph G;LinkQueue q;CreateDG(G);printf("n");printf(&q