72_图的存储结构（上）

关键词：邻接矩阵法的设计与实现

0. 基本思想

• 用一维数组存储顶点：描述顶点相关的数据
• 用二维数组存储边：描述顶点间的关系和权

1. 邻接矩阵法

设图A = (V, E)是一个有n个顶点的图， 图的邻接矩阵为Edge[n][n]，则：

注意：

• 解决工程问题时，习惯于对图中的每个顶点进行编号
• 当不需要权值时，取W为非空表示结点间有连接

2. 设计与实现

邻接矩阵法的继承关系图

问题：如何具体表示顶点集数组？如何具体表示边集数组？

实现方式一：直接使用数组表示顶点集和边集

问题：

• 构造效率低下：图对象初始化时，频繁调用顶点类型和边类型的构造函数
• 空间使用率低下：图对象占用大量空间，而大多数空间处于闲置状态
• 无法表示空值：无法用统一的方式表示边为空的情形

实现方式二：使用指针数组表示顶点集和边集

问题的解决：

• 构造效率：初始化图像时，只需要将数组元素赋值为空
• 空间使用率：顶点数据元素和边数据元素在需要时动态创建
• 空值的表示：任意的顶点类型和边类型都是用NULL表示空值

MatrixGraph.h

3. 小结

• 邻接矩阵法使用数组对图相关的数据进行存储
• 一维数组存储顶点相关的数据（空表示无相关数据）
• 二维数组存储边相关的数据（空表示顶点间无数据）
• 代码实现时使用指针数组进行数据的存储（提高效率）

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4