【数据结构笔记20】图的定义，图的表示：邻接矩阵与邻接表

本次笔记内容：
6.1.1 什么是图 - 定义
6.1.2 什么是图 - 邻接矩阵表示法
6.1.3 什么是图 - 邻接表表示法

图的定义

线性表与树可看做图的特殊实例

图（Graph）表示“多对多”的关系：

• 线性表表示“一对一”的关系；
• 树表示“一对多”的关系。

图包含

• 一组定点：通常用V（Vertex）表示顶点集合；
• 一组边：通常用E（Edge）表示边的集合；
• • 边是顶点对：(v,w)∈E，其中v,w属于V；
• • 有向边<v,w>表示从v指向w的边（单行线）；
• 不考虑重边和自回路。

抽象数据类型定义

如上图，图的操作集很庞大，这里只提几个常用的。

常见术语

• 无向图与有向图；
• 带权重的路径：网络；
• 具体术语应用时再说。

在程序中表示图

邻接矩阵

如上图，邻接矩阵规律如下：

• 对角元全部设为0；
• 矩阵是对称的。

存储无向图，如何节省一半空间？

如上图，用一维数组只存下三角的元素。

邻接矩阵优点

• 直观简单；
• 方便检查任意一对顶点间是否存在边；
• 方便找任意顶点的所有“邻接点”（有边直接相连的顶点）；
• 方便计算任一顶点的“度”（从该点发出的边数为“出度”，指向该点的边数为“入度”）：
• • 无向图：对应行（或列）非0元素的个数；
• • 有向图：对应行非0元素的个数是“出度”；对应列非0元素的个数是“入度”。

临界矩阵缺点

• 浪费空间：存稀疏图（点很多而边很少）有大量无效元素；
• 浪费时间：统计稀疏图中一共有多少条边。

邻接表

邻接表的表示不唯一，因为每个链表中顺序不唯一。但是上图的方法中，并不很省空间，而且对于网络来说，结构中还要增加表示权重的域。

因此，一定要够稀疏才用邻接表。

邻接表特点

• 方便查找任一顶点的所有“邻接点”；
• 节省稀疏图的空间：
• • 邻接表需要N个头指针+2E个结点（每个结点至少2个域）；
• 方便计算任一顶点的“度”么？
• • 对于无向图：是的；
• • 对于有向图：只能计算“出度”，需要构造“逆邻接表”（存指向自己的边）来方便计算“入度”；
• 方便检查任意一对顶点间存在边么？
• • 不方便。

还有很多表示图的方法，应用取决于具体问题。