一、图
图（Graph）由顶点（vertex）和边（edge）组成，通常表示为G = (V, E)。G表示一个图，V是顶点集（有穷且非空），E是边集（可以是空的）。任意两个顶点之间都可以用边来表示它们之间的关系。
图结构的应用极其广泛。例如，社交网络、地图导航、游戏开发等。
1.1. 有向图
有向图（Directed Graph）的边是有明确方向的。
如果一个有向图，从任意顶点出发无法经过若干条边回到该顶点，那么它就是一个有向无环图（Directed Acyclic Graph，简称DAG)。
注意上面两个图的区别：2 -> 5（无环），5 -> 2（有环）。
1.1.1. 出度（Out-degree）
一个顶点的出度为x，是指有x条边以该顶点为起点（如下图，顶点11的出度是3）。
1.1.2. 入度（In-degree）
一个顶点的入度为x，是指有x条边以该顶点为终点（如下图，顶点11的入度是2）。
出度、入度适用于有向图。
1.2. 无向图
无向图（Undirected Graph）的边是无方向的。
因为是无方向的，所以效果类似于下面的有向图：
1.3. 混合图
混合图（Mixed Graph）的边可能是无向的，也可能是有向的。
1.4. 简单图、多重图
1.4.1. 平行边
在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边（如下图，a、b、c是平行边、e、f是平行边）。
在有向图中，关联一对顶点的有向边如果多于1条，并且它们的的方向相同，则称这些边为平行边（如下图，a、b是平行边、e、f是平行边）。
1.4.2. 多重图（Multigraph）
有平行边或者有自环的图（如下图，红色是平行边，蓝色是自环边）。
1.4.3. 简单图（Simple Graph）
既没有平行边也不没有自环的图（图的相关章节中讨论的基本都是简单图，实际开发中遇到的大部分也是简单图）。
1.5. 无向完全图
无向完全图（Undirected Complete Graph）的任意两个顶点之间都存在边。
如下图，有5个顶点：
- 顶点1连接顶点2、3、4、5（需要
5 - 1 = 4条边） - 顶点2连接顶点3、4、5（需要
5 - 2 = 3条边） - 顶点3连接顶点4、5（需要
5 - 3 = 2条边） - 顶点4连接顶点5（需要
5 - 4 = 1条边） - 共有：
(5 - 1) + (5 - 2) + (5 - 3) + (5 - 4) = 10条边
由上可得出，n个顶点的无向完全图有n(n − 1)/2条边（n−1 + n−2 + n−3 +⋯+3+2+1 = n(n − 1)/2）。
1.6. 有向完全图
有向完全图（Directed Complete Graph）的任意两个顶点之间都存在方向相反的两条边。
n个顶点的有向完全图有n(n − 1)条边（因为顶点之间有2条边，所以是无向完全图边数的2倍）。
稠密图（Dense Graph）：边数接近于或等于完全图。
稀疏图（Sparse Graph）：边数远远少于完全图。
1.7. 有权图
有权图（Weighted Graph）的边可以拥有权值（Weight）。
权值可以是整数、小数、自定义对象。
1.8. 连通图
如果顶点x和y之间存在可相互抵达的路径（直接或间接的路径），则称x和y是连通的。
如果无向图G中任意2个顶点都是连通的，则称G为连通图（Connected Graph）。
1.8.1. 连通分量
连通分量（Connected Component）：无向图的极大连通子图。
连通图只有一个连通分量，即其自身。非连通的无向图有多个连通分量（只要有多个连通分量，必然不是连通图）。
下面的无向图有3个连通分量：
1.9. 强连通图
如果有向图G中任意2个顶点都是连通的，则称G为强连通图（Strongly Connected Graph）。
1.9.1 强连通分量
强连通分量（Strongly Connected Component）：有向图的极大强连通子图。
强连通图只有一个强连通分量，即其自身。非强连通的有向图有多个强连通分量。
如下图，不是一个强连通图，有3个强连通分量：
二、图的实现方案
图有2种常见的实现方案：
- 邻接矩阵（Adjacency Matrix）
- 邻接表（Adjacency List）
2.1. 邻接矩阵
邻接矩阵的存储方式：
- 一维数组存放顶点信息
- 二维数组存放边信息
如下图，是一个无向图，边数组存储的数据是对角线对称的（只需要存储一次就可以了，有点浪费内存）：
如下图，是一个有向图：
如下图，是一个有权图，无穷大符号代表没有边，如果有边，对应存储的值就是权值。
邻接矩阵比较适合稠密图，不然会比较浪费内存（无边也创建了内存）。
2.2. 邻接表
可以使用数组 + 链表/映射的形式存储。
如下图，是一个无向图：
如下图，是一个有向图：
还可以使用逆邻接表表示，如下图，表示的意思是，谁能到达v0/v1/v2/v3：
如下图，是一个有权图，节点可以存储权值：
图的相关概念比较多，有些作为了解即可。
