图论理论基础和存储方式的实现

图论1

图论 (Graph theory) 是数学的一个分支，图是图论的主要研究对象。图 (Graph) 是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。

1、图的理论基础

图（Graph）

​ 用大写字母（如 $G$）表示图，通常记为 $G=(V,E)$，其中 $V$ 表示顶点集，$E$ 表示边集。例如：设 $G=(V,E)$ 是一个无向图，$V$ 包含多个顶点，$E$ 包含连接这些顶点的边。

相邻（Adjacent）

​ 若顶点 $u$ 和 $v$ 相邻，可表示为：$u\sim v$。例如：在图 $G$ 中，若顶点 $u$ 和 $v$ 之间有边相连，则有 $u\sim v$。

简单图（Simple Graph）

​ 设 $G=(V,E)$ 为简单图，特点是不存在自环（即不存在边 $e=(u,u)$，$u\in V$）和多重边（任意两顶点间不存在多条相同边），可描述为：$G=(V,E)$ 是简单图，满足无自环与多重边条件。

度数（Degree）

• 无向图中顶点度数：无向图里顶点 $v$ 的度数用 $\mathrm{deg}(v)$ 表示，比如：在无向图 $G$ 中，顶点 $v$ 的度数记为 $\mathrm{deg}(v)$，其值等于与 $v$ 相连的边的数量。

• 有向图中顶点度数：有向图中顶点 $v$ 的入度表示为 $\text{indeg}(v)$，出度表示为 $\text{outdeg}(v)$。例如：在有向图 $G$ 中，顶点 $v$ 的入度为 $\text{indeg}(v)$，出度为 $\text{outdeg}(v)$，度数可结合二者考量。

路径（Path）

​ 用 $P=(v_0,v_1,\cdots ,v_n)$ 表示从顶点 $v_0$ 出发，依次经过 $v_1,\cdots ,v_n$ 这些顶点的路径。例如：在图 $G$ 中，存在路径 $P=(v_1,v_2,v_3)$，即从顶点 $v_1$ 出发，依次经过 $v_2$ 和 $v_3$ 的路线。

子图（Subgraph）

设 $G=(V,E)$ 是原图，$G'=(V',E')$ 是它的子图，关系表示为：$V'\subseteq V$ 且 $E'\subseteq E$，同时 $E'$ 中边的端点都在 $V'$ 中，则 $G'=(V',E')$ 为 $G$ 的子图。

​ 比如：已知图 $G=(V,E)$，取 $V^{\prime }$ 为 $V$ 的部分顶点集，$E^{\prime }$ 为相应连接这些顶点的部分边集，满足条件后，$G^{\prime }=(V^{\prime },E^{\prime })$ 就是 $G$ 的子图。

连通（Connected）

• 无向图连通：设 $G=(V,E)$ 为无向图，若对任意 $u,v\in V$，都存在一条路径连接 $u$ 和 $v$，则称 $G$ 是连通的，可写成：$\forall u,v\in V$，存在路径连接 $u$ 与 $v$，则 $G$ 连通。

• 有向图连通相关（强连通和弱连通）：

  • 强连通：对于有向图 $G=(V,E)$，若对任意 $u,v\in V$，都存在从 $u$ 到 $v$ 的有向路径以及从 $v$ 到 $u$ 的有向路径，则 $G$ 是强连通的，即：$\forall u,v\in V$，存在从 $u$ 到 $v$ 及从 $v$ 到 $u$ 的有向路径，则 $G$ 强连通。

  • 弱连通：若把有向图 $G=(V,E)$ 的边看作无向边时图是连通的，则 $G$ 是弱连通的，表示为：将有向图 $G=(V,E)$ 的边视为无向边时图连通，则 $G$ 弱连通。

无向图（Undirected Graph）

直接用 $G=(V,E)$ 表示无向图，并说明其边无方向特点。

​ 如：$G=(V,E)$ 为无向图，其边没有方向，即对边 $e=(u,v)\in E$，$u$ 与 $v$ 的关系是对称的。

有向图（Directed Graph）

​ 用 $G=(V,E)$ 表示有向图，强调边有方向。

​ 例如：$G=(V,E)$ 为有向图，边 $e=(u,v)\in E$ 有方向，从 $u$ 指向 $v$，表示一种单向关系。

