图论基础

图的相关概念

图论相关定义在不同教材中往往会有所不同，遇到的时候需根据上下文加以判断。

本文章摘录自OI-Wiki，原文地址：图论相关概念 - OI Wiki

图

图 (graph)是一个二元组 $G=(V(G), E(G))$。其中 $V(G)$ 是非空集，称为点集 (vertex set)，对于 $V$ 中的每个元素，我们称其为顶点 (vertex)或节点 (node)，简称点；$E(G)$ 为 $V(G)$ 各结点之间边的集合，称为**边集 (edge set)**。

常用 $G=(V,E)$ 表示图。

当 $V,E$ 都是有限集合时，称 $G$ 为有限图。

当 $V$ 或 $E$ 是无限集合时，称 $G$ 为无限图。

图有多种，包括**无向图 (undirected graph)，有向图 (directed graph)，混合图 (mixed graph)**等。

若 $G$ 为无向图，则 $E$ 中的每个元素为一个无序二元组 $(u, v)$，称作**无向边 (undirected edge)，简称边 (edge)，其中 $u, v \in V$。设 $e = (u, v)$，则 $u$ 和 $v$ 称为 $e$ 的端点 (endpoint)**。

若 $G$ 为有向图，则 $E$ 中的每一个元素为一个有序二元组 $(u, v)$，有时也写作 $u \to v$，称作**有向边 (directed edge)或弧 (arc)，在不引起混淆的情况下也可以称作边 (edge)。设 $e = u \to v$，则此时 $u$ 称为 $e$ 的起点 (tail)，$v$ 称为 $e$ 的终点 (head)，起点和终点也称为 $e$ 的端点 (endpoint)**。并称 $u$ 是 $v$ 的直接前驱，$v$ 是 $u$ 的直接后继。

“为什么起点是 tail，终点是 head？”
边通常用箭头表示，而箭头是从「尾」指向「头」的。

若 $G$ 为混合图，则 $E$ 中既有有向边，又有无向边。

若 $G$ 的每条边 $e_k=(u_k,v_k)$ 都被赋予一个数作为该边的权，则称 $G$ 为赋权图。如果这些权都是正实数，就称 $G$ 为正权图。

图 $G$ 的点数 $\left| V(G) \right|$ 也被称作图 $G$ 的**阶 (order)**。

形象地说，图是由若干点以及连接点与点的边构成的。

color1

dom-tree1

相邻

在无向图 $G = (V, E)$ 中，若点 $v$ 是边 $e$ 的一个端点，则称 $v$ 和 $e$ 是**关联的 (incident)或相邻的 (adjacent)。对于两顶点 $u$ 和 $v$，若存在边 $(u, v)$，则称 $u$ 和 $v$ 是相邻的 (adjacent)**。

一个顶点 $v \in V$ 的**邻域 (neighborhood)**是所有与之相邻的顶点所构成的集合，记作 $N(v)$。

一个点集 $S$ 的邻域是所有与 $S$ 中至少一个点相邻的点所构成的集合，记作 $N(S)$，即：

$$
N(S) = \bigcup_{v \in S} N(v)
$$

简单图

**自环 (loop)**：对 $E$ 中的边 $e = (u, v)$，若 $u = v$，则 $e$ 被称作一个自环。

**重边 (multiple edge)**：若 $E$ 中存在两个完全相同的元素（边）$e_1, e_2$，则它们被称作（一组）重边。

**简单图 (simple graph)**：若一个图中没有自环和重边，它被称为简单图。具有至少两个顶点的简单无向图中一定存在度相同的结点。（鸽巢原理）

如果一张图中有自环或重边，则称它为**多重图 (multigraph)**。

在无向图中 $(u, v)$ 和 $(v, u)$ 算一组重边，而在有向图中，$u \to v$ 和 $v \to u$ 不为重边。

在题目中，如果没有特殊说明，是可以存在自环和重边的，在做题时需特殊考虑。

度数

与一个顶点 $v$ 关联的边的条数称作该顶点的**度 (degree)**，记作 $d(v)$。特别地，对于边 $(v, v)$，则每条这样的边要对 $d(v)$ 产生 $2$ 的贡献。

对于无向简单图，有 $d(v) = \left| N(v) \right|$。

握手定理（又称图论基本定理）：对于任何无向图 $G = (V, E)$，有 $\sum_{v \in V} d(v) = 2 \left| E \right|$。

推论：在任意图中，度数为奇数的点必然有偶数个。

若 $d(v) = 0$，则称 $v$ 为**孤立点 (isolated vertex)**。

