无向图的存储及深度和广度优先遍历

1、数据结构实验报告实验题目:无序图的存储并分别实现深度和广度优先遍历实验目的：理解并掌握以邻接表的方式存储图，以及图的非递归的深度和广度优先遍历实验内容：首先将图的元素输入并以邻接表的方式存储，然后分别进行递归和非递归遍历。 一、需求分析1、输入的形式和输入值的范围：输入图的顶点元素和边；输入数字选择要进行的操作：深度遍历，广度遍历或结束操作。2、输出的形式:按深度或者广度优先顺序输出各节点的编号3、程序所能达到的功能：（1）以邻接表的方式存储图（2）对图进行深度优先的非递归遍历（3）对图进行广度优先的非递归遍历4、测试数据：输入各结点元素：a,b,c,d,e,f,g,h；输入图中的各边：1,2

2、 1,3 2,4 2,5 3,6 3,7 4,8 5,8操作选项 输入1进行深度优先遍历；遍历结果为：1 3 7 6 2 5 8 4操作选项 输入2进行广度优先遍历；遍历结果为：1 3 2 7 6 5 4二 概要设计（1）抽象数据类型定义：#define MaxVerNum 100/边表结点typedef struct nodeint adjvex;struct node *next;EdgeNode,*ENode;顶点表结点；typedef struct vnodechar vertex;EdgeNode *firstedge;VertexNode;typedef VertexNode Ad

3、jListMaxVerNum;定义图；typedef structAdjList adjlist;int n,e;AlGraph;AlGraph G;（2）主程序的流程：1. 根据提示输入顶点个数和边的个数；2. 输入图的各边； 3. 输入数字执行相关操作（3）其函数之间调用关系如下：main()模块 （开始创建链表）Create（）创建图输入1输入2按广度优先遍历按深度优先遍历 输入0结束操作 执行结束后，重新执行判定操作和循环。三 详细设计1.元素类型#define MaxVerNum 100typedef struct nodeint adjvex;struct node *next;E

4、dgeNode,*ENode;typedef struct vnodechar vertex;EdgeNode *firstedge;VertexNode;typedef VertexNode AdjListMaxVerNum;typedef structAdjList adjlist;int n,e;AlGraph;AlGraph G;2每个模块的分析：（1）主程序模块：int main() int a,v; /创建图Create(G); printf(请选择要进行的操作：n 选择深度优先请输入1；n 选择广度优先请输入2；n结束操作请输入0n); scanf(%d,&a); while(a

5、!=0) printf(请输入开始遍历顶点的坐标n); scanf(%d,&v); if(a=1) /深度优先遍历 DfsTravel(G,v); else if(a=2) /广度优先遍历 BfsTravel(G,v); printf(请选择要进行的操作：n 选择深度优先请输入1；n 选择广度优先请输入2；n结束操作请输入0n); scanf(%d,&a); return 0;（2）深度优先遍历void DfsTravel(AlGraph &G,int v)ENode stackMaxVerNum;ENode p;int visitedMaxVerNum,top=-1,i;for(i=0;ia

6、djvex=1)p=p-next;elseprintf(%d ,p-adjvex);visitedp-adjvex=1;top+;stacktop=p;p=G.adjlistp-adjvex.firstedge;if(top!=-1) p=stacktop; top-; p=p-next;printf(n);（3）广度优先遍历void BfsTravel(AlGraph &G,int v)int visitedMaxVerNum;int queueMaxVerNum;int front=-1,rear=-1; EdgeNode *p; int i; for(i=0;iadjvex=0)prin

7、tf(%d ,p-adjvex); visitedp-adjvex=1;rear=rear+1;queuerear=p-adjvex;p=p-next;printf(n);(4)创建图void Create(AlGraph &G)int i,j,k;EdgeNode *s,*r;printf(请依次输入无向图顶点个数和边的个数n);scanf(%d,%d,&(G.n),&(G.e);getchar();printf(请输入各顶点信息n);for(i=0;iG.n;i+)scanf(%c,&(G.adjlisti.vertex);getchar(); G.adjlisti.firstedge=N

8、ULL;printf(请输入各边的信息，输入格式为i,jn); for(k=0;kadjvex=j;s-next= G.adjlisti.firstedge;G.adjlisti.firstedge=s; r=(EdgeNode*)malloc(sizeof(EdgeNode);r-adjvex=i;r-next= G.adjlistj.firstedge;G.adjlistj.firstedge=r;四 使用说明、测试分析及结果输入各结点元素：a,b,c,d,e,f,g,h；输入图中的各边：1,2 1,3 2,4 2,5 3,6 3,7 4,8 5,8操作选项 输入1进行深度优先遍历；遍历结果为：1 3 7 6 2 5 8 4操作选项 输入2进行广度优先遍历；遍历结果为：1 3 2 7 6 5 41.程序使用说明；（1）本程序的运行环境为VC6.0。（2）进入演示程序后即显示提示信息：请输入顶点个数和边的个数：2、测试结果与分析；输入各结点元素：a,b,c,d,e,f,g,h；输入图中的各边：1,2