割（Cut）

• 边割（针对无向图）：设 $G=(V,E)$ 是连通无向图，若存在边子集 $E^{\prime }\subseteq E$，去掉 $E^{\prime }$ 后使得图不再连通，则 $E^{\prime }$ 是 $G$ 的一个边割，可表示为：$G=(V,E)$ 连通无向图，$\exists E^{\prime }\subseteq E$，去掉 $E^{\prime }$ 后 $G$ 不连通，则 $E^{\prime }$ 为 $G$ 的边割。

• 点割（针对无向图）：对于连通无向图 $G=(V,E)$，若存在顶点子集 $V^{\prime }\subseteq V$，去掉 $V^{\prime }$ 以及和这些顶点相关联的边后使得图不再连通，则 $V^{\prime }$ 是 $G$ 的一个点割，写成：$G=(V,E)$ 连通无向图，$\exists V^{\prime }\subseteq V$，去掉 $V^{\prime }$ 及相关边后 $G$ 不连通，则 $V^{\prime }$ 为 $G$ 的点割。

稀疏图/稠密图（Sparse Graph / Dense Graph）

• 稀疏图：对于图 $G=(V,E)$，若 $|E|\ll |V{|}^2$（这里 $\ll$ 示意边数量远小于顶点数量平方的大概关系），则 $G$ 为稀疏图，如：$G=(V,E)$，当 $|E|\ll |V{|}^2$ 时，$G$ 为稀疏图。

• 稠密图：与稀疏图对应，若 $|E|$ 接近 $|V{|}^2$ 量级，可写成：$G=(V,E)$，当 $|E|$ 接近 $|V{|}^2$ 时，$G$ 为稠密图。

补图（Complement Graph）

​ 设 $G=(V,E)$ 是无向简单图，其补图 $\overline{G}=(V,\overline{E})$，其中 $\overline{E}$ 包含了所有不在 $E$ 中但两端点在 $V$ 中的边，可表示为：$G=(V,E)$ 为无向简单图，其补图 $\overline{G}=(V,\overline{E})$，$\overline{E}=\{(u,v)\mid u,v\in V,(u,v)\notin E\}$。

反图（Inverse Graph）

​ 对于有向图 $G=(V,E)$，其反图 $G^{-1}=(V,E^{-1})$，这里 $E^{-1}$ 是把 $E$ 中每条边的方向都反转所得到的边集，写成：$G=(V,E)$ 为有向图，其反图 $G^{-1}=(V,E^{-1})$，$E^{-1}=\{(v,u)\mid (u,v)\in E\}$。

特殊的图

完全图（Complete Graph）：

• 无向完全图：用 $K_n$ 表示 $n$ 个顶点的无向完全图，其边数为 $\frac{n(n-1)}{2}$。例如：$K_5$ 是有 $5$ 个顶点的无向完全图，边数为 $\frac{5\times (5-1)}{2}=10$。
• 有向完全图：用 $D_n$ 表示 $n$ 个顶点的有向完全图，其边数为 $n(n-1)$。
• 树（Tree）：树可描述为无向连通且无环的图，记为：$T=(V,E)$ 为树，即 $T$ 是无向连通且无环的图。
• 二分图（Bipartite Graph）：设顶点集 $V$ 可分成两个互不相交的子集 $V_1$ 和 $V_2$，使图中每条边的两个端点分别属于 $V_1$ 和 $V_2$，可写成：$G=(V,E)$ 为二分图，$\exists V_1,V_2\subseteq V$，$V_1\cap V_2=\varnothing$，且 $\forall e=(u,v)\in E$，$u\in V_1$ 且 $v\in V_2$ 或 $u\in V_2$ 且 $v\in V_1$。

同构（Isomorphism）

​ 设 $G=(V,E)$ 和 $G^{\prime }=(V^{\prime },E^{\prime })$ 是两个图，若存在双射函数 $f:V\to V^{\prime }$，使得对于任意的 $u,v\in V$，$(u,v)\in E$ 当且仅当 $(f(u),f(v))\in E^{\prime }$，则称 $G$ 和 $G^{\prime }$ 是同构的，表示为：$G=(V,E)$，$G^{\prime }=(V^{\prime },E^{\prime })$，若 $\exists f:V\to V^{\prime }$ 双射，满足 $\forall u,v\in V$，$(u,v)\in E\iff (f(u),f(v))\in E^{\prime }$，则 $G$ 与 $G^{\prime }$ 同构。