若 $d(v) = 1$，则称 $v$ 为叶节点 (leaf vertex)/**悬挂点 (pendant vertex)**。

若 $2 \mid d(v)$，则称 $v$ 为**偶点 (even vertex)**。

若 $2 \nmid d(v)$，则称 $v$ 为**奇点 (odd vertex)**。图中奇点的个数是偶数。

若 $d(v) = \left| V \right| - 1$，则称 $v$ 为**支配点 (universal vertex)**。

对一张图，所有节点的度数的最小值称为 $G$ 的**最小度 (minimum degree)，记作 $\delta (G)$；最大值称为最大度 (maximum degree)**，记作 $\Delta (G)$。即：$\delta (G) = \min_{v \in G} d(v)$，$\Delta (G) = \max_{v \in G} d(v)$。

在有向图 $G = (V, E)$ 中，以一个顶点 $v$ 为起点的边的条数称为该顶点的**出度 (out-degree)，记作 $d^+(v)$。以一个顶点 $v$ 为终点的边的条数称为该节点的入度 (in-degree)**，记作 $d^-(v)$。显然 $d^+(v)+d^-(v)=d(v)$。

对于任何有向图 $G = (V, E)$，有：

$$
\sum_{v \in V} d^+(v) = \sum_{v \in V} d^-(v) = \left| E \right|
$$

若对一张无向图 $G = (V, E)$，每个顶点的度数都是一个固定的常数 $k$，则称 $G$ 为**$k$- 正则图 ($k$-regular graph)**。

如果给定一个序列 a，可以找到一个图 G，以其为度数列，则称 a 是可图化的。

如果给定一个序列 a，可以找到一个简单图 G，以其为度数列，则称 a 是可简单图化的。

路径

途径 (walk)：途径是连接一连串顶点的边的序列，可以为有限或无限长度。形式化地说，一条有限途径 $w$ 是一个边的序列 $e_1, e_2, \ldots, e_k$，使得存在一个顶点序列 $v_0, v_1, \ldots, v_k$ 满足 $e_i = (v_{i-1}, v_i)$，其中 $i \in [1, k]$。这样的途径可以简写为 $v_0 \to v_1 \to v_2 \to \cdots \to v_k$。通常来说，边的数量 $k$ 被称作这条途径的长度（如果边是带权的，长度通常指途径上的边权之和，题目中也可能另有定义）。

**迹 (trail)**：对于一条途径 $w$，若 $e_1, e_2, \ldots, e_k$ 两两互不相同，则称 $w$ 是一条迹。

**路径 (path)（又称简单路径 (simple path)**）：对于一条迹 $w$，若其连接的点的序列中点两两不同，则称 $w$ 是一条路径。

**回路 (circuit)**：对于一条迹 $w$，若 $v_0 = v_k$，则称 $w$ 是一条回路。

**环/圈 (cycle)（又称简单回路/简单环 (simple circuit)**）：对于一条回路 $w$，若 $v_0 = v_k$ 是点序列中唯一重复出现的点对，则称 $w$ 是一个环。

关于路径的定义在不同地方可能有所不同，如，「路径」可能指本文中的「途径」，「环」可能指本文中的「回路」。如果在题目中看到类似的词汇，且没有「简单路径」/「非简单路径」（即本文中的「途径」）等特殊说明，最好询问一下具体指什么。

子图

对一张图 $G = (V, E)$，若存在另一张图 $H = (V’, E’)$ 满足 $V’ \subseteq V$ 且 $E’ \subseteq E$，则称 $H$ 是 $G$ 的**子图 (subgraph)**，记作 $H \subseteq G$。

若对 $H \subseteq G$，满足 $\forall u, v \in V’$，只要 $(u, v) \in E$，均有 $(u, v) \in E’$，则称 $H$ 是 $G$ 的**导出子图/诱导子图 (induced subgraph)**。

容易发现，一个图的导出子图仅由子图的点集决定，因此点集为 $V’$($V’ \subseteq V$) 的导出子图称为 $V’$ 导出的子图，记作 $G \left[ V’ \right]$。

若 $H \subseteq G$ 满足 $V’ = V$，则称 $H$ 为 $G$ 的**生成子图/支撑子图 (spanning subgraph)**。

显然，$G$ 是自身的子图，支撑子图，导出子图；无边图 是 $G$ 的支撑子图。原图 $G$ 和无边图都是 $G$ 的平凡子图。

如果一张无向图 $G$ 的某个生成子图 $F$ 为 $k$- 正则图，则称 $F$ 为 $G$ 的一个**$k$- 因子 ($k$-factor)**。

如果有向图 $G = (V, E)$ 的导出子图 $H = G \left[ V^\ast \right]$ 满足 $\forall v \in V^\ast, (v, u) \in E$，有 $u \in V^\ast$，则称 $H$ 为 $G$ 的一个**闭合子图 (closed subgraph)**。

连通

无向图

对于一张无向图 $G = (V, E)$，对于 $u, v \in V$，若存在一条途径使得 $v_0 = u, v_k = v$，则称 $u$ 和 $v$ 是**连通的 (connected)**。由定义，任意一个顶点和自身连通，任意一条边的两个端点连通。

若无向图 $G = (V, E)$，满足其中任意两个顶点均连通，则称 $G$ 是**连通图 (connected graph)，$G$ 的这一性质称作连通性 (connectivity)**。

若 $H$ 是 $G$ 的一个连通子图，且不存在 $F$ 满足 $H\subsetneq F \subseteq G$ 且 $F$ 为连通图，则 $H$ 是 $G$ 的一个**连通块/连通分量 (connected component)**（极大连通子图）。

有向图

对于一张有向图 $G = (V, E)$，对于 $u, v \in V$，若存在一条途径使得 $v_0 = u, v_k = v$，则称 $u$ 可达 $v$。由定义，任意一个顶点可达自身，任意一条边的起点可达终点。（无向图中的连通也可以视作双向可达。）

若一张有向图的节点两两互相可达，则称这张图是**强连通的 (strongly connected)**。

若一张有向图的边替换为无向边后可以得到一张连通图，则称原来这张有向图是**弱连通的 (weakly connected)**。

与连通分量类似，也有**弱连通分量 (weakly connected component)（极大弱连通子图）和强连通分量 (strongly connected component)**（极大强连通子图）。

相关算法请参见 强连通分量。

割

相关算法请参见 割点和桥 以及 双连通分量。

在本部分中，有向图的「连通」一般指「强连通」。

对于连通图 $G = (V, E)$，若 $V’\subseteq V$ 且 $G\left[V\setminus V’\right]$（即从 $G$ 中删去 $V’$ 中的点）不是连通图，则 $V’$ 是图 $G$ 的一个**点割集 (vertex cut/separating set)。大小为一的点割集又被称作割点 (cut vertex)**。

对于连通图 $G = (V, E)$ 和整数 $k$，若 $|V|\ge k+1$ 且 $G$ 不存在大小为 $k-1$ 的点割集，则称图 $G$ 是**$k$- 点连通的 ($k$-vertex-connected)，而使得上式成立的最大的 $k$ 被称作图 $G$ 的点连通度 (vertex connectivity)**，记作 $\kappa(G)$。（对于非完全图，点连通度即为最小点割集的大小，而完全图 $K_n$ 的点连通度为 $n-1$。）

对于图 $G = (V, E)$ 以及 $u, v\in V$ 满足 $u\ne v$，$u$ 和 $v$ 不相邻，$u$ 可达 $v$，若 $V’\subseteq V$，$u, v\notin V’$，且在 $G\left[V\setminus V’\right]$ 中 $u$ 和 $v$ 不连通，则 $V’$ 被称作 $u$ 到 $v$ 的点割集。$u$ 到 $v$ 的最小点割集的大小被称作 $u$ 到 $v$ 的**局部点连通度 (local connectivity)**，记作 $\kappa(u, v)$。

还可以在边上作类似的定义：

对于连通图 $G = (V, E)$，若 $E’\subseteq E$ 且 $G’ = (V, E\setminus E’)$（即从 $G$ 中删去 $E’$ 中的边）不是连通图，则 $E’$ 是图 $G$ 的一个**边割集 (edge cut)。大小为一的边割集又被称作桥 (bridge)**。

对于连通图 $G = (V, E)$ 和整数 $k$，若 $G$ 不存在大小为 $k-1$ 的边割集，则称图 $G$ 是**$k$- 边连通的 ($k$-edge-connected)，而使得上式成立的最大的 $k$ 被称作图 $G$ 的边连通度 (edge connectivity)**，记作 $\lambda(G)$。（对于任何图，边连通度即为最小边割集的大小。）

对于图 $G = (V, E)$ 以及 $u, v\in V$ 满足 $u\ne v$，$u$ 可达 $v$，若 $E’\subseteq E$，且在 $G’=(V, E\setminus E’)$ 中 $u$ 和 $v$ 不连通，则 $E’$ 被称作 $u$ 到 $v$ 的边割集。$u$ 到 $v$ 的最小边割集的大小被称作 $u$ 到 $v$ 的**局部边连通度 (local edge-connectivity)**，记作 $\lambda(u, v)$。

**点双连通 (biconnected)**几乎与 $2$- 点连通完全一致，除了一条边连接两个点构成的图，它是点双连通的，但不是 $2$- 点连通的。换句话说，没有割点的连通图是点双连通的。

**边双连通 ($2$-edge-connected)**与 $2$- 边双连通完全一致。换句话说，没有桥的连通图是边双连通的。

与连通分量类似，也有**点双连通分量 (biconnected component)（极大点双连通子图）和边双连通分量 ($2$-edge-connected component)**（极大边双连通子图）。

Whitney 定理：对任意的图 $G$，有 $\kappa(G)\le \lambda(G)\le \delta(G)$。（不等式中的三项分别为点连通度、边连通度、最小度。）

稀疏图/稠密图

若一张图的边数远小于其点数的平方，那么它是一张**稀疏图 (sparse graph)**。

若一张图的边数接近其点数的平方，那么它是一张**稠密图 (dense graph)**。

这两个概念并没有严格的定义，一般用于讨论 时间复杂度 为 $O(|V|^2)$ 的算法与 $O(|E|)$ 的算法的效率差异（在稠密图上这两种算法效率相当，而在稀疏图上 $O(|E|)$ 的算法效率明显更高）。

补图

对于无向简单图 $G = (V, E)$，它的**补图 (complement graph)**指的是这样的一张图：记作 $\bar G$，满足 $V \left( \bar G \right) = V \left( G \right)$，且对任意节点对 $(u, v)$，$(u, v) \in E \left( \bar G \right)$ 当且仅当 $(u, v) \notin E \left( G \right)$。

反图

对于有向图 $G = (V, E)$，它的**反图 (transpose graph)**指的是点集不变，每条边反向得到的图，即：若 $G$ 的反图为 $G’=(V, E’)$，则 $E’={(v, u)|(u, v)\in E}$。

特殊的图

若无向简单图 $G$ 满足任意不同两点间均有边，则称 $G$ 为**完全图 (complete graph)，$n$ 阶完全图记作 $K_n$。若有向图 $G$ 满足任意不同两点间都有两条方向不同的边，则称 $G$ 为有向完全图 (complete digraph)**。

边集为空的图称为**无边图 (edgeless graph)、空图 (empty graph)或零图 (null graph)**，$n$ 阶无边图记作 $\overline{K}_n$ 或 $N_n$。$N_n$ 与 $K_n$ 互为补图。

零图 (null graph)也可指零阶图 (order-zero graph)$K_0$，即点集与边集均为空的图。

若有向简单图 $G$ 满足任意不同两点间都有恰好一条边（单向），则称 $G$ 为**竞赛图 (tournament graph)**。

若无向简单图 $G = \left( V, E \right)$ 的所有边恰好构成一个圈，则称 $G$ 为**环图/圈图 (cycle graph)**，$n$($n \geq 3$) 阶圈图记作 $C_n$。易知，一张图为圈图的充分必要条件是，它是 $2$- 正则连通图。

若无向简单图 $G = \left( V, E \right)$ 满足，存在一个点 $v$ 为支配点，其余点之间没有边相连，则称 $G$ 为**星图/菊花图 (star graph)**，$n + 1$($n \geq 1$) 阶星图记作 $S_n$。

若无向简单图 $G = \left( V, E \right)$ 满足，存在一个点 $v$ 为支配点，其它点之间构成一个圈，则称 $G$ 为**轮图 (wheel graph)**，$n + 1$($n \geq 3$) 阶轮图记作 $W_n$。

若无向简单图 $G = \left( V, E \right)$ 的所有边恰好构成一条简单路径，则称 $G$ 为**链 (chain/path graph)**，$n$ 阶的链记作 $P_n$。易知，一条链由一个圈图删去一条边而得。

如果一张无向连通图不含环，则称它是一棵**树 (tree)**。相关内容详见 树基础。

如果一张无向连通图包含恰好一个环，则称它是一棵**基环树 (pseudotree)**。

如果一张有向弱连通图每个点的入度都为 $1$，则称它是一棵基环外向树。

如果一张有向弱连通图每个点的出度都为 $1$，则称它是一棵基环内向树。

多棵树可以组成一个森林 (forest)，多棵基环树可以组成基环森林 (pseudoforest)，多棵基环外向树可以组成基环外向树森林，多棵基环内向树可以组成**基环内向森林 (functional graph)**。

如果一张无向连通图的每条边最多在一个环内，则称它是一棵仙人掌 (cactus)。多棵仙人掌可以组成沙漠。

如果一张图的点集可以被分为两部分，每一部分的内部都没有连边，那么这张图是一张**二分图 (bipartite graph)。如果二分图中任何两个不在同一部分的点之间都有连边，那么这张图是一张完全二分图 (complete bipartite graph/biclique)**，一张两部分分别有 $n$ 个点和 $m$ 个点的完全二分图记作 $K_{n, m}$。相关内容详见 二分图。

如果一张图可以画在一个平面上，且没有两条边在非端点处相交，那么这张图是一张**平面图 (planar graph)**。一张图的任何子图都不是 $K_5$ 或 $K_{3, 3}$ 是其为一张平面图的充要条件。对于简单连通平面图 $G=(V, E)$ 且 $V\ge 3$，$|E|\le 3|V|-6$。

无向简单图的二元运算

对于无向简单图，我们可以定义如下二元运算：

**交 (intersection)**：图 $G = \left( V_1, E_1 \right), H = \left( V_2, E_2 \right)$ 的交定义成图 $G \cap H = \left( V_1 \cap V_2, E_1 \cap E_2 \right)$。

容易证明两个无向简单图的交还是无向简单图。

**并 (union)**：图 $G = \left( V_1, E_1 \right), H = \left( V_2, E_2 \right)$ 的并定义成图 $G \cup H = \left( V_1 \cup V_2, E_1 \cup E_2 \right)$。

**和 (sum)/直和 (direct sum)**：对于 $G = \left( V_1, E_1 \right), H = \left( V_2, E_2 \right)$，任意构造 $H’ \cong H$ 使得 $V \left( H’ \right) \cap V_1 = \varnothing$($H’$ 可以等于 $H$)。此时与 $G \cup H’$ 同构的任何图称为 $G$ 和 $H$ 的和/直和/不交并，记作 $G + H$ 或 $G \oplus H$。

若 $G$ 与 $H$ 的点集本身不相交，则 $G \cup H = G + H$。

比如，森林可以定义成若干棵树的和。

可以理解为，「并」会让两张图中「名字相同」的点、边合并，而「和」则不会。

参考资料

图论相关概念 - OI Wiki

OI 中转站 - 图论概念梳理

Wikipedia（以及相关概念的对应词条）

离散数学（修订版），田文成 周禄新 编著，天津文学出版社，P184-187

戴一奇，胡冠章，陈卫。图论与代数结构 [M]. 北京：清华大学出版社，1995.

图的存储方法

前面4个为常用存图方法

邻接矩阵

写法最简单，但是耗费空间较大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int g[N][N];

void dfs(int u) {
    for (int i = 1; i <= n; i ++ ) {
        int v = g[u][i];
        dfs(v);
    }
}

int main() {
    for (int i = 1; i <= n; i ++ ) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = c;
        // g[a][b] = c;
    }
}

vector模拟邻接表2

利用动态数组优化代码逻辑的邻接表

适用性较强，应用面较广，还能实现一些边的排序功能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 不带边权的图的存储和dfs
std::vector<int> g[N];

void dfs(int u) {
    for (auto v: g[u]) {
        dfs(v);
    }
}

int main() {
    cin >> m;
	while (m --) {
        int a, b;
  		cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
}

// 带边权的图的存储和dijkstra求最短路
struct Edge {
    int v, w;
};
std::vector<Edge> g[N];
int dist[N];
bool st[N];

void dijkstra() {
    memset(dist, 0x3f, sizeof(dist));
    memset(st, false, sizeof(st));
    std::priority_queue<int, std::vector<int>, std::greater<int>> q;
    q.push({0, 1});
    while (q.size()) {
        auto [d, u] = q.front();
        q.pop();
        if (st[u]) continue;
        st[u] = true;
        for (auto v: g[u]) {
            if (dist[v] > d + u) {
                dist[v] = d + u;
                q.push(v);
            }
        }
    }
}

int main() {
    cin >> m;
    while (m --) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});	// 只加正向边有向图
        g[b].push_back({a, c});	// 加反向边无向图
    }
}

链式前向星

通过增加节点头指针数组，通过起点快速定位某些边

能够快速找到反向边，一般在网络流问题中用到较多，通用性也较强，缺点是不能对边权进行排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const int N = 1e5 + 10;	// N 是点数
const int M = 2e5 + 10; // M 是边数

int h[N], ne[M], e[M], w[M], idx;

// 带边权存
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

// 不带边权存
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int main() {
    cin >> m;
    memset(h, -1, sizeof(h));	// 将所有表头初始化成-1，如果ne[u]指向的是-1，则说明该点的边已经遍历完了
    while (m --) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);	// 只加正向边有向图
        add(b, a, c);	// 正反都加则是无向图
    }
}

只存边

直接按把边的信息丢到一个结构体里，用数组存所有的边，一般用于最小生成树和需要多次建图的题目中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
const int M = 1e5 + 10;

struct Edge {
    int u, v, w;
    bool operator<(const Edge &e) const {
        return w < e.w;
    }
}edges[M];

// 并查集
int dsu[N];
// 并查集查找祖先
int find(int x) {
	if (x == dsu[x]) return x;
    return dsu[x] = find(dsu[x]);
}
// 初始化并查集
void init_dsu(int n) {
    for (int i = 1; i <= n; i ++ ) dsu[i] = i;
}

void kruskal() {
    init_dsu();
    
    int cnt = 0;
    for (int i = 1; i <= m; i ++ ) {
        auto [u, v, _] = edges[i];
        a = find(u), b = find(v);
        if (a == b) continue;
        dsu[a] = b;
        cnt ++;
        if (cnt == n - 1) break;
    }
}

int main() {
    cin >> m;
    for (int i = 1; i <= m; i ++ ) cin >> edges[i].u >> edges[i].v >> edges[i].w;
    std::sort(edges + 1, edges + m + 1);
    
    kruskal();
}

前向星

利用链表存边

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>
using namespace std;
struct Node {
    int v, next;
} E[100001];
int p[100001], eid = 0;
inline void insert(int u, int v) {
    eid++;
    E[eid].v = v;
    E[eid].next = p[u];
    p[u] = eid;
}

邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define MVNum 100                //最大顶点数
typedef struct ArcNode           //边结点
{
	int adjvex;                  //该边所指向的顶点的位置
	struct ArcNode *nextarc;     //指向下一条边的指针
	OtherInfo info;              //和边相关的信息(权值等)
}ArcNode;

typedef struct
{
	AdjList vertices;      //存放各个顶点的数组
	int vexnum, arcnum;    //图的当前顶点数和弧数
}ALGraph;

树的相关概念

引入

图论中的树和现实生活中的树长得一样，只不过我们习惯于处理问题的时候把树根放到上方来考虑。这种数据结构看起来像是一个倒挂的树，因此得名。

定义

一个没有固定根结点的树称为无根树（unrooted tree）。无根树有几种等价的形式化定义：

  • 有 $n$ 个结点，$n-1$ 条边的连通无向图

  • 无向无环的连通图

  • 任意两个结点之间有且仅有一条简单路径的无向图

  • 任何边均为桥的连通图

  • 没有圈，且在任意不同两点间添加一条边之后所得图含唯一的一个圈的图

在无根树的基础上，指定一个结点称为根，则形成一棵有根树（rooted tree）。有根树在很多时候仍以无向图表示，只是规定了结点之间的上下级关系，详见下文。

有关树的定义

适用于无根树和有根树

-森林（forest）：每个连通分量（连通块）都是树的图。按照定义，一棵树也是森林。

-生成树（spanning tree）：一个连通无向图的生成子图，同时要求是树。也即在图的边集中选择 $n - 1$ 条，将所有顶点连通。

-无根树的叶结点（leaf node）：度数不超过 $1$ 的结点。

question “ 为什么不是度数恰为 $1$？”
考虑 $n = 1$。

-有根树的叶结点（leaf node）：没有子结点的结点。

只适用于有根树

  • 父亲（parent node）：对于除根以外的每个结点，定义为从该结点到根路径上的第二个结点。
    根结点没有父结点。
  • 祖先（ancestor）：一个结点到根结点的路径上，除了它本身外的结点。
    根结点的祖先集合为空。
  • 子结点（child node）：如果 $u$ 是 $v$ 的父亲，那么 $v$ 是 $u$ 的子结点。
    子结点的顺序一般不加以区分，二叉树是一个例外。
  • 结点的深度（depth）：到根结点的路径上的边数。
  • 树的高度（height）：所有结点的深度的最大值。
  • 兄弟（sibling）：同一个父亲的多个子结点互为兄弟。
  • 后代（descendant）：子结点和子结点的后代。
    或者理解成：如果 $u$ 是 $v$ 的祖先，那么 $v$ 是 $u$ 的后代。

tree-definition.svg

-子树（subtree）：删掉与父亲相连的边后，该结点所在的子图。

tree-definition-subtree.svg

特殊的树

-链（chain/path graph）：满足与任一结点相连的边不超过 $2$ 条的树称为链。

-菊花/星星（star）：满足存在 $u$ 使得所有除 $u$ 以外结点均与 $u$ 相连的树称为菊花。

-有根二叉树（rooted binary tree）：每个结点最多只有两个儿子（子结点）的有根树称为二叉树。常常对两个子结点的顺序加以区分，分别称之为左子结点和右子结点。
大多数情况下，二叉树一词均指有根二叉树。

-完整二叉树（full/proper binary tree）：每个结点的子结点数量均为 0 或者 2 的二叉树。换言之，每个结点或者是树叶，或者左右子树均非空。

-完全二叉树（complete binary tree）：只有最下面两层结点的度数可以小于 2，且最下面一层的结点都集中在该层最左边的连续位置上。

-完美二叉树（perfect binary tree）：所有叶结点的深度均相同，且所有非叶节点的子节点数量均为 2 的二叉树称为完美二叉树。

Proper binary tree 的汉译名称不固定，且完全二叉树和满二叉树的定义在不同教材中定义不同，遇到的时候需根据上下文加以判断。

OIers 所说的「满二叉树」多指完美二叉树。

存储

只记录父结点

用一个数组 parent[N] 记录每个结点的父亲结点。

这种方式可以获得的信息较少，不便于进行自顶向下的遍历。常用于自底向上的递推问题中。

邻接表

  • 对于无根树：为每个结点开辟一个线性列表，记录所有与之相连的结点。
1
std::vector<int> adj[N];

  • 对于有根树：

    • 方法一：若给定的是无向图，则仍可以上述形式存储。下文将介绍如何区分结点的上下关系。

    • 方法二：若输入数据能够确保结点的上下关系，则可以利用这个信息。为每个结点开辟一个线性列表，记录其所有子结点；若有需要，还可在另一个数组中记录其父结点。

1
2
std::vector<int> children[N];
int parent[N];

当然也可以用其他方式（如链表）替代 std::vector。

左孩子右兄弟表示法

过程

对于有根树，存在一种简单的表示方法。

首先，给每个结点的所有子结点任意确定一个顺序。

此后为每个结点记录两个值：其第一个子结点 child[u] 和其下一个兄弟结点 sib[u]。若没有子结点，则 child[u] 为空；若该结点是其父结点的最后一个子结点，则 sib[u] 为空。

实现

遍历一个结点的所有子结点可由如下方式实现。

1
2
3
4
5
6
7
int v = child[u];  // 从第一个子结点开始
while (v != EMPTY_NODE) {
  // ...
  // 处理子结点 v
  // ...
  v = sib[v];  // 转至下一个子结点，即 v 的一个兄弟
}

也可简写为以下形式。

1
2
3
4
5
for (int v = child[u]; v != EMPTY_NODE; v = sib[v]) {
  // ...
  // 处理子结点 v
  // ...
}

二叉树

需要记录每个结点的左右子结点。

实现

1
2
3
4
int parent[N];
int lch[N], rch[N];
// -- or --
int child[N][2];

树的遍历

树上 DFS

在树上 DFS 是这样的一个过程：先访问根节点，然后分别访问根节点每个儿子的子树。

可以用来求出每个节点的深度、父亲等信息。

二叉树 DFS 遍历

先序遍历

preorder

按照根，左，右的顺序遍历二叉树。

实现

1
2
3
4
5
6
7
void preorder(BiTree* root) {
    if (root) {
        cout << root->key << " ";
        preorder(root->left);
        preorder(root->right);
    }
}

中序遍历

inorder

按照左，根，右的顺序遍历二叉树。

实现

1
2
3
4
5
6
7
void inorder(BiTree* root) {
    if (root) {
        inorder(root->left);
        cout << root->key << " ";
        inorder(root->right);
    }
}

后序遍历

postorder

按照左，右，根的顺序遍历二叉树。

实现

1
2
3
4
5
6
7
void postorder(BiTree* root) {
    if (root) {
        postorder(root->left);
        postorder(root->right);
        cout << root->key << " ";
    }
}

反推

已知中序遍历序列和另外一个序列可以求第三个序列。

reverse

  1. 前序的第一个是 root，后序的最后一个是 root。
  2. 先确定根节点，然后根据中序遍历，在根左边的为左子树，根右边的为右子树。
  3. 对于每一个子树可以看成一个全新的树，仍然遵循上面的规律。

树上 BFS

从树根开始，严格按照层次来访问节点。

BFS 过程中也可以顺便求出各个节点的深度和父亲节点。

树的层序遍历

树层序遍历是指按照从根节点到叶子节点的层次关系，一层一层的横向遍历各个节点。根据 BFS 的定义可以知道，BFS 所得到的遍历顺序就是一种层序遍历。但层序遍历要求将不同的层次区分开来，所以其结果通常以二维数组的形式表示。

例如，下图的树的层序遍历的结果是 [[1], [2, 3, 4], [5, 6]]（每一层从左向右）。

tree-basic-levelOrder

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<vector<int>> levelOrder(Node* root) {
    if (!root) {
        return {};
    }
    vector<vector<int>> res;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        int currentLevelSize = q.size();  // 当前层的节点个数
        res.push_back(vector<int>());
        for (int i = 0; i < currentLevelSize; ++i) {
            Node* cur = q.front();
            q.pop();
            res.back().push_back(cur->val);
            for (Node* child : cur->children) {  // 把子节点都加入
                q.push(child);
            }
        }
    }
    return res;
}

二叉树 Morris 遍历

二叉树遍历的核心问题是，当遍历当前节点的子节点后，如何返回当前节点并继续遍历。遍历二叉树的递归方法和非递归方法都使用了栈结构，记录返回路径，来实现从下层到上层的移动。其空间复杂度最好时为 $O(\log n)$，最坏时为 $O(n)$（二叉树呈线性）。

Morris 遍历的实质是避免使用栈，利用底层节点空闲的 right 指针指回上层的某个节点，从而完成下层到上层的移动。

Morris 遍历的过程

假设来到当前节点 cur，开始时来到根节点位置。

  1. 如果 cur 为空时遍历停止，否则进行以下过程。
  2. 如果 cur 没有左子树，cur 向右移动（cur = cur->right）。
  3. 如果 cur 有左子树，找到左子树上最右的节点，记为 mostRight。
    • 如果 mostRight 的 right 指针指向空，让其指向 cur，然后 cur 向左移动（cur = cur->left）。
    • 如果 mostRight 的 right 指针指向 cur，将其修改为 null，然后 cur 向右移动（cur = cur->right）。

例如，cur 从节点 1 开始访问。

tree-basic-morris-1

cur 第一次访问节点 2 时，找到左子树上最右的节点 4，将 4 的 right 指针指向 cur（节点 2)。

tree-basic-morris-2

cur 通过 4 的 right 指针返回上层，第二次访问节点 2 时，找到左子树上最右节点 4，将 4 的 right 指针修改为 null，然后继续访问右子树。之后的过程省略。

tree-basic-morris-1

整棵树的访问顺序是 1242513637。可以发现有左子树的节点访问两次，没有左子树的节点只访问一次。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void morris(TreeNode* root) {
    TreeNode* cur = root;
    while (cur) {
        if (!cur->left) {
            // 如果当前节点没有左子节点，则输出当前节点的值并进入右子树
            std::cout << cur->val << " ";
            cur = cur->right;
            continue;
        }
        // 找到当前节点的左子树的最右节点
        TreeNode* mostRight = cur->left;
        while (mostRight->right && mostRight->right != cur) {
            mostRight = mostRight->right;
        }
        if (!mostRight->right) {
            // 如果最右节点的right指针为空，将其指向当前节点，并进入左子树
            mostRight->right = cur;
            cur = cur->left;
        } else {
            // 如果最右节点的right指针指向当前节点，说明左子树已经遍历完毕，输出当前节点的值并进入右子树
            mostRight->right = nullptr;
            std::cout << cur->val << " ";
            cur = cur->right;
        }
    }
}

无根树

过程

树的遍历一般为深度优先遍历，这个过程中最需要注意的是避免重复访问结点。

由于树是无环图，因此只需记录当前结点是由哪个结点访问而来，此后进入除该结点外的所有相邻结点，即可避免重复访问。

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int u, int from) {
    // 递归进入除了 from 之外的所有子结点
    // 对于出发结点，from 为空，故会访问所有相邻结点，这与期望一致
    for (int v : adj[u])
        if (v != from) {
            dfs(v, u);
        }
}
// 开始遍历时
int EMPTY_NODE = -1;  // 一个不存在的编号
int root = 0;         // 任取一个结点作为出发点
dfs(root, EMPTY_NODE);

有根树

对于有根树，需要区分结点的上下关系。

考察上面的遍历过程，若从根开始遍历，则访问到一个结点时 from 的值，就是其父结点的编号。

通过这个方式，可以对于无向的输入求出所有结点的父结点，以及子结点列表。

本页面部分内容引用自博文 二叉树：前序遍历、中序遍历、后续遍历，遵循 CC 4.0 BY-SA 版权协议。

#算法 #ACM #图论 #树
图论基础
https://www.lry666.cn/posts/3b61/
作者
LRY666
发布于
2024年11月9日
许可协议