前言

图论真是枯燥我还跳过了树，好在已经过来了。

前面的内容比较简单，所以会短邑点

---

图的存储

图的存储有三种方式：

1. 邻接矩阵
2. 邻接链表
3. 链式前向星

其中，我们最常用的是邻接链表。

记住这个图：

下面会用这个图来举例。

邻接矩阵

定义一个二维数组 g，其中 g[u][v] 表示节点 $u$ 和节点 $v$ 是否相连。如下：

节点	1	2	3	4	5
1	0	1	$1$	$0$	0
2	$1$	0	$0$	1	$0$
3	1	$0$	0	$1$	0
4	0	1	$1$	0	$0$
5	$0$	0	$0$	1	0

其中，如果边有权值，可以设为权值而不是 $1$。

• 添加边：要在 $u-v$ 添加一条边，只需要把 g[u][v] 设为 $1$ 或权值。
• 删除边：要删除 $u-v$ 之间的边，只需要把 g[u][v] 设为 $0$。
• 判断边：判断 $u-v$ 是否有边，只需要查找 g[u][v] || g[v][u]。
• 遍历边：枚举所有点，判断是否与 $u$ 相连。

优点

删边、添边极快，容易理解。

缺点

内存占用大（$O(m^2)$）。

遍历时间 $O(n)$。

邻接链表最常用

本质上是定义 $n$ 条链表，第 $u$ 条链表上是与 $u$ 相连的点。

但是使用链表极其繁琐，而 vector 正好可以解决这个问题。如表：

节点	与	它	相连	的	点
1	2	3	/
2	1	4
3	$1$	$4$
4	2	3
5	4	/

定义 vector <int> g[N]（$N$ 是常量，表示点数 $n$ 的最大值）。内容就和上表是一样的。

• 添加边：要添加 $u-v$ 边，只需要 g[u].push_back(v)。
• 删除边：要删除 $u-v$ 边，需要枚举 $u$ 的所有边，如果有 $u-v$，就删除（g[u].erase(g[u].begin() + k)）。
• 查找边：遍历 $u$ 的所有边，判断是否有 $v$ 与它相连。
• 遍历边：循环遍历 g[u]。

优点

内存占用小，添加边容易。

缺点

删边复杂。

链式前向星

定义一个 head[N]、edge[N][3]（或 {u,v,next}edge[N]）。

head[u] 表示与 $u$ 相连的第一条边在 edge 的位置。edge[id].u 表示这一条边的一段，edge[id].v 则是另一段，edge[id].next 表示 edge[id].u 的下一条边在 edge 的边号。

如表：

节点	head
1	$1$
2	3
3	5
4	7
5	10

边号	$u$	$v$	$next$
1	$1$	2	$2$
2	1	3	-1
3	2	1	4
4	$2$	4	-1
5	3	1	6
6	$3$	4	-1
7	4	2	8
8	$4$	3	9
9	4	5	-1
10	5	4	$-1$