「图论专题」——图
1. 前言：
本文仅讲述在OI中常见的图论相关概念，其余概念左转百度
2. 正文：
2.1 图：
2.1.1 概念：
是由顶点的集合（称作点集）与边的集合（称作边集）组成的二元组（通常记为G = (V, E)）
如下图：
V={1,2,3,4,5} E={(1,2),(2,3),(3,4),(4,5),(5,1),(2,5),(4,1)}
（顶点前后顺序不限）
2.1.2 有向图与无向图：
顾名思义，即分为边有无方向
如上图即为无向图，对于边可表示为（a,b）
注意：(a,b)与(b,a)等价，因为所表示的边相等
如下图即为有向图
对于边可表示为
注意：
2.1.3 度：
在无向图中，与顶点有关联的边的数目称之为度
（特殊的，有向图中则为此顶点的入度与出度之和）
入度：以该顶点为终点的边的数目和
出度：以该顶点为起点的边的数目和
2.1.4 带权图（网）：
显而易见，图的边上带有权值（即边上有数量关系）
2.1.5 路径：
路径长度是指路径上边或弧的数目
路径序列中顶点不重复出现的称为简单路径
路径中存在相同顶点称为回路，起点和终点相同的称为简单回路（或简单环）
2.1.6 连通图：
对于一个无向图G，如满足任意两点均有连通，则称无向图G为连通图
（连通：在一个无向图中，从顶点到另一个顶点有路径）
强连通图：在一个有向图G中，如满足任意两点u、v均可以从u到v及v到u有路径称之为强连通图
2.1.7 稀疏图和稠密图：
稀疏图：一张图的边数少于其图点数的平方
稠密图：一张图的边数接近于其图点数的平方
2.2 图的存储：
2.2.0 输入数组存边：
即在输入时直接用数组存储起点和终点（可能会有边权）
2.2.1 邻接数组：
设一个二维数组a
对于没有边权的图，a[u][v]可表示是否存在从u到v的边（1表存在，0则反之）
对于有边权的图，a[u][v]可存储从u到v的边权
大多适用于稠密图，优点是可以在O(1)的时间内查询边
1 /* 之后代码默认头文件省略 */
2 int a[N][N];
3 for (int i = 1; i <= n; i ++)
4 {
5 int u, v;
6 scanf("%d%d", &u, &v);
7 a[u][v] = 1 //带边权的图中可为 a[u][v] = 权值;
8 }2.2.2 邻接表：
设一个二维数组a
其中a[u][0]表示u的出度
a数组存储的是与该点的出度的相关信息（终点、边权等）
适用于各种图（尤其是关于出边的场合）
1 int a[N][N]
2 for (int i = 1; i <= n; i ++)
3 {
4 int u, v;
5 scanf("%d%d", &u, &v);
6 a[u][++ a[u][0]] = v; //存储u的出度
7 }2.2.3 链式前向星：
即为用链表存储的邻接表（本人也只会背板子）
舍弃时间求空间，有时方便，但不能快速查询边
1 int tot;
2 int next[N], head[N], to[N];
3
4 void add(int u, int v)
5 {
6 to[++ tot] = v;
7 next[tot] = head[u];
8 head[u] = tot;
9 }（下面表格用n代指图的点数，用m代指图的边数，用d代指点u的出度）
| 下：复杂度（应用） 右：存储方式 | 邻接矩阵 | 邻接表 | 链式前向星 |
| 查询一条边（从u到v） | O(1) | O(d) | O(d) |
| 遍历一个点的出边 | O(n) | O(d) | O(d) |
| 遍历整张图 | O(n2) | O(n+m) | O(n+m) |
| 空间复杂度 | O(n2) | O(m) | O(m) |
3.参考资料：
oi-wiki——图的存储