72_图的存储结构（上）
2018-07-29 本文已影响6人
编程半岛
关键词：邻接矩阵法的设计与实现
0. 基本思想
- 用一维数组存储顶点：描述顶点相关的数据
- 用二维数组存储边：描述顶点间的关系和权
1. 邻接矩阵法
设图A = (V, E)是一个有n个顶点的图， 图的邻接矩阵为Edge[n][n]，则：
注意：
- 解决工程问题时，习惯于对图中的每个顶点进行编号
- 当不需要权值时，取W为非空表示结点间有连接
2. 设计与实现
邻接矩阵法的继承关系图
问题：如何具体表示顶点集数组？如何具体表示边集数组？
实现方式一：直接使用数组表示顶点集和边集
问题：
- 构造效率低下：图对象初始化时，频繁调用顶点类型和边类型的构造函数
- 空间使用率低下：图对象占用大量空间，而大多数空间处于闲置状态
- 无法表示空值：无法用统一的方式表示边为空的情形
实现方式二：使用指针数组表示顶点集和边集
问题的解决：
- 构造效率：初始化图像时，只需要将数组元素赋值为空
- 空间使用率：顶点数据元素和边数据元素在需要时动态创建
- 空值的表示：任意的顶点类型和边类型都是用NULL表示空值
3. 小结
- 邻接矩阵法使用数组对图相关的数据进行存储
- 一维数组存储顶点相关的数据（空表示无相关数据）
- 二维数组存储边相关的数据（空表示顶点间无数据）
- 代码实现时使用指针数组进行数据的存储（提高效率）
声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4
