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

数据结构试验报告实验四图的存储及应用实验题目：图的遍历问题1

第3小组实验报告实验报告实验类型__综合设计__实验室_软件实验室三__一、实验题目图的存储及应用二、实验目的和要求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];2

第3小组实验报告intn,e;}ALGraph;四、概要设计为了实现上述程序功能，代码如下：#include<stdio.h>#include<stdlib.h>#include<string.h>typedefstructnode{//边表结点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));请输入图的顶点数和边数(空格隔开)：读入顶点数和边数for(i=0;i<G->v;i++){请输入图中第%d元素：读入顶点信息3

第3小组实验报告G->List[i].fnext=NULL;//边表置为空表}for(k=0;k<G->e;k++){请请输入第%d条边的两顶点序号(空格隔开)：读入边（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));请输入图的顶点数和边数【空格隔开】：for(i=0;i<G->v;i++){请输入图中第%d元素：读入顶点信息G->List[i].fnext=NULL;}for(k=0;k<G->e;k++){请请输入第%d边的两顶点序号【空格隔开】：4

第3小组实验报告q=(node*)malloc(sizeof(node));//生成新边表结点sq->adj=j;//邻接点序号为jq->next=G->List[i].fnext;G->List[i].fnext=q;}returnG;}//输出图的邻接表voidPrint(GraphG){inti;node*p;邻接表for(i=0;i<G->v;i++){p=G->List[i].fnext;while(p){p=p->next;}}}typedefstruct{charvex[20];}Lists[20];typedefstruct{Listsl;intedge[20][20];//邻接矩阵intv1,e1;//顶点数和弧数}AGraph;typedefstruct{5

第3小组实验报告intdata;/*某顶点与已构造好的部分生成树的顶点之间权值最小的顶点*/intlowcost;/*某顶点与已构造好的部分生成树的顶点之间的最小权值*/}ClosEdge[20];/*用普里姆算法求最小生成树时的辅助数组*/voidCreateAN(AGraph*G1){/*构造邻接矩阵结构的图G*/inti,j,k,w;请输入图的顶点数和边数（空格隔开）：读入顶点数和边数for(i=1;i<=G1->v1;i++){请输入图%d号元素：读入顶点信息}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++){请输入两顶点及边的权值（空格隔开）：G1->edge[i][j]=w;G1->edge[j][i]=w;}}voidPrintAN(AGraph*G1){inti,j;邻接矩阵for(i=1;i<=G1->v1;i++){for(j=1;j<=G1->v1;j++)}}//输出各顶点的度数6

第3小组实验报告voidDu(GraphG){inti,j;node*p;各点度数for(i=0;i<G->v;i++){p=G->List[i].fnext;顶点%2s的度为：j=0;while(p){j++;p=p->next;}}}//栈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;//将栈顶元素摘下7

第3小组实验报告free(p);//释放栈顶空间returnj;}//拓扑排序voidTopo(GraphG,stack*s){inti,k,count;intj=0;intindegree[20]={0};node*p;for(i=0;i<G->v;i++){p=G->List[i].fnext;;while(p!=NULL){indegree[p->adj]++;p=p->next;}}for(i=0;i<G->v;i++)if(indegree[i]==0)push(s,i);count=0;while(s->next!=NULL){i=pop(s,j);++count;for(p=G->List[i].fnext;p!=NULL;p=p->next){k=p->adj;if(!(--indegree[k]))push(s,k);}}有回路}8

第3小组实验报告voidDFS(GraphG,inti,intflag[]){node*p;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;i<G->v;i++)flag[i]=0;for(i=0;i<G->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;9

第3小组实验报告}//入队voidEnter(QueueQ,inte){if((Q->rear+1)%20!=Q->front)Q->elem[Q->rear]=e;else队列满Q->rear=(Q->rear+1)%20;}//出队voidLeave(QueueQ,inte){if(Q->rear!=Q->front)e=Q->elem[Q->front];else队列空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;i<G->v;i++)flag[i]=0;for(i=0;i<G->v;i++)if(flag[i]==0){flag[i]=1;Enter(Q,i);10

第3小组实验报告while(Q->front!=Q->rear){Leave(Q,j);//队头元素出队并置为jp=G->List[j].fnext;while(p!=NULL){if(flag[p->adj]==0){flag[p->adj]=1;Enter(Q,p->adj);}p=p->next;}}}}intminimum(ClosEdgecl,intvnum){inti;intw,p;w=1000;for(i=1;i<=vnum;i++)if(cl[i].lowcost!=0&&cl[i].lowcost<w){w=cl[i].lowcost;p=i;}returnp;}voidPrim(AGraph*G1,intu){ClosEdgeclosedge;inti,j,k;for(j=1;j<=G1->v1;j++)/*辅助数组初始化*/if(j!=u){closedge[j].data=u;closedge[j].lowcost=G1->edge[u][j];}11

第3小组实验报告closedge[u].lowcost=0;/*初始，U={u}*/for(i=1;i<G1->v1;i++){k=minimum(closedge,G1->v1);/*求出生成树的下一个顶点*/输出生成树的边*/closedge[k].lowcost=0;/*第k顶点并入U集*/for(j=1;j<=G1->v1;j++)/*新顶点并入U后，修改辅助数组*/if(G1->edge[k][j]<closedge[j].lowcost){closedge[j].data=k;closedge[j].lowcost=G1->edge[k][j];}}}//菜单列表voidmenu(){图的遍历问题建立无向邻接图建立有向邻接图建立无向邻接矩阵输出各顶点的度拓扑排序深度优先遍历广度优先遍历算法生成最小生成树退出}//主函数voidmain(){GraphG;AGraphG1;intchoice,u;stack*s=(stack*)malloc(sizeof(stack));12

第3小组实验报告