无向简单图的二元运算

并运算（Union）：设 $G_1=(V_1,E_1)$ 和 $G_2=(V_2,E_2)$ 是两个无向简单图，它们的并 $G_1\cup G_2=(V_1\cup V_2,E_1\cup E_2)$，可写成：$G_1=(V_1,E_1)$，$G_2=(V_2,E_2)$，则 $G_1\cup G_2=(V_1\cup V_2,E_1\cup E_2)$。例如：已知 $G_1$ 和 $G_2$ 两个无向简单图，计算它们的并图 $G_1\cup G_2$。

交运算（Intersection）：$G_1\cap G_2=(V_1\cap V_2,E_1\cap E_2)$，表示为：$G_1=(V_1,E_1)$，$G_2=(V_2,E_2)$，则 $G_1\cap G_2=(V_1\cap V_2,E_1\cap E_2)$。

差运算（Difference）：$G_1-G_2=(V_1,E_1-E_2)$，写成：$G_1=(V_1,E_1)$，$G_2=(V_2,E_2)$，则 $G_1-G_2=(V_1,E_1-E_2)$。

特殊的点集/边集

支配集（Dominating Set）

​ 在无向图 $G=(V,E)$ 中，顶点子集 $D\subseteq V$ 称为支配集，若对任意顶点 $v\in V-D$，都存在顶点 $u\in D$ 使得 $u$ 和 $v$ 相邻，可表示为：$G=(V,E)$ 无向图，$\exists D\subseteq V$，$\forall v\in V-D$，$\exists u\in D$，$u\sim v$，则 $D$ 为支配集。

边支配集（Edge Dominating Set）

​ 在无向图 $G=(V,E)$ 中，边子集 $F\subseteq E$ 称为边支配集，若对任意边 $e\in E-F$，都存在边 $f\in F$ 与 $e$ 相邻（共享端点），写成：$G=(V,E)$ 无向图，$\exists F\subseteq E$，$\forall e\in E-F$，$\exists f\in F$，$e$ 与 $f$ 共享端点，则 $F$ 为边支配集。

独立集（Independent Set）

​ 在无向图 $G=(V,E)$ 中，顶点子集 $I\subseteq V$ 称为独立集，若 $I$ 中任意两个顶点都不相邻，即：$G=(V,E)$ 无向图，$\exists I\subseteq V$，$\forall u,v\in I$，$u$ 与 $v$ 不相邻，则 $I$ 为独立集。

匹配（Matching）

​ 在无向图 $G=(V,E)$ 中，边子集 $M\subseteq E$ 称为匹配，若 $M$ 中的边两两之间没有公共端点，可表示为：$G=(V,E)$ 无向图，$\exists M\subseteq E$，$\forall e_1,e_2\in M$，$e_1$ 与 $e_2$ 无公共端点，则 $M$ 为匹配。

点覆盖（Vertex Cover）

​ 在无向图 $G=(V,E)$ 中，顶点子集 $C\subseteq V$ 称为点覆盖，若图 $G$ 中的每条边至少有一个端点在 $C$ 中，写成：$G=(V,E)$ 无向图，$\exists C\subseteq V$，$\forall e\in E$，$\exists v\in C$，$v$ 为 $e$ 的端点，则 $C$ 为点覆盖。

边覆盖（Edge Cover）

​ 在无向图 $G=(V,E)$ 中，边子集 $L\subseteq E$ 称为边覆盖，若对于任意顶点 $v\in V$，都存在边 $e\in L$ 使得 $v$ 是 $e$ 的端点，可表示为：$G=(V,E)$ 无向图，$\exists L\subseteq E$，$\forall v\in V$，$\exists e\in L$，$v$ 为 $e$ 的端点，则 $L$ 为边覆盖。

团（Clique）

​ 在无向图 $G=(V,E)$ 中，顶点子集 $K\subseteq V$ 称为团，若 $K$ 中任意两个顶点都相邻，即 $K$ 所诱导出的子图是完全图，可表示为：$G=(V,E)$ 无向图，$\exists K\subseteq V$，$\forall u,v\in K$，$u\sim v$，则 $K$ 为团。

