数据结构图实验报告

一、实验目的和要求（1）掌握图的相关概念，包括图，有向图，无向图，完全图，子图，连通图，度，入度，出度，简单回路和环等定义。（2）重点掌握图的各种存储结构，包括邻接矩阵和邻接表等。（3）重点掌握图的基本运算，包括创建图，输出图，深度优先遍历，广度优先遍历等。（4）掌握图的其他运算，包括最小生成树，最短路径，拓扑排序和关键路径等算法。（5）灵活运用图这种数据结构解决一些综合应用问题。二、实验内容和方法(1)实验内容：1、编写一个程序algo8-1.cpp，实现不带权图和带权图的邻接矩阵与邻接表的相互转换算法、输出邻接矩阵与邻接表的算法，并在此基础上设计一个程序exp8-1.cpp实现如下功能：①建立如图1所示的有向图G的邻接矩阵，并输出；②由有向图G的邻接矩阵产生邻接表，并输出；③再由②的邻接表产生对应的邻接矩阵，并输出。图12、编写一个程序algo8-2.cpp，实现图的遍历运算，并在此基础上设计一个程序exp8-2.cpp完成如下功能：①输出图1所示的有向图G从顶点0开始的深度优先遍历序列（递归算法）；②输出图1所示的有向图G从顶点0开始的深度优先遍历序列（非递归算法）；③输出图1所示的有向图G从顶点0开始的广度优先遍历序列。3、设计一个程序exp8-3.cpp,采用邻接表存储图，并输出图8.1（a）中从指定顶点1出发的所有深度优先遍历序列。1569758453015243(2)实验方法：1、综合运用课本所学的知识，用不同的算法实现在不同的程序功能。2、结合指导老师的指导，解决程序中的问题，正确解决实际中存在的异常情况，逐步改善功能。3、根据实验内容，编译程序。三、实验环境：Windows7，VisualC++6.0三、实验过程描述文件graph.h中定义了图的邻接矩阵表示类型和邻接表表示类型，该头文件在以下三个实验中都会使用到。其代码如下：#ifndefGRAPH_H_INCLUDED#defineGRAPH_H_INCLUDEDtypedefintInfoType;#defineMAXV100//最大顶点个数#defineINF32767//INF表示无限大//以下定义邻接矩阵类型typedefstruct{intno;InfoTypeinfo;}VertexType;typedefstruct{intedges[MAXV][MAXV];intn,e;VertexTypevexs[MAXV];}MGraph;//以下定义邻接表类型typedefstructANode{intadjvex;structANode*nextarc;InfoTypeinfo;}ArcNode;typedefintVertex;typedefstructVNode{Vertexdata;ArcNode*firstarc;}VNode;VertexTypevexs[MAXV];}MGraph;//以下定义邻接表类型typedefstructANode{intadjvex;structANode*nextarc;InfoTypeinfo;}ArcNode;typedefintVertex;typedefstructVNode{Vertexdata;ArcNode*firstarc;实验①源程序。一、输入如下所示程序；//文件名：exp8-1.cpp#includestdio.h#includemalloc.h#includegraph.hexternvoidMatToList1(MGraph,ALGraph*&);externvoidListToMat1(ALGraph*,MGraph&);externvoidDispMat1(MGraph);externvoidDispAdj1(ALGraph*);intmain(){inti,j;MGraphg,g1;ALGraph*G;intA[MAXV][6]={{0,5,INF,7,INF,INF},{INF,0,4,INF,INF,INF},{8,INF,0,INF,INF,9},{INF,INF,5,0,INF,6},{INF,INF,INF,5,0,INF},{3,INF,INF,INF,1,0}};g.n=6;g.e=10;for(i=0;ig.n;i++)for(j=0;jg.n;j++)g.edges[i][j]=A[i][j];printf(有向图G的邻接矩阵：\n);//文件名：algo8-1.cpp#includestdio.h#includemalloc.h#includegraph.h//不带权图的算法voidMatToList(MGraphg,ALGraph*&G){inti,j;ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;ig.n;i++)for(j=g.n-1;j=0;j--)if(g.edges[i][j]!=0){p=(ArcNode*)malloc(sizeof(ArcNode));p-adjvex=j;p-nextarc=G-adjlist[i].firstarc;G-adjlist[i].firstarc=p;}G-n=g.n;G-e=g.e;}voidListToMat(ALGraph*G,MGraph&g){inti,j;ArcNode*p;for(i=0;iG-n;i++)voidDispAdj1(ALGraph*G){inti;ArcNode*p;for(i=0;iG-n;i++){p=G-adjlist[i].firstarc;printf(%3d:,i);while(p!=NULL){printf(%3d(%d),p-adjvex,p-info);p=p-nextarc;}printf(\n);}}二、编译并链接程序；三、运行程序，结果如下图：实验○2源程序一、输入如下所示程序；//文件名：exp8-2.cpp#includestdio.h#includemalloc.h#includegraph.hexternvoidMatToList1(MGraph,ALGraph*&);externvoidDispAdj1(ALGraph*G);externvoidDFS(ALGraph*G,intv);externvoidDFS1(ALGraph*G,intv);externvoidDFS2(ALGraph*G,intv);externvoidBFS(ALGraph*G,intv);intmain(){inti,j;MGraphg;//文件名：algo8-2.cpp#includestdio.h#includemalloc.h#includegraph.hintvisited[MAXV];voidDFS(ALGraph*G,intv)//递归深度优先遍历{ArcNode*p;visited[v]=1;printf(%3d,v);p=G-adjlist[v].firstarc;while(p!=NULL){if(visited[p-adjvex]==0)DFS(G,p-adjvex);top++;St[top]=G-adjlist[w].firstarc;break;}p=p-nextarc;}}printf(\n);}voidBFS(ALGraph*G,intv){ArcNode*p;intqueue[MAXV],front=0,rear=0;intvisited[MAXV];intw,i;for(i=0;iG-n;i++)voidMatToList1(MGraphg,ALGraph*&G){inti,j;ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;ig.n;i++)G-adjlist[i].firstarc=NULL;for(i=0;ig.n;i++)for(j=g.n-1;j=0;j--)if(g.edges[i][j]!=0&&g.edges[i][j]!=INF){p=(ArcNode*)malloc(sizeof(ArcNode));p-adjvex=j;p-info=g.edges[i][j];p-nextarc=G-adjlist[i].firstarc;G-adjlist[i].firstarc=p;}二、对程序进行编译链接；三、运行该程序，结果如图实验③源程序。一、输入如下所示程序；#includestdio.h#includemalloc.h#includegraph.hexternvoidMatToList(MGraph,ALGraph*&);externvoidDispAdj(ALGraph*);intvisited[MAXV];voidDFSALL(ALGraph*G,intv,intpath[],intd){ArcNode*p;visited[v]=1;path[d]=v;d++;if(d==G-n){for(intk=0;kd;k++)printf(%2d,path[k]);printf(\n);}p=G-adjlist[v].firstarc;while(p!=NULL){if(visited[p-adjvex]==0)DFSALL(G,p-adjvex,path,d);p=p-nextarc;}visited[v]=0;}intmain()if(visited[p-adjvex]==0)DFSALL(G,p-adjvex,path,d);p=p-nextarc;}visited[v]=0;}p=(ArcNode*)malloc(sizeof(ArcNode));p-adjvex=j;p-nextarc=G-adjlist[i].firstarc;G-adjlist[i].firstarc=p;}G-n=g.n;G-e=g.e;二、对程序进行编译链接；三、运行该程序，结果如图