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

《实验四-图的应用——深度优先／广度优先搜索遍历.doc》由会员分享，可在线阅读，更多相关《实验四-图的应用——深度优先／广度优先搜索遍历.doc（21页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date实验四-图的应用深度优先广度优先搜索遍历华北水利水电学院 数据结构 实验报告数据结构 实验报告实验四 图的应用一、 实验题目：图的应用深度优先广度优先搜索遍历二、 实验内容：很多涉及图上操作的算法都是以图的遍历操作为基础的。试编写一个算法，实现图的深度优先和广度优先搜索遍历操作。要求：以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现连通无向图的深度优先及广

2、度优先搜索遍历，并输出遍历的结点序列。（注：学号为奇数的同学使用邻接矩阵存储结构实现，学号为偶数的同学使用邻接矩阵实现）提示：首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先、广度优先搜索遍历，并输出遍历的结果。三、程序源代码：#include#include#define MAX_VERTEX_NUM 20#define OVERFLOW -1int visited80;typedef struct ArcNodeint adjvex; /该弧所指向的顶点的位置struct ArcNode *nextarc; /指向下一条弧的指针ArcNode;ty

3、pedef struct VNodeint data; /顶点信息ArcNode *firstarc; /指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,arcnum;/图的当前顶点数和弧数ALGraph;typedef struct QNodeint data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;/队头指针QueuePtr rear;/队尾指针LinkQueue;void Ini

4、tQueue(LinkQueue &q)/构造一个空队列qq.front=q.rear=(QueuePtr)malloc(sizeof(QNode);if(!q.front) exit(OVERFLOW);q.front-next=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(Li

5、nkQueue &q)int e;/若队列不空，则删除q的队头元素，用e返回其值，并返回OK;否则返回ERRORif(q.front=q.rear) return false;QueuePtr 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 L

6、ocateVex(ALGraph G,int v)int i;for(i=0;iG.vexnum;i+)if(G.verticesi.data=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;iG.vexnum;i+)scanf(%d,&G.verticesi.data);G.verticesi.firstarc=NULL;printf(输入邻接点:n);for(k=0;k

7、adjvex=j;s-nextarc=G.verticesi.firstarc;G.verticesi.firstarc=s;struct ArcNode *t;t=(ArcNode *)malloc(sizeof(ArcNode);t-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.firs

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

9、 *p;for(u=0;uG.vexnum;u+) visitedu=0; /访问标志数组初始化InitQueue(q);for(u=0;uadjvex;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(输出深度优先搜索序列：n);DFSTraverse(G);printf(n);printf(输出广度优先搜索序列：n);BFSTraverse(G,q);printf(n);return 0;四、 测试结果：-