图的矩阵表示(存储方式)

邻接矩阵（Adjacency Matrix）

对于一个无向图 $G=(V,E)$ ，设顶点集 V = { v 1 , v 2 , ⋯ , v n } V = \{v_1, v_2, \cdots, v_n\} V={v1​,v2​,⋯,vn​}，其邻接矩阵 $A$ 是一个 $n\times n$ 的矩阵，其中元素 $a_{ij}$ 定义为：若顶点 $v_i$ 和 $v_j$ 相邻，则 $a_{ij}=1$（对于无向简单图）；若不相邻，则 $a_{ij}=0$。

用公式表示为：$a_{ij}=\{\begin{array}{ll}1,& v_i\sim v_j\text{相邻}\\ 0,& v_i\sim v_j\text{不相邻}\end{array}$

例如，对于一个简单的三角形形状的无向图，其邻接矩阵为：$\left(\begin{array}{ccc}0& 1& 1\\ 1& 0& 1\\ 1& 1& 0\end{array}\right)$。

对于有向图，若存在从顶点 $v_i$ 指向 $v_j$ 的边，则 $a_{ij}=1$，否则 $a_{ij}=0$。其邻接矩阵能反映出有向图中顶点之间的有向连接关系。

关联矩阵（Incidence Matrix）

设无向图 $G=(V,E)$ ，顶点集 V = { v 1 , v 2 , ⋯ , v n } V = \{v_1, v_2, \cdots, v_n\} V={v1​,v2​,⋯,vn​}，边集 E = { e 1 , e 2 , ⋯ , e m } E = \{e_1, e_2, \cdots, e_m\} E={e1​,e2​,⋯,em​}，其关联矩阵 $M$ 是一个 $n\times m$ 的矩阵，元素 $m_{ij}$ 定义如下：若顶点 $v_i$ 与边 $e_j$ 关联（即 $v_i$ 是 $e_j$ 的一个端点），则 $m_{ij}=1$；若不关联，则 $m_{ij}=0$。

用公式表示为：$m_{ij}=\{\begin{array}{ll}1,& \text{如果}{v}_i\text{关联}{e}_j\\ 0,& \text{如果}{v}_i\text{不关联}{e}_j\end{array}$

例如，对于一个简单的有四条边、三个顶点的无向图，其关联矩阵可能为：$\left(\begin{array}{cccc}1& 1& 0& 0\\ 1& 0& 1& 1\\ 0& 1& 1& 0\end{array}\right)$ 。 有向图的关联矩阵定义稍有不同，对于有向边 $e_j$ ，若顶点 $v_i$ 是边 $e_j$ 的起点，则 $m_{ij}=1$；若 $v_i$ 是边 $e_j$ 的终点，则 $m_{ij}=-1$；若 $v_i$ 与 $e_j$ 不关联，则 $m_{ij}=0$。

2、图的存储

n为图的顶点数，m为图的边数，$d^{+}(u)$为点u的出度，$d^{-}(u)$为点u的入度

2.1、直接存边

实现：

使用多个数组来存储变得起点终点和权值。

复杂度：

查询是否存在某条边：$O(m)$

遍历一个点的所有出边：$O(m)$

遍历整张图：$O(nm)$

空间复杂度：$O(m)$

注：在Kruskal算法中，需要把边按权值排序，需要直接存储边。

2.2、邻接矩阵

实现：

使用二维数组 $adj[u][v]$ 来存储，$adj[u][v]$的值表示 $u$ 到 $v$ 是否有边。

用公式表示为：$adj[u][v]=\{\begin{array}{cc}1& ,存在u到v的边\\ 0& ,不存在u到v的边\end{array}$

代码

复杂度：

查询是否存在某条边：$O(1)$

遍历一个点的所有出边：$O(n)$

遍历整张图：$O(n^2)$

空间复杂度：$O(n^2)$

邻接矩阵只适用于没有重边的图

由于邻接矩阵在稀疏图上效率很低（尤其是在点数较多的图上，空间无法承受），所以一般只会在稠密图上使用邻接矩阵。

2.3、邻接表

2.4、链式前向星