深入浅出数据结构（图）

图

图的逻辑结构
- 定义
- 逻辑结构
- - 基本术语（提起来脑海有印象就行）
  - 对比
存储结构（邻接矩阵和邻接表）
- 铺垫
邻接矩阵
- 透过问题看本质
- - 无向图相关
  - 有向图相关
  - 网图相关
- 伪代码实现
- - 类（无向图）
  - 构造函数（伪代码）
邻接表
- 如何实现
- 图示
- 透过问题看本质（对照上图）
- - 网图相关
- 伪代码实现
- - 类（无向图）
  - 构造函数

图的逻辑结构

定义

在这里插入图片描述

逻辑结构

在这里插入图片描述

基本术语（提起来脑海有印象就行）

我觉得在图这一章中邻接和依附是很重要的概念为什么这么说？因为这是我们描述图中顶点之间联系的关键，回想起之前我们所学习的数组链表，我们都可以用前驱和后继来描述节点之间的关系，在树那一章中，我们也可以用双亲或者孩子来描述，所以这就是我为什么说这个概念比较关键
在这里插入图片描述
说白了啥意思？举个例子，在上面的无向图中，拿V0来举例，V0和V1互为邻接点，同时边V0V1依附于顶点V0和顶点V1（没他俩这条边就活不了了）这也是后面理解邻接矩阵和邻接表的基础

有向图类似（单相思）

对比

在这里插入图片描述

存储结构（邻接矩阵和邻接表）

铺垫

在前面我们学习链表队列的时候，我们通常在讨论他的存储方式的时候会分为链式存储和顺序存储，而且他们各有优劣，这里也是很类似的换汤不换药，不需要觉得他是一个很难的东西

邻接矩阵

经过前面的铺垫我们自然而然的就会产生疑问：
在这里插入图片描述

如何存储顶点？
是不是搞一个数组来把顶点一存就解决了

如何存储边？（难点）
因为我们需要表示顶点之间的关系，所以我们不能简单的用一维数组，我们可以想到用一个二维数组来存储，怎么弄？
我们以前都数学学过99乘法表对吧，比如我们需要知道3乘3为多少，那么我们只需要找到第三行第三列对吧，这里其实是一样的道理，我们想要知道V0到V1是不是有路径的，我们只需要找到第V0行第V1列，这里我们只需要设置一个flag，把有路的设置为1，没路的设置为0，这样不就行了吗，如下图

透过问题看本质

理解之后，我们所构建的矩阵就是我们这章的重点《邻接矩阵》

无向图相关

Q1思考以上的问题：
学过线性代数的应该一眼就能看出来，这不是一个关于主对角线是对称的矩阵吗
想想为啥啊？
很简单这因为咱们这是无向图吧！也就是说顶点之间都是情投意合的吧，你能来我家玩，我也能去你家玩
Q2:
那么我们如果需要求一个顶点的度就很好求了吧，就是看他能到谁家玩呗
反映到我们所构建的邻接矩阵上就是第i行或者第i列非零元素之和呗
在这里插入图片描述
Q3:
这不就是我们构建这个邻接矩阵的依据吗我就不过多赘述了

Q4：

在这里插入图片描述

有向图相关

P1：（有向图相关）
在这里插入图片描述
P2：

那么出度不就是第i列元素之和吗
P3:（对照上图）

网图相关

下图是一个网图，也就是含有权值的图，我们把之前有向图或者无向图的1变为了权值以此来表达某两个顶点是连通的，有些人看到这里可能会有疑惑：
为什么没有边的两个顶点之间要填上无穷的符号呢？
这时候我们就需要回顾权的概念，所谓权指的是网图中，某一点到达另一个顶点所需要花费的代价，这是非常关键的，例如下图中V1和V3之间没有边，那就代表着V1不论花费多大的代价都到不了V3，所以这里只能填上无穷而不是0！！！
在这里插入图片描述

伪代码实现

类（无向图）

在这里插入图片描述

构造函数（伪代码）

在这里插入图片描述

由于考虑到函数的复用性，最好再额外定义一个输入函数

邻接表

突然给你一个邻接表的定义，你可能会不知所措，但是我先告诉你，这个东西跟链式存储90%相似，为什么这么说，你想当给你一个稀疏图（边很少的图），你如果用邻接矩阵是不是还是得构建一个n×n大小的，虽然矩阵里面0肯定很多，但你不得不这么做，为了解决这个问题我们就引入了邻接表
类比于解决数组浪费空间的问题类比于解决稀疏多项式的问题类比于解决斜树的问题又或是平衡二叉树的问题其实我的理解都可以把这些看作是一种adjustment 希望大家能够理解