引入
学了那么多图的知识，是时候动手设计一下图的存储结构了，图跟线性表、树有那么大得差别，所以图的数据结构要复杂很多。
思考
我们先回忆一下线性表和树得存储结构
- 线性表：一对一的关系，用数组和链表就能很好的表示。
- 树：一对多得关系，用数组和链表得特性结合在一起就可以很好的表示。
那么图呢？
- 图上的任意一个顶点都可以是第一个顶点，谁开始都行。
- 任意一个顶点的邻接点也不存在次序关系，多对多，大家都一样。
我们观察下面的四张图
这四张图形态各异，但是
- 各个结点的邻接点都相同
- 边也都相同
- 所以位置虽然不一样，但其实
都是一张图。
那么该如何将图在内存中表示呢？
- 既然任意两个顶点都可能存在联系
- 我们不能线性的表达数据元素之间得关系
- 因为内存的物理位置也是线性的，而图的元素关系是平面的。
- 既然线性关系不行，那用多重链表呢？可以！
- 但会造成巨大的资源浪费，各个顶点得度数如果相差很大，就会造成很大的浪费。
解决
想明白上面得问题，我们就来回答这个问题
- 图是由顶点和边两部分组成的，合在一起表示困难，我们分开表示就好了
- 顶点：因为不分大小、主次，用一个简单的一维数组来存储就好
- 边、弧：其实就是顶点和顶点之间得关系，一个二维数组来存储就好
- 所以，我们使用
邻接矩阵方案，撒花！
无向图的邻接矩阵
图的邻接矩阵（Adjacency Matrix）：存储方式是用两个数组来表示图。
- 一个一维数组存储图中得顶点信息
- 一个二维数组（邻接矩阵）存储图中边、弧的信息
我们试着来存放上面这个无向图，首先设计一个一维数组 vexs 存放顶点信息
| vexs0 | vexs1 | vexs2 | vexs3 |
|---|---|---|---|
| V0 | V1 | V2 | V3 |
接着设计一个邻接矩阵（二维数组）arcs，存放边和边得信息
| V0 | V1 | v2 | v3 | |
|---|---|---|---|---|
| V0 | 0 | 1 | 1 | 1 |
| V1 | 1 | 0 | 1 | 0 |
| V2 | 1 | 1 | 0 | 1 |
| V3 | 1 | 0 | 1 | 0 |
因为是无向图，所以
- 无论是先行再列看（V0，V1）还是 先列再行看（V1，V0）都可以
- 邻接矩阵存储得是边、弧，如果存在就写1，反之则写0
- 这个邻接矩阵也是一个对称矩阵，因为这是一个无向图。
无向图邻接矩阵的存储结构
我们设计这个存储结构时
- 设计两个数组
- 顶点数组vertex[4]
- 边数组 arc[4][4] 为对称矩阵
- 边数组中，0表示顶点间不存在边，1表示顶点间存在边
所谓对称矩阵，就是
- N 阶矩阵的元满足
- a[i][j]=a[j]i
- 也就是从矩阵的左上角到右下角为轴
- 右上角得元与左下角相对应得元全都是相等的
有了这个数据结构，我们就可以很轻松的知道
- 任意两个顶点之间是否存在边，0就是没边，1就是有边
- 某个顶点的度，就是顶点 Vi 在邻接矩阵中第 i 行或 i 列的元素的和。
- 还记得无向图顶点的度嘛？就是该顶点邻接的边的个数
- 就是这一列或这一行，有多少个 1，加起来就是这个 Vi 的度
- 最后一个就是求 Vi 顶点的所有邻接点
- 就是将第 i 行元素扫描一遍，只要 arc[ i ][ j ]为1就是邻接点
| V0 | V1 | v2 | v3 | |
|---|---|---|---|---|
| V0 | 0 | 1 | 1 | 1 |
| V1 | 1 | 0 | 1 | 0 |
| V2 | 1 | 1 | 0 | 1 |
| V3 | 1 | 0 | 1 | 0 |
V1 的度是2，因为无论行、列，为1的元素加起来，都是2
V1 的邻接点是 V0、V2，因为 V1 行只有 V0、V2 的元素为1
我们看看图对不对，没有问题！
有向图的邻接矩阵
我们在无向图中发现，邻接矩阵竟然是对称的，原因也很简单
- 因为无论是顶点 A 到顶点 B 还是顶点 B 到顶点 A 都是相同的
- 那么在有向图中，给顶点规定了方向之后，会不会好一些呢？
有向图最重要的一点就是区分方向，我们按照上面的思路，首先设计一个一维数组 vexs 存放顶点信息
| vexs0 | vexs1 | vexs2 | vexs3 |
|---|---|---|---|
| V0 | V1 | V2 | V3 |
接着设计一个邻接矩阵（二维数组）arcs，存放边和边得信息
| V0 | V1 | v2 | v3 | |
|---|---|---|---|---|
| V0 | 0 | 0 | 0 | 1 |
| V1 | 1 | 0 | 1 | 0 |
| V2 | 1 | 1 | 0 | 0 |
| V3 | 0 | 0 | 0 | 0 |
因为我们要注意方向
- 所以行为弧为、列为弧头
- 如果不规定，那么 A->B 和 B->A 就一样了
- 这就不是有向图了
有向图邻接矩阵的存储结构
我们设计这个存储结构时
- 设计两个数组
- 顶点数组vertex[4]
- 边数组 arc[4][4] ，有向图矩阵并不对称
- 边数组中，0表示顶点间不存在边，1表示顶点间存在边
有向图有入度和出度的概念，所以
- 顶点 V1 的入度为1，正好是第 V1列的各数之和
- 顶点 V1 的出度为2，正好是第 V2行的各数之和
- 我们看看下表
| V0 | V1 | v2 | v3 | |
|---|---|---|---|---|
| V0 | 0 | 0 | 0 | 1 |
| V1 | 1 | 0 | 1 | 0 |
| V2 | 1 | 1 | 0 | 0 |
| V3 | 0 | 0 | 0 | 0 |
V1 的入度是1，出度是2
- V1列所有元素的和为1
- V1行所有元素的和为2
- 我们看下图验证一下
没有问题，我们接下来实际设计一下数据结构。
邻接矩阵（网）
我们在上一节，说到了网这个概念，实际上就是每条边上带有权的图，就是网。
- 网跟上面的思路一样，使用两个数组搞定
- 在数组中的元素就不在是0和1了
- 因为每条边有权，所以我们就将每条边的权值赋值到二维数组中
网最重要的一点就是看好权值，我们按照上面的思路，首先设计一个一维数组 vexs 存放顶点信息
| vexs0 | vexs1 | vexs2 | vexs3 |
|---|---|---|---|
| V0 | V1 | V2 | V3 |
接着设计一个邻接矩阵（二维数组）arcs，存放边和边得信息
| V0 | V1 | v2 | v3 | |
|---|---|---|---|---|
| V0 | $\infty$ | $\infty$ | $\infty$ | 18 |
| V1 | 8 | $\infty$ | 2 | $\infty$ |
| V2 | 4 | $\infty$ | $\infty$ | $\infty$ |
| V3 | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
这里有三种情况
- 如果有弧，则将权值写入
- 如果指向自己，那就写$\infty$
- 如果没有弧，那就写入$\infty$
- $\infty$ 表示计算机允许的，一个大于所有权值的值。
代码实现
1 | typedef enum { DG, UDG } GraphType; //声明图的类型，有向还是无向 |
好了，理解了上述概念，我们下节课来讲，如何创建一个图。
尾巴
这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。
