基本介绍

图(G)是由顶点集(V)和边集(E)组成的有序对，G=(V,E)，可以用|V|，|E|表示图中的顶点数量和边数量
图既可以是有向的，即单向链接，也可以是无向的，即双向链接。
只包含有向边的图称为有向图，只包含无向边的图称为无向图
若边关联了权重/成本，则叫做权重图，反之叫做非权重图

图的属性

一条边的两个端点为同一个顶点，称为自环
同一条边出现了不止一次，称为多重边
不包含自环或多重边的图称为简单图

边的数量
在一个简单图中，给定顶点的数量n(|V|=n)
有向图：0≤|E|≤n*(n-1)
无向图：0≤|E|≤n*(n-1)/2
若图中的边的数量接近最大的可能边数(顶点数量的平方)，则称这个图是稠密的。
若图中的边的数量接近顶点数量，则称这个图是稀疏的。
对图进行处理时，根据图的稠密/稀疏做出决策，如使用邻接矩阵存储稠密的图，使用邻接表存储稀疏的图
Path,Walk,Trail
简单路径(Path)：没有重复边/点的途径(Walk)
途径中的顶点可以重复但是边不能重复，则称为Trail
链接
强链接：从任意顶点可以去到任意的其他顶点
若是一个无向图，直接称它为connected
环
开始与结束为同一顶点且边数>0

图的存储方式

图的存储方式分为邻接矩阵和邻接表。使用邻接矩阵，当结点数量较多时，比如有1e5个点，那么至少开1e10的数组。
相较之下，使用邻接表就更为方便。邻接表包括前向星和vector两种形式。使用vector变长数组支持排序。
用vector g[N]来存图，g[i]表示i的所有出点编号。若有x->y，则g[x].push_back(y)