数据结构图实验报告

《数据结构图实验报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一、实验目的和要求（1）掌握图的相关概念，包括图，有向图，无向图，完全图，子图，连通图，度，入度，出度，简单回路和环等定义。（2）重点掌握图的各种存储结构，包括邻接矩阵和邻接表等。（3）重点掌握图的基本运算，包括创建图，输出图，深度优先遍历，广度优先遍历等。（4）掌握阁的其他运算，包括最小生成树，最短路径，拓扑排序和关键路径等算法。（5）灵活运用图这种数据结构解决一些综合应用问二、iS容i「务运（1）实验内容：1、编写一个程序alg08-l.Cpp，实现不带权图和带权图的邻接矩阵与邻接表的相互转换算法、输出邻接矩阵与邻接表的

2、算法，并在此基础上设计一个程序exp8-l.cPP实现如下功①建立如图1所示的有向图G的邻接矩阵，并输出;②由有向图G的邻接矩阵产生邻接表，并输出；③再由②的邻接表产生对应的邻接矩阵，并输出。2、编写一个程序algo8-2.cpp,实现图的遍历运算,并在此基础上设计一个程序exp8-2.cpp：完成如下功能：:①输出图1所示的有向图G从顶点0开始的深度优先遍历序列（递归算法）；I②输出图1所示的有向图G从顶点0开始的深度优先遍历序列（非递归算法）；

3、③输出图1所示的有向图G从顶点0开始的广度优先遍历序列。

4、3、设计一个程序e

5、xp8-3.cpp,采用邻接表存储图，并输出图8.1（a）中从指定顶点1出发的所有深度优先遍历序列。(2)实验方法：1、综合运用课本所学的知识，用不同的算法实现在不同的程序功能。2、结合指导老师的指导，解决程序中的问题，正确解决实际中存在的异常情况，逐步改善功能。3、根据实验内容，编译程序。三、实验环:Windows7,VisualC++6.0三、实验过程描述文件graph,h中定义了图的邻接矩阵表示类型和邻接表表示类型，该头文件在以丁三个实验中都会使用到。其代码如下：#ifndefGRAPH_H_INCLUDED#defi

6、neGRAPH_H_INCLUDEDtypedefintInfoType;#defineMAXV100//最大顶点个数#defineINF32767//INF表示无限大//以下足义邻接矩阵类型typedefstruct{intno;InfoTypeinfo;JVertexType;typedefstruct{intedgesfMAXVKMAXV];intn，e;VertexTypevexs[MAXV];}MGraph;//以下定义邻接表类型typedefstructANode{intadjvex;structANode*ne

7、xtarc;InfoTypeinfo;[ArcNode;typedefintVertex;typedefstructVNodeVertexdata;实验①源程序。一、输入如下所示程序；//文件名:exp8-1.cpp^include#include#include"graph.h"externvoidMatToListl(MGraph,ALGraph*&);externvoidListToMat1(ALGraph*,MGraph&);externvoidDispMat1(MGraph);

8、externvoidDispAdj1(ALGraph*);intmain(){inti,j;MGraphg，gl;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}};gn=6;g.e=10;for(i=0;i

9、[j]=A[i]

10、j];printf("有向图G的邻接矩阵：");//文件名:algo8-l.cpp#include#include#include"graph.h"//不带权图的算法voidMatToList(MGraphg,ALGraph*&G){inti，j;ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;i=O;j-)if(g.edges[ilfj]!=O){p=(Arc

11、Node*)malloc(sizeof(ArcNode));p->adjvex=j;p->nextarc=G-〉adjlist[il.firstarc;G-〉adjlistni.firstarc=p;}G-〉n=g.n;G-〉e=g.e;“voidListToMat(ALGraph*G,M