文档库

最新最全的文档下载
当前位置:文档库 > 数据结构图实验报告

数据结构图实验报告

一、实验目的和要求

(1)掌握图的相关概念,包括图,有向图,无向图,完全图,子图,连通图,度,入度,出度,简单回路和环等定义。

(2)重点掌握图的各种存储结构,包括邻接矩阵和邻接表等。

(3)重点掌握图的基本运算,包括创建图,输出图,深度优先遍历,广度优先遍历等。 (4)掌握图的其他运算 ,包括最小生成树,最短路径,拓扑排序和关键路径等算法。 (5)灵活运用图这种数据结构解决一些综合应用问题。

二、实验内容和方法

(1)实验内容:

1、编写一个程序algo8-1.cpp ,实现不带权图和带权图的邻接矩阵与邻接表的相互转换算法、输出邻接矩阵与邻接表的算法,并在此基础上设计一个程序exp8-1.cpp 实现如下功能:

①建立如图1所示的有向图G 的邻接矩阵,并输出; ②由有向图G 的邻接矩阵产生邻接表,并输出; ③再由②的邻接表产生对应的邻接矩阵,并输出。

图1

2、编写一个程序algo8-2.cpp ,实现图的遍历运算,并在此基础上设计一个程序exp8-2.cpp 完成如下功能:

①输出图1所示的有向图G 从顶点0开始的深度优先遍历序列(递归算法); ②输出图1所示的有向图G 从顶点0开始的深度优先遍历序列(非递归算法); ③输出图1所示的有向图G 从顶点0开始的广度优先遍历序列。

3、设计一个程序exp8-3.cpp,采用邻接表存储图,并输出图8.1(a )中从指定顶点1出发的所有深度优先遍历序列。

1

5

6 9

7

5

8

4

5

3

0 1 5

2 4

3