【数据结构与数据库-实验报告】图的遍历(深度和广度).pdf
版权归原作者 Amber 所有1/16数据结构与数据库数据结构与数据库实验报告实验报告题题目目图的遍历（深/广度）院院系系化学物理系姓姓名名*学学号号*指导老师指导老师司 虎提交时间提交时间2011 年 12 月 5 日 星期三版权归原作者 Amber 所有2/16一一 实验内容1、图的深度优先搜索（DFS）和广度优先搜索（BFS）。2、图的最小生成树和最短路径(选作)。二 目的与要求1、掌握 DFS 和 BFS 原理，并用 DFS 和 BFS 打印图的顶点信息。2、掌握图的最小生成树算法和最短路径算法。三 实验算法本程序要点在于运用队列实现图的创建及遍历。1、队列及结点的定义typedef structint*base;int front;int rear;SqQueue;void InitQueue(SqQueue&Q)Q.base=(int*)malloc(sizeof(int)*MAXQSIZE);if(!Q.base)printf(ERROR!n);Q.front=Q.rear=0;版权归原作者 Amber 所有3/16void EnQueue(SqQueue&Q,int e)if(Q.front=(Q.rear+1)%(MAXQSIZE)printf(队满！n);return;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;void DeQueue(SqQueue&Q,int&e)if(Q.rear=Q.front)printf(队是空的n);return;e=Q.baseQ.front;Q.front=(Q.front+1)%(MAXQSIZE);int EmptyQueue(SqQueue Q)return Q.front=Q.rear?1:0;#define max_n 20typedef struct ArcNodeint adjvex;struct ArcNode*nextarc;ArcNode;typedef struct VNode版权归原作者 Amber 所有4/16int data;ArcNode*firstarc;VNode,AdjListmax_n;typedef structAdjList vertices;int vexnum,arcnum;int kind;ALGraph;2、创建图图的类型“2”，代表无向图。类型，顶点数，边数用逗号隔开。顶点，边的偶对均为输入一组，按回车建。void CreateGraph(ALGraph&G)int k,i,j;int vi,vj;ArcNode*p;printf(请输入类型，顶点数，边数：);scanf(%d,%d,%d,&G.kind,&G.vexnum,&G.arcnum);printf(请输入顶点：);for(k=0;kG.vexnum;k+)scanf(%d,&G.verticesk.data);G.verticesk.firstarc=NULL;版权归原作者 Amber 所有5/16printf(请输入边的偶对：n);for(k=0;kadjvex=j;p-nextarc=G.verticesi.firstarc;G.verticesi.firstarc=p;if(G.kind=AG)p=(ArcNode*)malloc(sizeof(ArcNode);p-adjvex=i;p-nextarc=G.verticesj.firstarc;G.verticesj.firstarc=p;3、打印图void PrintGraph(ALGraph G)int i;ArcNode*p;for(i=0;iadjvex);p=p-nextarc;while(p!=NULL);printf(n);4、深度优先序列void DFS(ALGraph G,int v)/*深度优先序列*/ArcNode*p;visite(G.verticesv.data);visitedv=TRUE;for(p=G.verticesv.firstarc;p!=NULL;p=p-nextarc)if(!visitedp-adjvex)DFS(G,p-adjvex);5、广度优先序列void BFS(ALGraph G)/*广度优先序列*/int v,u,w;SqQueue Q;for(v=0;vG.vexnum;v+)visitedv=FALSE;InitQueue(Q);for(v=0;v=0;w=NextAdjVex(G,u,w)if(!visitedw)visite(w);visitedw=TRUE;EnQueue(Q,w);6、主函数void main()ALGraph G;CreateGraph(G);PrintGraph(G);printf(输出深度优先序列：n);DFS(G,0);printf(输出广度优先序列：n);BFS(G);四 程序结构1、数据结构版权归原作者 Amber 所有8/16typedef struct/队列int*base;int front;int rear;SqQueue;typedef struct/结点定义AdjList vertices;int vexnum,arcnum;int kind;ALGraph;2.主要函数功能说明void CreateGraph(ALGraph&G)/*创建图*/void PrintGraph(ALGraph G)/*打印图*/void DFS(ALGraph G,int v)/*深度优先序列*/void BFS(ALGraph G)/*广度优先序列*/void main()/*主函数*/五 实验结果与分析上述程序在 Visual C+6.0 环境下加以实现。经过多次测试，程序运行正确。结果如图：版权归原作者 Amber 所有9/16即为图：1357六 心得体会1、通过实验更加了解队列及图的知识2、本程序界面不够人性化，且功能不够完善，需改进。七 实验源程序（附件）#include#include#include#include版权归原作者 Amber 所有10/16#define AG 2#define MAXQSIZE50#define TRUE 1#define FALSE 0typedef struct/队列int*base;int front;int rear;SqQueue;void InitQueue(SqQueue&Q)/初始队列Q.base=(int*)malloc(sizeof(int)*MAXQSIZE);if(!Q.base)printf(ERROR!n);Q.front=Q.rear=0;void EnQueue(SqQueue&Q,int e)/进队if(Q.front=(Q.rear+1)%(MAXQSIZE)printf(队满！n);return;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;版权归原作者 Amber 所有11/16void DeQueue(SqQueue&Q,int&e)/出队if(Q.rear=Q.front)printf(队是空的n);return;e=Q.baseQ.front;Q.front=(Q.front+1)%(MAXQSIZE);int EmptyQueue(SqQueue Q)/清空队return Q.front=Q.rear?1:0;#define max_n 20typedef struct ArcNode/结点定义int adjvex;struct ArcNode*nextarc;ArcNode;typedef struct VNodeint data;ArcNode*firstarc;VNode,AdjListmax_n;typedef structAdjList vertices;int vexnum,arcnum;版权归原作者 Amber 所有12/16int kind;ALGraph;int LocateVex(ALGraph G,char v)int i,j=-1;for(i=0;iG.vexnum;i+)if(G.verticesi.data=v)j=i;return j;void CreateGraph(ALGraph&G)/创建图int k,i,j;int vi,vj;ArcNode*p;printf(请输入类型，顶点数，边数：);scanf(%d,%d,%d,&G.kind,&G.vexnum,&G.arcnum);printf(请输入顶点：);for(k=0;kG.vexnum;k+)scanf(%d,&G.verticesk.data);G.verticesk.firstarc=NULL;printf(请输入边的偶对：n);for(k=0;kadjvex=j;p-nextarc=G.verticesi.firstarc;G.verticesi.firstarc=p;if(G.kind=AG)p=(ArcNode*)malloc(sizeof(ArcNode);p-adjvex=i;p-nextarc=G.verticesj.firstarc;G.verticesj.firstarc=p;void PrintGraph(ALGraph G)/打印图int i;ArcNode*p;for(i=0;iadjvex);p=p-nextarc;版权归原作者 Amber 所有14/16while(p!=NULL);printf(n);void visite(int i)printf(%d,i);unsigned visitedmax_n;void DFS(ALGraph G,int v)/深度优先ArcNode*p;visite(G.verticesv.data);visitedv=TRUE;for(p=G.verticesv.firstarc;p!=NULL;p=p-nextarc)if(!visitedp-adjvex)DFS(G,p-adjvex);int FirstAdjVex(ALGraph G,int v)ArcNode*p;p=G.verticesv.firstarc;if(!p)return-1;版权归原作者 Amber 所有15/16else return p-adjvex;int NextAdjVex(ALGraph G,int v,int w)ArcNode*p=G.verticesv.firstarc;while(p&p-adjvex!=w)p=p-nextarc;if(!p|!p-nextarc)return-1;else return p-nextarc-adjvex;void BFS(ALGraph G)/广度优先int v,u,w;SqQueue Q;for(v=0;vG.vexnum;v+)visitedv=FALSE;InitQueue(Q);for(v=0;v=0;w=NextAdjVex(G,u,w)if(!visitedw)visite(w);visitedw=TRUE;EnQueue(Q,w);void main()/主函数ALGraph G;CreateGraph(G);PrintGraph(G);printf(输出深度优先序列：n);DFS(G,0);printf(输出广度优先序列：n);BFS(G);
