资源描述：
《数据结构实验报告图的遍历.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第3小组实验报告数据结构试验报告实验四图的存储及应用实验题目：图的遍历问题专业班级：计科系1405班组长：张纪远（）组员：周振军（）朱新祥（）梁丽蓉（）段慧娟（）2016年6月1日18第3小组实验报告实验报告实验类型__综合设计__实验室_软件实验室三__一、实验题目图的存储及应用二、实验目的和要求1．掌握图的存储思想及其存储实现2．掌握图的深度、广度优先遍历算法思想及其程序实现3．掌握图的常见应用算法的思想及其程序实现三、需求分析1．问题描述使用菜单实现图的相关算法,如键盘输入以下结点数据：太原、成都、北京、上海、天津
2、、大连、河北，建立一个有向图或无向图（自定）的邻接表并输出该邻接表；在图的邻接表的基础上计算各顶点的度，并输出；以有向图的邻接表为基础实现输出它的拓扑排序序列；采用邻接表存储实现无向图的深度优先遍历；采用邻接表存储实现无向图的广度优先遍历；采用邻接矩阵存储实现无向图的最小生成树的PRIM算法2.设计分析调用菜单项，分别调用相应的子函数。注意顶点存储地名，使用字符数组来实现。3.结构类型定义typedefcharvextype[10];/*顶点数据类型*/typedefintedgetype;/*边数据类型*/typede
3、fstruct{vextypevex[MAXSIZE];edgetypearc[MAXSIZE][MAXSIZE];intvexnum,arcnum;}Mgraph;typedefstructnode{intadjvex;structnode*next}EdgeNode;typedefstructnode{vextypevex;EdgeNode*firstedge;}VexNode;typedefstruct{VexNodeadjvex[MAXSIZE];18第3小组实验报告intn,e;}ALGraph;二、概要设计为
4、了实现上述程序功能，代码如下：#include#include#includetypedefstructnode{//边表结点intadj;//边表结点数据域structnode*next;}node;typedefstructvnode{//顶点表结点charname[20];node*fnext;}vnode,AList[20];typedefstruct{AListList;//邻接表intv,e;//顶点树和边数}*Graph;//建立无向邻接表Graph
5、CreatDG(){GraphG;inti,j,k;node*s;G=malloc(20*sizeof(vnode));printf("请输入图的顶点数和边数(空格隔开)：");scanf("%d%d",&G->v,&G->e);//读入顶点数和边数for(i=0;iv;i++){printf("请输入图中第%d元素：",i+1);scanf("%s",G->List[i].name);//读入顶点信息18第3小组实验报告G->List[i].fnext=NULL;//边表置为空表}for(k=0;ke;
6、k++){printf("请请输入第%d条边的两顶点序号(空格隔开)：",k+1);scanf("%d%d",&i,&j);//读入边（Vi,Vj）的顶点对序号;s=(node*)malloc(sizeof(node));//生成边表结点s->adj=j;s->next=G->List[i].fnext;G->List[i].fnext=s;//将新结点*s插入顶点Vi的边表头部s=(node*)malloc(sizeof(node));s->adj=i;//邻接点序号为is->next=G->List[j].fnext
7、;G->List[j].fnext=s;//将新结点*s插入顶点Vj的边表头部}returnG;}//有向邻接图GraphCreatAG(){GraphG;inti,j,k;node*q;G=malloc(20*sizeof(vnode));printf("请输入图的顶点数和边数【空格隔开】：");scanf("%d%d",&G->v,&G->e);for(i=0;iv;i++){printf("请输入图中第%d元素：",i+1);scanf("%s",&G->List[i].name);//读入顶点信息G->L
8、ist[i].fnext=NULL;}for(k=0;ke;k++){printf("请请输入第%d边的两顶点序号【空格隔开】：",k+1);scanf("%d%d",&i,&j);18第3小组实验报告q=(node*)malloc(sizeof(node));//生成新边表结点sq->adj=j;//邻接点
