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

《无向图的存储及深度和广度优先遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、图进行广度优先的非递归遍历4、测试数据：输入各结点元素：a,b,c,d,e,f,g,h；输入图中的各边：1,21,32,42,53,63,74,85,8操作选项输入1进行深度优先遍历；遍历结果为：13762584操作选项输入2进行广度优先遍历；遍历结果为：1327654二概要设计（1）抽象数据类型定义：#defineMaxVerNum100//边表结点typedefstructnode{intadjvex;structnode*next;}EdgeNode,*ENode;顶点表结点；typedef

3、structvnode{charvertex;EdgeNode*firstedge;}VertexNode;typedefVertexNodeAdjList[MaxVerNum];定义图；typedefstruct{AdjListadjlist;intn,e;}AlGraph;AlGraphG;（2）主程序的流程：1.根据提示输入顶点个数和边的个数；2.输入图的各边；3.输入数字执行相关操作（3）其函数之间调用关系如下：main()模块（开始创建链表）Create（）创建图输入1输入2按广度优先遍

4、历按深度优先遍历输入0结束操作执行结束后，重新执行判定操作和循环。三详细设计1.元素类型#defineMaxVerNum100typedefstructnode{intadjvex;structnode*next;}EdgeNode,*ENode;typedefstructvnode{charvertex;EdgeNode*firstedge;}VertexNode;typedefVertexNodeAdjList[MaxVerNum];typedefstruct{AdjListadjlist;i

5、ntn,e;}AlGraph;AlGraphG;2．每个模块的分析：（1）主程序模块：intmain(){inta,v;//创建图Create(G);printf("请选择要进行的操作：选择深度优先请输入1；选择广度优先请输入2；结束操作请输入0");scanf("%d",&a);while(a!=0){printf("请输入开始遍历顶点的坐标");scanf("%d",&v);if(a==1)//深度优先遍历DfsTravel(G,v);}elseif(a==2)//广度优先

6、遍历{BfsTravel(G,v);}printf("请选择要进行的操作：选择深度优先请输入1；选择广度优先请输入2；结束操作请输入0");scanf("%d",&a);}return0;}（2）深度优先遍历voidDfsTravel(AlGraph&G,intv){ENodestack[MaxVerNum];ENodep;intvisited[MaxVerNum],top=-1,i;for(i=0;i

7、：");printf("%d",v);visited[v]=1;p=G.adjlist[v].firstedge;while(top!=-1

8、

9、p!=NULL){while(p!=NULL){if(visited[p->adjvex]==1)p=p->next;else{printf("%d",p->adjvex);visited[p->adjvex]=1;top++;stack[top]=p;p=G.adjlist[p->adjvex].firstedge;}}if(top!=-1){p=s

10、tack[top];top--;p=p->next;}}printf("");}（3）广度优先遍历voidBfsTravel(AlGraph&G,intv){intvisited[MaxVerNum];intqueue[MaxVerNum];intfront=-1,rear=-1;EdgeNode*p;inti;for(i=0;i