深入浅出数据结构（图）
图
- 图的逻辑结构
- 定义
- 逻辑结构
- 基本术语（提起来脑海有印象就行）
- 对比
- 存储结构（邻接矩阵和邻接表）
- 铺垫
- 邻接矩阵
- 透过问题看本质
- 无向图相关
- 有向图相关
- 网图相关
- 伪代码实现
- 类（无向图）
- 构造函数（伪代码）
- 邻接表
- 如何实现
- 图示
- 透过问题看本质（对照上图）
- 网图相关
- 伪代码实现
- 类（无向图）
- 构造函数
图的逻辑结构
定义
逻辑结构
基本术语（提起来脑海有印象就行）
我觉得在图这一章中邻接和依附是很重要的概念 为什么这么说？因为这是我们描述图中顶点之间联系的关键，回想起之前我们所学习的数组链表，我们都可以用前驱和后继来描述节点之间的关系，在树那一章中，我们也可以用双亲或者孩子来描述，所以这就是我为什么说这个概念比较关键
说白了啥意思？举个例子，在上面的无向图中，拿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 希望大家能够理解
如何实现
具体的来说还是回到起初的两个问题
1.怎么存顶点
2.怎么存边
图示
透过问题看本质（对照上图）
)
网图相关
无非就是增加了一个数据域来存储权值吧
伪代码实现
类（无向图）
构造函数
**预告：
大概明天一下图的深度和广度优先遍历 应该能更完，可以先三连一下 那祝愿看到这里的你有美好的一天
******************************************************************************signed by 曦月逸霜