目录
一、图的相关概念1.1 简单图1.2 邻域1.3 度数1.4 路径1.5 连通1.5.1 无向图1.5.2 有向图 二、图的存储2.1 直接存边2.2 邻接矩阵2.3 邻接表2.4 链式前向星 三、图的遍历3.1 图的深度优先遍历3.2 图的广度优先遍历3.3 其他存图方式的BFS/DFS实现3.3.1 直接存边3.3.2 邻接矩阵3.3.3 邻接表 References
一、图的相关概念
图 G G G 是一个二元组 G = ( V , E ) G=(V,E) G=(V,E)。其中 V V V 是非空集，称为点集， V V V 中的每个元素称为顶点或节点。 E E E 为各节点之间边的集合，称为边集。图 G G G 的点数 ∣ V ∣ |V| ∣V∣ 称作 G G G 的阶。
当 V V V 和 E E E 都是有限集合时，称 G G G 为有限图。当 V V V 或 E E E 是无限集合时，称 G G G 为无限图。
根据边是否有向可将图分为：无向图、有向图和混合图：
无向图： E E E 中的每个元素都是一个无序二元组 ( u , v ) (u,v) (u,v)，称作无向边，其中 u , v ∈ V u,v\in V u,v∈V。记 e = ( u , v ) e=(u,v) e=(u,v)，则 u u u 和 v v v 称为 e e e 的端点；有向图： E E E 中的每个元素都是一个有序二元组 ( u , v ) (u,v) (u,v)，有时也写作 u → v u\to v u→v，称作有向边或弧。记 e = ( u , v ) e=(u,v) e=(u,v)，称 u u u 为 e e e 的起点， v v v 为 e e e 的终点，起点和终点也称为 e e e 的端点；混合图： E E E 中既有有向边，又有无向边。若 G G G 的每条边都被赋予一个数作为该边的权，则称 G G G 为赋权图。如果这些权都是正实数，则称 G G G 为正权图。
1.1 简单图
自环： 对 E E E 中的边 e = ( u , v ) e=(u,v) e=(u,v)，若 u = v u=v u=v，则称 e e e 是一个自环。
重边： 若存在 e 1 , e 2 ∈ E e_1,e_2\in E e1,e2∈E 使得 e 1 = e 2 e_1=e_2 e1=e2，则称它们是（一组）重边。
简单图： 若一个图中没有自环和重边，则它被称为简单图。
多重图： 图中存在自环或重边。
? 在无向图中 ( u , v ) (u,v) (u,v) 和 ( v , u ) (v,u) (v,u) 算一组重边，但在有向图中不算。
1.2 邻域
在无向图 G = ( V , E ) G=(V,E) G=(V,E) 中，若对 u , v ∈ V u,v\in V u,v∈V，存在边 ( u , v ) (u,v) (u,v)，则称 u u u 和 v v v 是相邻的。
一个顶点 v ∈ V v \in V v∈V 的邻域是所有与之相邻的顶点所构成的集合，记作 N ( v ) N(v) N(v)。一个点集 S S S 的邻域定义如下：
N ( S ) = ⋃ v ∈ S N ( v ) N(S)=\bigcup_{v\in S} N(v) N(S)=v∈S⋃N(v)
1.3 度数
与一个顶点 v v v 关联的边的条数称作该顶点的度，记作 d ( v ) d(v) d(v)。
对于无向简单图，有 d ( v ) = ∣ N ( v ) ∣ d(v)=|N(v)| d(v)=∣N(v)∣。根据 d ( v ) d(v) d(v) 的取值可对图中的顶点进行分类：
d ( v ) = { 0 , v 是孤立点 1 , v 是叶节点 / 悬挂点 2 k , v 是偶点 2 k + 1 , v 是奇点 ∣ V ∣ − 1 , v 是支配点 d(v)= \begin{cases} 0, &v\,是孤立点 \\ 1, &v\,是叶节点/悬挂点 \\ 2k,&v\,是偶点 \\ 2k+1,&v\,是奇点 \\ |V|-1,&v\,是支配点 \\ \end{cases} d(v)=⎩ ⎨ ⎧0,1,2k,2k+1,∣V∣−1,v是孤立点v是叶节点/悬挂点v是偶点v是奇点v是支配点
? 自环 ( v , v ) (v,v) (v,v) 将对 d ( v ) d(v) d(v) 产生 2 2 2 的贡献。
对于图 G G G，所有节点的度数的最小值称为 G G G 的最小度，记作 δ ( G ) \delta (G) δ(G)；最大值称为最大度，记作 Δ ( G ) \Delta (G) Δ(G)。即： δ ( G ) = min v ∈ G d ( v ) \delta (G) = \min_{v \in G} d(v) δ(G)=minv∈Gd(v)， Δ ( G ) = max v ∈ G d ( v ) \Delta (G) = \max_{v \in G} d(v) Δ(G)=maxv∈Gd(v)。若 δ ( G ) = Δ ( G ) = k \delta(G)=\Delta(G)=k δ(G)=Δ(G)=k，即图中每个顶点的度数都是一个固定的常数 k k k，则称 G G G 为 k − k- k−正则图。
握手定理（图论基本定理）：对任何无向图，由于每条边都会贡献两个度，所以 ∑ v ∈ V d ( v ) = 2 ∣ E ∣ \sum_{v\in V}d(v)=2|E| ∑v∈Vd(v)=2∣E∣。
下面考虑有向图。以一个顶点 v v v 为起点的边的条数称为该顶点的出度，记作 d + ( v ) d^+(v) d+(v)。以一个顶点 v v v 为终点的边的条数称为该节点的入度，记作 d − ( v ) d^-(v) d−(v)。显然 d + ( v ) + d − ( v ) = d ( v ) d^+(v)+d^-(v)=d(v) d+(v)+d−(v)=d(v)。
由于每条边都会贡献一个出度和一个入度，所以
∑ v ∈ V d + ( v ) = ∑ v ∈ V d − ( v ) = ∣ E ∣ \sum_{v\in V}d^+(v)=\sum_{v\in V}d^-(v)=|E| v∈V∑d+(v)=v∈V∑d−(v)=∣E∣
1.4 路径
途径：途径是连接一连串顶点的边的序列，可以为有限或无限长度。形式化地说，一条有限途径 w w w 是一个边的序列 e 1 , e 2 , ⋯ , e k e_1, e_2, \cdots, e_k e1,e2,⋯,ek，使得存在一个顶点序列 v 0 , v 1 , ⋯ , v k v_0, v_1, \cdots, v_k v0,v1,⋯,vk 满足 e i = ( v i − 1 , v i ) e_i = (v_{i-1}, v_i) ei=(vi−1,vi)。这样的途径可以简写为 v 0 → v 1 → v 2 → ⋯ → v k v_0 \to v_1 \to v_2 \to \cdots \to v_k v0→v1→v2→⋯→vk。通常来说，边的数量 k k k 被称作这条途径的长度（如果边是带权的，长度通常指途径上的边权之和）。
迹：对于一条途径 w w w，若 e 1 , e 2 , ⋯ , e k e_1, e_2, \cdots, e_k e1,e2,⋯,ek 两两互不相同，则称 w w w 是一条迹。
路径：对于一条迹 w w w，若其连接的点的序列中点两两不同，则称 w w w 是一条路径。
? 以上三者的区别在于：途径的边和顶点都可以重复；迹的边不能重复，但顶点可以重复；路径的边和顶点都不能重复。
回路：对于一条迹 w w w，若 v 0 = v k v_0 = v_k v0=vk，则称 w w w 是一条回路。
环/圈：对于一条回路 w w w，若 v 0 = v k v_0 = v_k v0=vk 是点序列中唯一重复出现的点对，则称 w w w 是一个环。
⚠️ 关于路径的定义在不同地方可能有所不同，如，「路径」可能指本文中的「途径」，「环」可能指本文中的「回路」。
1.5 连通
1.5.1 无向图
对于一张无向图 G = ( V , E ) G = (V, E) G=(V,E)，对于 u , v ∈ V u, v \in V u,v∈V，若存在一条途径使得 v 0 = u , v k = v v_0 = u, v_k = v v0=u,vk=v，则称 u u u 和 v v v 是连通的。由定义，任意一个顶点和自身连通，任意一条边的两个端点连通。
若无向图 G G G 满足其中任意两个顶点均连通，则称 G G G 是连通图， G G G 的这一性质称作连通性。
若 H H H 是 G G G 的一个连通子图，且不存在 F F F 满足 H ⊊ F ⊆ G H\subsetneq F \subseteq G H⊊F⊆G 且 F F F 为连通图，则称 H H H 是 G G G 的一个连通块/连通分量。
1.5.2 有向图
对于一张有向图 G = ( V , E ) G = (V, E) G=(V,E)，对于 u , v ∈ V u, v \in V u,v∈V，若存在一条途径使得 v 0 = u , v k = v v_0 = u, v_k = v v0=u,vk=v，则称 u u u 可达 v v v。由定义，任意一个顶点可达自身，任意一条边的起点可达终点。
若有向图 G G G 满足其中任意两个顶点互相可达，则称 G G G 是强连通的。若有向图 G G G 的边替换为无向边后可以得到一张连通图，则称原来这张有向图是弱连通的。
类似可得强连通分量和弱连通分量的定义。
二、图的存储
图的输入格式通常为：
? 第一行包含两个整数，分别是 n n n 和 m m m，代表 ∣ V ∣ |V| ∣V∣ 和 ∣ E ∣ |E| ∣E∣。接下来 m m m 行，每行包含三个整数，分别是 a a a， b b b 和 c c c，代表起点，终点和边权。
2.1 直接存边
使用一个 vector 来存边，数组中的每个元素都包含了一条边的起点与终点（带边权的图还包含边权）。
struct Edge { int a, b, c;};int main() { int n, m; cin >> n >> m; vector<Edge> edges(m); // 也可以先声明为全局变量，然后通过resize调整 for (int i = 0; i < m; i++) cin >> edges[i].a >> edges[i].b >> edges[i].c; return 0;}复杂度分析：
查询是否存在某条边： O ( m ) O(m) O(m)；遍历一个点的所有出边： O ( m ) O(m) O(m)；遍历整张图： O ( n m ) O(nm) O(nm)；空间复杂度： O ( m ) O(m) O(m)。应用：
直接存边的遍历效率低下，一般不用于遍历图。2.2 邻接矩阵
使用一个二维数组 adj 来存边，其中 adj[u][v] = 1 表示存在 u u u 到 v v v 的边，adj[u][v] = 0 表示不存在。如果是带边权的图，可以在 adj[u][v] 中存储 u u u 到 v v v 的边权。
int g[N][N];int main() { int n, m; cin >> n >> m; while (m--) { int a, b, c; cin >> a >> b >> c; g[a][b] = c; } return 0;}复杂度分析：
查询是否存在某条边： O ( 1 ) O(1) O(1)；遍历一个点的所有出边： O ( n ) O(n) O(n)；遍历整张图： O ( n 2 ) O(n^2) O(n2)；空间复杂度： O ( n 2 ) O(n^2) O(n2)。应用：
邻接矩阵只适用于没有重边的情况；邻接矩阵在稀疏图上的效率很低，所以一般只会在稠密图上使用邻接矩阵。2.3 邻接表
使用一个支持动态增加元素的数据结构构成的数组，如 vector<int> adj[N] 来存边，其中 adj[u] 存储的是点 u u u 的所有出边的相关信息（终点、边权等）。
vector<pair<int, int>> adj[N];int main() { int n, m; cin >> n >> m; while (m--) { int a, b, c; cin >> a >> b >> c; adj[a].emplace_back(b, c); } return 0;}邻接表有很多种实现方式，我们还可以单独定义一个结构体或者开两个 vector<int> 型数组分别用来存储终点和边权。
复杂度分析：
查询是否存在 u u u 到 v v v 的边： O ( d + ( u ) ) O(d^+(u)) O(d+(u))；遍历点 u u u 的所有出边： O ( d + ( u ) ) O(d^+(u)) O(d+(u))；遍历整张图： O ( n + m ) O(n+m) O(n+m)；空间复杂度： O ( m ) O(m) O(m)。应用：
存各种图都很适合，除非有特殊需求；尤其适用于需要对一个点的所有出边进行排序的场合。排序之后，查边的复杂度降至 O ( log d + ( u ) ) O(\log d^+(u)) O(logd+(u))。2.4 链式前向星
之前的邻接表是基于 vector 来实现的，如果把 vector 换成用数组实现的链表，效率将会提高很多，而这样实现的邻接表又被称为链式前向星。
? 链式前向星和哈希表中的拉链法非常相似。
int h[N], e[N], ne[N], idx; // e相当于val，ne相当于nxt，具体请参考上方的超链接int w[N]; // 用来存储每条边的权重// 向图中添加a到b的有向边，权重为cvoid add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;}int main() { memset(h, -1, sizeof(h)); // 使用链式前向星必须进行初始化 int n, m; cin >> n >> m; while (m--) { int a, b, c; cin >> a >> b >> c; add(a, b, c); } return 0;}复杂度分析：
因其本质仍是邻接表，所以复杂度和2.3节中的相同。
应用：
存各种图都很适合，但不能快速查询一条边是否存在，也不能方便地对一个点的出边进行排序；优点是边是带编号的，有时会非常有用。三、图的遍历
接下来提到的图均使用链式前向星来存储。
3.1 图的深度优先遍历
深度优先遍历也叫深度优先搜索（Depth First Search），遍历是手段，搜索是目的，通过遍历所有可能的情况以达到搜索的目的，因此「遍历」和「搜索」可以看作是两个的等价概念。
「一条路走到底，不撞南墙不回头」是对DFS的最直观描述。DFS最显著的特征在于其递归调用自身。DFS会对其访问过的点打上访问标记，在遍历图时跳过已打过标记的点，以确保每个点仅访问一次。
DFS实现：
// 从节点u开始进行深度优先搜索void dfs(int u) { st[u] = true; // 给u打上已访问的标记 for (int i = h[u]; ~i; i = ne[i]) { int v = e[i]; if (!st[v]) dfs(v); }}DFS的时间复杂度为 O ( n + m ) O(n+m) O(n+m)，空间复杂度为 O ( n ) O(n) O(n)。
3.2 图的广度优先遍历
广度优先遍历（Breadth First Search）每次都尝试访问同一层的节点。 如果同一层都访问完了，再访问下一层。这样做的结果是，BFS算法找到的路径是从起点开始的最短合法路径。
算法过程可以看做是图上火苗传播的过程：最开始只有起点着火了，在每一时刻，有火的节点都向它相邻的所有节点传播火苗。
BFS实现：
// 从节点u开始进行广度优先搜索void bfs(int u) { queue<int> q; st[u] = true, q.push(u); while (!q.empty()) { auto t = q.front(); q.pop(); for (int i = h[t]; ~i; i = ne[i]) { int v = e[i]; if (!st[v]) st[v] = true, q.push(v); } }}在BFS的过程中，也可以记录一些额外的信息。例如，我们可以开一个 d 数组用于记录起点到某个节点的最短距离，再开一个 p 数组记录是从哪个节点走到当前节点的。
void bfs(int u) { queue<int> q; st[u] = true, q.push(u); d[u] = 0, p[u] = -1; // 假设节点的编号均为正整数 while (!q.empty()) { auto t = q.front(); q.pop(); for (int i = h[t]; ~i; i = ne[i]) { int v = e[i]; if (!st[v]) { st[v] = true, q.push(v); d[v] = d[t] + 1, p[v] = t; } } }}假设路径终点是 x，那么从 u 到 x 的最短路径长度就是 d[x]，相应地，我们可以根据 p 数组还原出这条路径：
vector<int> restore(int x) { vector<int> path; for (int v = x; ~v; v = p[v]) path.push_back(v); reverse(path.begin(), path.end()); return path;}BFS的时空复杂度与DFS相同。
3.3 其他存图方式的BFS/DFS实现
3.3.1 直接存边
BFS：
void bfs(int u) { queue<int> q; st[u] = true, q.push(u); while (!q.empty()) { auto t = q.front(); q.pop(); for (auto &[a, b, c]: edges) if (a == t && !st[b]) st[b] = true, q.push(b); }}DFS：
void dfs(int u) { st[u] = true; for (auto &[a, b, c]: edges) if (a == u && !st[b]) dfs(b);}3.3.2 邻接矩阵
假设图中节点的编号从 1 1 1 开始。
BFS：
void bfs(int u) { queue<int> q; st[u] = true, q.push(u); while (!q.empty()) { auto t = q.front(); q.pop(); for (int j = 1; j <= n; j++) { if (g[t][j] && !st[j]) st[j] = true, q.push(j); } }}DFS：
void dfs(int u) { st[u] = true; for (int j = 1; j <= n; j++) if (g[u][j] && !st[j]) dfs(j);}3.3.3 邻接表
BFS：
void bfs(int u) { queue<int> q; st[u] = true, q.push(u); while (!q.empty()) { auto t = q.front(); q.pop(); for (auto &[b, c]: adj[t]) if (!st[b]) st[b] = true, q.push(b); }}DFS：
void dfs(int u) { st[u] = true; for (auto &[b, c]: adj[u]) { if (!st[b]) dfs(b); }}References
[1] https://oi-wiki.org/graph/