江苏开放大学实验报告

学 号:

姓 名:

课程代码: 060220

课程名称:

数据结构与算法

评阅教师:

许小媛

实验名称：图的应用

一、实验目的及要求

1. 熟练掌握图的邻接矩阵和邻接表的存储方式；

2. 实现图的一些基本运算，特别是深度遍历和广度遍历；

3. 掌握以图为基础的一些常用算法，如最小生成树、拓扑排序、最短路径等。

二、实验内容

1

、

图

G

＝

(V

，

E)

，

其

中

V={1,2,3,4,5,6}

，

Ｅ

＝

{<1,2>,<1,3>,<1,4>,<2,5>,<3,2>,<3,5>,<3,6>,<4,6>,<5,6>}，请画出图 G，并写出其邻接矩阵和邻接

表表示。

2、已知一个无向图的邻接表如下图所示，要求：

（1）画出该无向图；

（2）根据邻接表，分别写出用 DFS(深度优先搜索)和 BFS（广度优先搜索）算法从顶点 V0 开始遍历该

图后所得到的遍历序列。

1

三、实验设备及环境

安装 C 语言编译环境。

四、实验步骤（功能实现的核心代码及说明，包括数据库表）

1

、

图

G

＝

(V

，

E)

，

其

中

V={1,2,3,4,5,6}

，

Ｅ

＝

{<1,2>,<1,3>,<1,4>,<2,5>,<3,2>,<3,5>,<3,6>,<4,6>,<5,6>}，请画出图 G，并写出其邻接矩阵和邻接

表表示。

2、已知一个无向图的邻接表如下图所示，要求：

（1）画出该无向图；

2

（2）根据邻接表，分别写出用 DFS(深度优先搜索)和 BFS（广度优先搜索）算法从顶点 V0 开始遍历该

图后所得到的遍历序列。

3