训练计划
什么是图？
图是一种复杂的非线性结构。
在线性结构中，数据元素之间满足唯一的线性关系，每个数据元素(除第一个和最后一个外)只有一个直接前趋和一个直接后继；
在树形结构中，数据元素之间有着明显的层次关系，并且每个数据元素只与上一层中的一个元素(parent node)及下一层的多个元素(孩子节点)相关；
而在图形结构中，节点之间的关系是任意的，图中任意两个数据元素之间都有可能相关。
图G由两个集合V(顶点Vertex)和E(边Edge)组成，定义为G=(V，E)
图论 (Graph theory) 是数学的一个分支，图是图论的主要研究对象。
图 (Graph) 是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。
图的相关概念（了解）
无向边
若顶点 U 到 V 之间的边没有方向，这条边就叫做无向边（Edge）
无向图
如果图中任意两个顶点之间的边都是无向边，则称该图为无项图（Undirected graphs）。
有向边
若从顶点 U 到 V 的边有方向，则称这条边为有向边，也称为弧 (Arc)。
有向图
如果图中任意两个顶点之间的边都是有向边，这个图就是有向图。
简单图
在图中，若不存在顶点到其自身的边，且同一条边不重复出现，这样的图就是简单图。
有向完全图
在有向图中，如果任意两点之间都存在方向互为相反的两条弧，这个图就是有向完全图。
n个顶点的有向完全图有 n(n-1)/2条边。
图的存储结构
直接存边
使用一个结构体数组来存边，数组中的每个元素都包含一条边的起点与终点（带边权的图还包含边权）。（或者使用多个数组分别存起点，终点和边权。）
复杂度：
查询是否存在某条边 O(m)。
遍历一个点的所有出边 O(m)。
遍历整张图 O(n*m)。
空间复杂度：O(m)。
应用:
由于直接存边的遍历效率低下，一般不用于遍历图。
在 Kruskal 算法 中，由于需要将边按边权排序，需要直接存边。
在有的题目中，需要多次建图（如建一遍原图，建一遍反图），此时既可以使用多个其它数据结构来同时存储多张图，也可以将边直接存下来，需要重新建图时利用直接存下的边来建图。
邻接矩阵（常用）：
参考代码：https://jhcloud.top/jpaste/?f6ff309c469025a1#cmMrbW/ZzwIiEYfXMt/x9+fKPNs6AZAHBcdWQT3eKpc=
邻接矩阵使用两个数组存储图。
顶点数组：一维数组 VERTEX，存放顶点的数据信息。如 VERTEX = [v1, v2, v3]
邻接矩阵：二维数组 A，下标表示顶点，元素表示顶点之间的关系。对于 A[i][j] 而言，存储的元素代表 VERTEX 中顶点 i 与顶点 j 间的边的信息。
一般而言，在无权图的邻接矩阵中，如果顶点间有边时，存储元素为 1，无边存放 0。如无向图 G1 和有向图 G2 的表示方法如下，它们的边都没有权重：
而对于网络（带权图）来说，邻接矩阵元素为边上的权值 w_{ij}，当无边时，可以用无穷大 ∞ 表示。
邻接矩阵的存储方式有如下特点：
1、无向图的邻接矩阵一定是对称矩阵。按压缩存储的思想，我们可以只用存储上三角或下三角元素。
2、无向图的第 i 行或第 i 列非零元素（或非 ∞ 元素）个数正好是第 i 个顶点的度。
3、有向图的第 i 行或第 i 列非零元素（或非 ∞ 元素）个数正好是第 i 个顶点的出度或入度。
空间复杂度 O(n^2)
时间复杂度
查询是否存在某条边:O(1)。
遍历一个点的所有出边：O(N)。
遍历整张图：O(n^2)。
空间复杂度：O(n^2)。
应用:
邻接矩阵只适用于没有重边（或重边可以忽略）的情况。
其最显著的优点是可以 O(1) 查询一条边是否存在。
由于邻接矩阵在稀疏图上效率很低（尤其是在点数较多的图上，空间无法承受），所以一般只会在稠密图上使用邻接矩阵。
邻接表：
邻接表使用顺序存储与链式存储相结合。
数组：存放顶点的数据信息。
链表：存放边的信息。
邻接表首先由一个数组，存放了所有的顶点结点，以每一个顶点结点作为头结点，又有 n 个链表，分别存放每个顶点依附的边。
同样是上面的 G1、G2 两张图，使用邻接表存储如下：
边结点里的序号指代的是顶点在顶点数组中间的索引。
对于网络来讲，边结点还需存储边的权重。
空间复杂度：O(m)
时间复杂度:
查询是否存在 u 到 v 的边：O(u的出边数）。
遍历点 u 的所有出边：O(u的出边数） 。
遍历整张图：O(n+m)。
空间复杂度：O(m)。
应用:
存各种图都很适合，除非有特殊需求（如需要快速查询一条边是否存在，且点数较少，可以使用邻接矩阵）。
尤其适用于需要对一个点的所有出边进行排序的场合。
十字链表（了解）
https://blog.csdn.net/wwh578867817/article/details/44748557
链式前向星(常用)
邻接表的一种实现：
参考代码：https://jhcloud.top/jpaste/?5c9ce06f50ad1aad#d8KIoeP4eGYaD5u6h8ETaYll6ngPYc1rWHxZL+MAd0c=
练手题目：
直接存边1：图的基本存储的基本方式二（提示：本题题面有误，m<=5e4 && q<=5e4, 时间复杂度 m*q 可过）
直接存边2：图的基本存储的基本方式三
邻接矩阵：图的基本存储的基本方式一
邻接矩阵/邻接表：图的基本存储的基本方式四（提示：建议大家使用邻接表（包含前向星）练习）
参考资料
8.2 图的存储方式
数据结构与算法：图和图算法(一)
数据结构学习笔记之图
数据结构–图的存储方式
oi-wiki 图的存储