%% # 纲要 > 主干纲要、Hint/线索/路标 # Q&A #### 已明确 #### 待明确 > 当下仍存有的疑惑 **❓<font color="#c0504d"> 有什么问题？</font>** # Buffer ## 闪念 > sudden idea ## 候选资料 > Read it later %% # 图的基本概念 ## 图定义 图可公式化描述为： $G=(V;E)$，由 "**顶点 Vertex**" 与 "**边 edge**" 构成。 - $V$ 为**顶点集**，顶点数量为 $n=|V|$； - $E$ 为**边集**，边数量为 $e=|E|$； #### 边的类型 - 无向边：$e=(u,v)$ - 有向边：$e=(u,v)$，**从 $u$ 指向 $v$**，起点 $u$ 称为尾（tail），终点 $v$ 称为头（head）。 #### 顶点、边之间关系 - **邻接关系**（adjacency）：$v \sim v$ ，**==两个相邻顶点==** 之间的关系。邻接矩阵表示为 $|V|\times|V|$ - **关联关系**（incidence）：$v\sim e$ ，**==顶点与其连边==** 之间的关系。关联矩阵表示为 $|V|\times |E|$ <br> ## 路径定义 **路径（path）** ——由一系列**相邻顶点**构成的**序列**，表示为 $\pi =<v_0, v_1,\dots,v_k>$ 。路径长度 $|\pi|=k$，即经历的**边的数量**。 ##### 路径类型 - **简单路径**（simple path）：**不含重复顶点**的路径，即为简单路径； - **环路**（cycle path）：路径的**起点和终点相同**，$v_0=v_k$。 - 简单环路：路径上不包含重复顶点的环路。 - **自环**（self-loop）：同一顶点自我邻接 - **欧拉环路**（Eulerian Tour）：覆盖**图中所有==边==**，且各条边恰好出现一次的环路。 - **哈密尔顿环路**（Hamiltonian Tour）：覆盖**图中所有==顶点==**，且各顶点恰好出现一次的环路。 > [!example] 示例：欧拉环路：lt;A,D,B,A,B,C,D,C,A>$ >  > > [!example] 示例：哈密尔顿环路：lt;A,D,B,C>$ >  > <br> <br> # 图的分类 - 根据**边**是否**有方向**进行划分： - **有向图** - **无向图** - **混合图** - 根据图中**是否有环**： - 无环图：不含环路，称为**无环图**（acyclic） - 根据图是否连通： - **连通图** / **强连通图** / 非连通图 ##### 常见的特殊图 - **有向无环图**（Dynamic Acyclic Graph，**DAG**）：**不包含任何环路**的有向图 <br><br> # 连通图相关 - 对于无向图： - **连通图**：若无向图中任意两点之间均在 **==路径==**，则称之为 "**连通图**"； - **双连通图**：包括两种类型 - **点双连通图**：不存在**割点**的连通图——即删去**任意一个顶点及其连边**后，仍然是连通图的，称之为点双连通图； - **边双连通图**：不存在**割边**的连通图——即删去**任意一条边**之后，仍然是连通图的，称之为边双连通图。 - 对于有向图： - **强连通图** ## 非连通图 **非连通图**：存在**多个连通分量**的图。 从非连通图中某个顶点出发，**只能访问到该节点所属连通分量中的所有顶点**，而不能访问到别的连通分量中的顶点。 <br> ## 连通图（无向图） ### 连通图、连通分量 - **连通图**：图中**任意两个不同的顶点之间均存在路径**，则称为 **==连通图==**（connected）。 - 对于连通图，从图中任一顶点出发进行图遍历，可以访问到图的所有顶点。 - **连通分量**：无向图 $G$ 中的每一个 **==极大==连通子图** 称为 $G$ 的**连通分量**。 - 任何**连通图**的连通分量只有一个，即其自身； <br> ### 生成树 | 支撑树 **生成树 / 支撑树（Spanning Tree）**：**连通图**中，覆盖 **==所有顶点==** 的树（无环连通子图）。 说明： - 具有 $n$ 个顶点的连通图，其**生成树包含全部 $n$ 个顶点，具有 $n-1$ 条边**； - 同一连通图的 **==生成树可能不唯一==**（顶点集相同，但**边集不同**）； #### 最小生成树 - **最小生成树 / 最小支撑树** ：**连通图**中，覆盖 **==所有顶点==**，且 **==边的总权重之和最小==的支撑树**。 <br> ### 搜索树 **搜索树**：在一个**无向连通图**中，从某一顶点 `u` 出发进行**DFS 搜索**，且限制**每一个节点==只访问一次==**（不重复访问同一节点），则 DFS 结束后将得到该连通图的一棵 "**搜索树**"（**由所有被访问过的节点与边构成**），该搜索树也即是一棵 "**==生成树==**"。  ### 割点 **无向图**的 **==割点==**（Articulation Points）：**删除该节点及其关联的边**后，**原图**的**连通分量增多**。 **割点** 至少要与两个节点连通（否则删除后连通分量不可能增加）： - 树的叶节点不可能是割点 - 树的根节点，**若其出度大于 1 则该根节点是割点**。 ### 割边 | 桥 **无向图**的**割边**（Bridge）：若删除边 $e$ 之后，图将**分裂成两个不相连的子图**，那么称 $e$ 为该无向图的**桥**或**割边**。 > [!example] > 下图中的 "A-B" 边即为**割边**。 > > ![[_attachment/00-数据结构与算法笔记/数据结构/图.assets/IMG-图-FBE9579E7BBFFD8B9A903E570A36545D.png|390]] > [!caution] **有割点不一定有割边，有割边则一定存在割点**（割边一定是割点依附的边） > > 示例：下图中，**顶点 C 为割点**，但**与 C 相连的边都不是割边**。 > >  <br> ## 双连通图 双连通图：一个连通且"不可分离"的**无向图**，分为"点双连通" 与 "边双连通"两种： - **点双连通**图：**删去任意一个顶点（及其连边）后，剩余子图仍然是连通图，即==不存在割点==，则称为点双连通图**。 - **边双连通**图：**删去任意一条连边后，剩余子图仍然是连通图，即==不存在桥（割边）==，则称为边双连通图**。 > [!example] > > 下面两个连通图，**既是点双连通图，也是边双连通图**。 > >  <br> ## 双连通分量 **双连通分量**（Bi-Connected Components）：无向图中的每一个**极大双连通子图**，称为双连通分量。 - **边**双连通分量：一个极大的 "**边双连通**" 子图。 - 无向图中，**==连接==两个"边双连通分量"的边即是桥**。 - **点**双连通分量：一个极大的 "**点双连通**" 子图 - 无向图中，**一个割点==属于==多个"点双连通分量"**。 ##### 双连通分量相关性质 - 点双连通分量一定是边双连通分量，反之不一定。 - 两个**点双连通分量**之间可以**有公共点**；但**边双连通分量之间不会有公共边，两个边双连通分量通过"桥"相连**。 ## 强连通图 强连通图：**有向图**中，对**任意两个不同的顶点 $V_i$ 与 $V_j$**，**均有从 $V_i\rightarrow V_j$ 的路径以及从 $V_j\rightarrow V_i$ 的路径**，则称该有向图为强连通图。 #### 强连通分量 - **强连通分量**：有向图的**极大强连通子图**称为 $G$ 的强连通分量，强连通图只有一个强连通分量，即是其自身。 <br><br><br> # 图的存储表示方式 有以下几种方式来 "表示" 一个图： - **邻接矩阵** - **邻接表** 其中，最常用的是 "**==邻接表==**"。 > [!summary] 通常使用 "**==邻接表==**" 来表示图，而**不应当使用邻接矩阵**。 > > 原因在于： > > 邻接矩阵表示下，不仅**空间开销为 $O(|V|^2)$**，**进行 DFS/BFS 的时间复杂度也均为 $O(|V|^2)$**。 > 而绝大多数情况下图为 "**稀疏图**"，其边数远小于 "**全连接图**" 的边数，即边数 $|E|\ll|V|^2$ （例如下图所示的 "平面图"）。 > 采用**邻接表**，则时间、空间复杂度均为 $O(|V|+|E|)$。 > > ![[_attachment/00-数据结构与算法笔记/数据结构/图.assets/IMG-图-F137D2E9F1C76F7FBD253E0BDCA0C62C.png|681]] > <br> ## 邻接矩阵 - 二维数组 ✖ （C++11 后，不应该再用原生数组） - `vector<vector<int>>` 内外层都根据节点总数`n` 来固定 size。 ## 邻接表 C++中邻接表以 "**嵌套 STL 容器**" 实现： - 外层容器可以是： - `vector<C>`： 适用于顶点标识为 "**连续整数**" 的情况（例如 `[0, n-1]` 或 `[1,n]` ） - `unordered_map<T, C>`： 适用于顶点标识为 "**字符串**"、"**非连续整数**" 的情况，`T` 是 `int` 或 `string` 等。 - 内层容器 `C` 可以是： - `vector<T>` 或 `list<T>`： **最常规的方式**，`T` 可以是 `int` 或 `string` ，或者 `pair<int, int>` ，表示**带权值的边** `{dest, weight}` 。 - `unordered_set<T>`：适用于需要 $O(1)$ **查找某条边是否存在**的情况； - `set<T>`：可对边**去重、排序**，适用于**快速查找某条边**（二分 logn）； <br><br> # 参考资料 # Footnotes