# 图
- Graph 学习参考
- 163 网易公开课 - 数据结构
一些顶点的集合，顶点通过一系列的边连接。边可以有权重（weight），例如 A 市到 B 市距离多远，C 市到 B 市距离多远。
- 边也可以是有向和无向的。
- 单向图，无论从什么顶点出发，最终无法回到原顶点。
术语：
- 出度： 节点指向相连的节点
- 入度： 其他节点指向本节点
效率：
| 操作 | 邻接列表 | 邻接矩阵 |
|---|---|---|
| 存储空间 | O(V + E) | O(V^2) |
| 添加顶点 | O(1) | O(V^2) |
| 添加边 | O(1) | O(1) |
| 检查相邻性 | O(V) | O(1) |
# 图的数据结构表示方法：
# 邻接矩阵
通过数组矩阵的方式进行存储，G[N][N] N 个顶点从 0 到 N-1 编号，两个顶点有边相连则用 1 或者这条边的权值表示。
对于无向图（无方向）来说，由于节点之间具有对称性，所以只需存储一半的数据即可。
用一个长度为 N(N+1)/2 的 1 维数组。
查找 Gij 在一个邻接矩阵中对应的下标就是 (i*(i+1)/2 + j)
对于有向图（有方向）需要存储所有节点的数据。
优点：
- 简单直观好理解
- 方便检查任意一对顶点间是否存在边
- 方便查找任意一顶点的所有邻接点（直接相连的顶点）
- 方便计算任意顶点的度
缺点：
- 浪费空间，存储稀疏图时候是有大量无效的元素。（点多边少）
# 邻接表
用数组存储每一个点，每个对应的点则用链表存储，链表指向相连的节点
优点：
- 方便查找任意点的所有邻接点（相连接的点）
- 节约稀疏图的空间
- 需要 N 个头指针 + 2E 个节点（每个节点至少 2 个域）
- 无向图方便计算任一顶点的度
- 有向图只能计算出度，需要构建一个逆向邻接表（每个点链表的节点都是其他节点指向它的）
缺点：
- 无法快速计算任意两个节点之间是否相连