数据结构实验报告图的遍历

第3小组实验报告1数据结构试验报告实验四图的存储及应用实验题目：图的遍历问题专业班级：计科系1405班组长：张纪远（2014100518）组员：周振军（2014100551）朱新祥（2014100552）梁丽蓉（2014100526）段慧娟（2014100512）2016年6月1日第3小组实验报告2实验报告实验类型__综合设计__实验室_软件实验室三__一、实验题目图的存储及应用二、实验目的和要求1．掌握图的存储思想及其存储实现2．掌握图的深度、广度优先遍历算法思想及其程序实现3．掌握图的常见应用算法的思想及其程序实现三、需求分析1．问题描述使用菜单实现图的相关算法,如键盘输入以下结点数据：太原、成都、北京、上海、天津、大连、河北，建立一个有向图或无向图（自定）的邻接表并输出该邻接表；在图的邻接表的基础上计算各顶点的度，并输出；以有向图的邻接表为基础实现输出它的拓扑排序序列；采用邻接表存储实现无向图的深度优先遍历；采用邻接表存储实现无向图的广度优先遍历；采用邻接矩阵存储实现无向图的最小生成树的PRIM算法2.设计分析调用菜单项，分别调用相应的子函数。注意顶点存储地名，使用字符数组来实现。3.结构类型定义typedefcharvextype[10];/*顶点数据类型*/typedefintedgetype;/*边数据类型*/typedefstruct{vextypevex[MAXSIZE];edgetypearc[MAXSIZE][MAXSIZE];intvexnum,arcnum;}Mgraph;typedefstructnode{intadjvex;structnode*next}EdgeNode;typedefstructnode{vextypevex;EdgeNode*firstedge;}VexNode;typedefstruct{VexNodeadjvex[MAXSIZE];第3小组实验报告3intn,e;}ALGraph;四、概要设计为了实现上述程序功能，代码如下：#includestdio.h#includestdlib.h#includestring.htypedefstructnode{//边表结点intadj;//边表结点数据域structnode*next;}node;typedefstructvnode{//顶点表结点charname[20];node*fnext;}vnode,AList[20];typedefstruct{AListList;//邻接表intv,e;//顶点树和边数}*Graph;//建立无向邻接表GraphCreatDG(){GraphG;inti,j,k;node*s;G=malloc(20*sizeof(vnode));printf(请输入图的顶点数和边数(空格隔开)：);scanf(%d%d,&G-v,&G-e);//读入顶点数和边数for(i=0;iG-v;i++){printf(请输入图中第%d元素：,i+1);scanf(%s,G-List[i].name);//读入顶点信息第3小组实验报告4G-List[i].fnext=NULL;//边表置为空表}for(k=0;kG-e;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;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;iG-v;i++){printf(请输入图中第%d元素：,i+1);scanf(%s,&G-List[i].name);//读入顶点信息G-List[i].fnext=NULL;}for(k=0;kG-e;k++){printf(请请输入第%d边的两顶点序号【空格隔开】：,k+1);scanf(%d%d,&i,&j);第3小组实验报告5q=(node*)malloc(sizeof(node));//生成新边表结点sq-adj=j;//邻接点序号为jq-next=G-List[i].fnext;G-List[i].fnext=q;}returnG;}//输出图的邻接表voidPrint(GraphG){inti;node*p;printf(\t=======邻接表========\n);for(i=0;iG-v;i++){p=G-List[i].fnext;printf(%d|%3s,i,G-List[i].name);while(p){printf(-%3s,G-List[p-adj].name);printf(-%d,p-adj);p=p-next;}printf(\n);}}typedefstruct{charvex[20];}Lists[20];typedefstruct{Listsl;intedge[20][20];//邻接矩阵intv1,e1;//顶点数和弧数}AGraph;typedefstruct{第3小组实验报告6intdata;/*某顶点与已构造好的部分生成树的顶点之间权值最小的顶点*/intlowcost;/*某顶点与已构造好的部分生成树的顶点之间的最小权值*/}ClosEdge[20];/*用普里姆算法求最小生成树时的辅助数组*/voidCreateAN(AGraph*G1){/*构造邻接矩阵结构的图G*/inti,j,k,w;printf(请输入图的顶点数和边数（空格隔开）：);scanf(%d%d,&G1-v1,&G1-e1);//读入顶点数和边数for(i=1;i=G1-v1;i++){printf(请输入图%d号元素：,i);scanf(%s,&G1-l[i].vex);//读入顶点信息}for(i=1;i=G1-v1;i++)//初始化邻接矩阵for(j=1;j=G1-v1;j++)G1-edge[i][j]=9;for(k=1;k=G1-e1;k++){printf(请输入两顶点及边的权值（空格隔开）：);scanf(%d%d%d,&i,&j,&w);G1-edge[i][j]=w;G1-edge[j][i]=w;}}voidPrintAN(AGraph*G1){inti,j;printf(\t=======邻接矩阵========\n);for(i=1;i=G1-v1;i++){for(j=1;j=G1-v1;j++)printf(%3d,G1-edge[i][j]);printf(\n);}}//输出各顶点的度数第3小组实验报告7voidDu(GraphG){inti,j;node*p;printf(\n----各点度数----\n);for(i=0;iG-v;i++){p=G-List[i].fnext;printf(顶点%2s的度为：,G-List[i].name);j=0;while(p){j++;p=p-next;}printf(%d\n,j);}}//栈typedefstructstack{intx;structstack*next;}stack;intpush(stack*s,inti){stack*p;p=(stack*)malloc(sizeof(stack));p-x=i;p-next=s-next;s-next=p;return1;}intpop(stack*s,intj){stack*p=s-next;//保存栈顶指针j=p-x;s-next=p-next;//将栈顶元素摘下第3小组实验报告8free(p);//释放栈顶空间returnj;}//拓扑排序voidTopo(GraphG,stack*s){inti,k,count;intj=0;intindegree[20]={0};node*p;for(i=0;iG-v;i++){p=G-List[i].fnext;;while(p!=NULL){indegree[p-adj]++;p=p-next;}}for(i=0;iG-v;i++)if(indegree[i]==0)push(s,i);count=0;while(s-next!=NULL){i=pop(s,j);printf(%2s,G-List[i].name);++count;for(p=G-List[i].fnext;p!=NULL;p=p-next){k=p-adj;if(!(--indegree[k]))push(s,k);}}if(countG-v)printf(有回路!);}第3小组实验报告9voidDFS(GraphG,inti,intflag[]){node*p;printf(%2s,G-List[i].name);flag[i]=1;p=G-List[i].fnext;while(p){if(!flag[p-adj])DFS(G,p-adj,flag);p=p-next;}}//深度优先遍历voidDFSTravel(GraphG){inti;intflag[20];//标志数组for(i=0;iG-v;i++)flag[i]=0;for(i=0;iG-v;i++)if(!flag[i])DFS(G,i,flag);}//建立队列typedefstruct{int*elem;intfront,rear;}*Queue;//队列初始化voidInitQueue(QueueQ){Q-elem=(int*)malloc(20*sizeof(int));if(!Q-elem)exit(0);Q-front=Q-rear=0;第3小组实验报告10}//入队voidEnter(QueueQ,inte){if((Q-rear+1)%20!=Q-front)Q-elem[Q-rear]=e;elseprintf(队列满!\n);Q-rear=(Q-rear+1)%20;}//出队voidLeave(QueueQ,inte){if(Q-rear!=Q-front)e=Q-elem[Q-front];elseprintf(队列空!\n);Q-front=(Q-front+1)%20;}//广度优先遍历voidBFSTravel(GraphG){QueueQ;node*p;inti,j=0;intflag[20];//标志数组Q=malloc(sizeof(20));InitQueue(Q);for(i=0;iG-v;i++)flag[i]=0;for(i=0;iG-v;i++)if(flag[i]==0){flag[i]=1;printf(%2s,G-List[i].name);Enter(Q,i);第3小组实验报告11while(Q-front!=Q-rear){Leave(Q,j);//队头元素出队并置为jp=G-List[j].fnext;while(p!=NULL){if(flag[p-adj]==0){printf(%2s,G-List[p-adj].name);flag[p-adj]=1;Enter(Q,p-