Loading... ## 定义 图 $G$ 由**顶点集 $V$** 和**边集 $E$** 组成，记为 $G = (V, E)$ 。其中 $V(G)$ 表示图 $G$ 中顶点的有限非空集； $E(G)$ 表示图 $G$ 中顶点之间的关系 (边) 集合。若 $V = {v_1, v_2, ..., v_n}$ ，则用 $|V|$ 来表示图 $G$ 中顶点的个数，也称**图 $G$ 的阶**；若 $E = \{(u, v) | u \in V, v \in V\}$ ，则用 $|E|$ 表示图 $G$ 中**边的条数**。 > 线性表可以是空表，树可以是空树，但图不可以为空，即 $V$ 一定是非空集。 > > 图的边集可以为空。 ### 常见的图 #### 无向图 若 $E$ 是**无向边** (简称**边**) 的有限集合，则图 $G$ 为**无向图**。边时顶点的无序对，记为 $(v, w)$ 或 $(w, v)$ ，其中 $v, w$ 是顶点。因为 $(v, w) = (w, v)$ ，可以说顶点 $v$ 和顶点 $w$ 互为邻接点。 #### 有向图 若 $E$ 为**有向边** (也称弧) 的有限集合时，图 $G$ 为有向图。弧时顶点的有序对，记为 < $v, w$ > 。其中 $v, w$ 是顶点， **$v$ 称为弧尾**， **$w$ 称为弧头**。< $v, w$ >称为从顶点 $v$ 到顶点 $w$ 的弧，也称 $v$ 邻接到 $w$ ，或 $W$ 邻接自 $v$ 。< $v, w$ > $\neq$ < $w, v$ > 。 > 有向图的弧在可视化中一般用箭头表示，其中箭头指向的节点叫做弧头，箭头尾部的节点叫做弧尾 #### 简单图 不存在重复边，且不存在顶点到自身的边。 大部分问题都可以用简单图来解决，不常用多重图。 #### 多重图 若图 $G$ 中某两个节点之间的边数多于一条，且允许顶点通过同一条边与自己关联，则 $G$ 为多重图。 ### 度，入度和出度 对于无向图，**顶点 $v$ 的度**是指依附于该顶点的边的条数，记为 $TD(v)$ 。 > 在具有 $n$ 个顶点， $e$ 条边的无向图中， $\sum^n_{i = 1} TD(v_i) = 2e$ > > 即无向图的所有顶点的度之和等于边数的两倍。 对于有向图： - **入度**是以顶点 $v$ 为重点的有向边的数目，记为 $ID(v)$ ； - **出度**是以顶点 $v$ 为起点的有向边的数目，记为 $OD(v)$ ； - **顶点 $v$ 的度**等于其**入度和出度之和**，即 $TD(v) = ID(v) + OD(v)$ 。 ### 顶点与顶点之间的关系 - 路径：顶点 $v_p$ 到顶点 $v_q$ 之间的一条路径是指一个顶点序列 $v_p, v_{i_1}, v{i_2}, ... v_q$ - 两个顶点中可能不存在路径。 - 有向图的路径也是有向的。 - 回路：第一个顶点和最后一个顶点相同的路径称为回路或环。 - 简单路径：在路径序列中，顶点不重复出现的路径称为简单路径。 - 简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。 - 路径长度：路径上边的数目。 - 点到点的距离：从顶点 $u$ 出发到顶点 $v$ 的最短路径。若该路径不存在，则距离为无穷 ($\infty$)。 - 无向图中，若顶点 $v$ 到顶点 $w$ 中存在路径，则称 $v$ 和 $w$ 是**连通**的。 - 有向图中，若从顶点 $v$ 到顶点 $w$ 和从顶点 $w$ 到顶点 $v$ 之间都有路径，则称这两个顶点是**强连通**的。 - 若无向图中任意两个顶点都是联通的，则称该图为连通图，反之则为非连通图。 - 若有向图中任意一对顶点都是强连通的，则称此图为强连通图。 ### 子图 设有两个图 $G = (V, E)$ 和 $G' = (V', E')$ ，若 $V'$ 是 $V$ 的子集，且 $E'$ 是 $E$ 的子集，则称 $G'$ 是 $G$ 的**子图**。 若有满足 $V(G') = V(G)$ 的子图 $G'$ ，则称其为 $G$ 的生成子图。  > 对于有向图也是一样的，这里只是以无向图举例。 ### 连通分量和强连通分量 **无向图**中的**极大连通子图** (包含尽可能多顶点和边的连通子图) 称为**连通分量**。 **有向图**中的**极大强连通子图** (包含尽可能多顶点和边的强连通子图) 称为有向图的**强连通分量**。 ### 生成树 **连通图**的**生成树**是包含图中**全部顶点**的一个**极小连通子图** (边尽可能少的连通子图) 。 - 若途中顶点数为 $n$ ，则它的生成树含有 $n - 1$ 条边。 - 对于生成树而言，若砍去它的一条边，则会变成非连通图；若加上一条边，则会形成一个回路。 #### 生成森林 在**非连通图**中，**连通分量的生成树**构成了非连通图的**生成森林**。 ### 带权图 / 网 - 边的权：在一个图中，每条边都可以标上具有某种含义的数值，称为边的**权值**。 - 带权图 / 网：边上带有权值的图称为**带权图**，也称为**网**。 - 带权路径长度：当图是带权图时，一条**路径上所有边的权值之和**，称为该路径的带权路径长度。 ### 几种特殊形态的图 - 无向完全图：无向图中任意两个顶点之间都存在边。 - 有向完全图：有向图中任意两个顶点之间都存在方向相反的两条弧。 - 稀疏图：边数很少的图，没有绝对的界限。一般来说 $|E| < |V| \cdot log |V|$ 时，可以将该图视为稀疏图。 - 稠密图：与稀疏图相反的称之为稠密图，一般只需要直到这两个图是相对的就够了。 - 树：不存在回路，且连通的无向图。 - 有向树：一个顶点的入度为 0 ，其余顶点的入度均为 1 的有向图，称为有向树。 ### 考点 1. 对于 $n$ 个顶点的无向图 $G$ ： - 若 $G$ 是连通图，则最少有 $n - 1$ 条边。 - 若 $G$ 是非连通图，则最多可能有 $C^2_{n-1}$ 条边。 - 无向完全图共有 $C_n^2$ 条边。 - 所有顶点的度之和为 $2E$ 。 2. 对于 $n$ 个顶点的有向图 $G$ ： - 若 $G$ 是强连通图，则至少有 $n$ 条边 (形成回路) 。 - 有向完全图共有 $2C_n^2$ 条边。 - 所有顶点的度之和为 $2E$ 。 - 所有顶点的出度之和 = 所有顶点的入度之和 = $|E|$ 。 3. $n$ 个顶点的图，若 $|E| > n - 1$ ，则该图一定存在回路。 ## 存储方式 ### 邻接矩阵  #### 代码定义 ```c++ typedef struct { ElemType Vex[MAX_SIZE]; int Edge[MAX_SIZE][MAX_SIZE]; int vexnum, arcnum; // 图的顶点数和边数/弧数 } MGraph; ``` #### 性质 - 对于无向图，第 $i$ 个节点的度为第 $i$ 行 (或第 $i$ 列) 的非零元素个数。 - 对于有向图： - 第 $i$ 个节点的出度 = 第 $i$ 行的非零元素个数； - 第 $i$ 个节点的入度 = 第 $i$ 列的非零元素个数； - 第 $i$ 个节点的度 = 第 $i$ 行，第 $i$ 列的非零元素个数之和。 - 邻接矩阵法求顶点的度/入度/出度的时间复杂度为 $O(|V|)$ 。 设图 $G$ 的邻接矩阵为 $A$ (矩阵元素为 0 或 1) ，则 $A^n$ 的元素 $A^n[i][j]$ 等于由顶点 $i$ 到顶点 $j$ 的长度为 $n$ 的路径的数目。(可以自己进行矩阵相乘验证，离散数学中图论部分有证明) ### 邻接表  #### 代码定义 ```c++ typedef struct ArcNode { int adjvex; // 边/弧指向的节点 struct ArcNode *next; // 指向下一条弧的指针 } ArcNode; typedef struct VNode { VertexType data; // 顶点 ArcNode *first; // 第一条边/弧 } VNode, AdjList[MAX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph; ``` > 图的邻接表表示方法并不唯一。 #### 性质 | | 邻接表 | 邻接矩阵 | | ---------------- | -------------------------------------- | -------------------- | | 空间复杂度 | 无向图 $O( | V | | 适合用于 | 存储稀疏图 | 存储稠密图 | | 表示方式 | 不唯一 | 唯一 | | 计算度/入度/出度 | 计算有向图的度，入度不方便，出度方便。 | 必须遍历对应的行或列 | | 找相邻的边 | 找有向图的入边不方便，其余方便。 | 必须遍历对应的行或列 | ### 十字链表法  - 顺着绿色线路可以找到指定顶点的所有出边，顺着橙色线路可以找到指定顶点的所有入边。 - 空间复杂度： $O(|V| + |E|)$ 。 - 只适用于存储有向图。 ### 邻接多重表  - 空间复杂度：$O(|V| + |E|)$ 。 - 删除边和节点等操作很方便。 - 邻接多重表只适合存储无向图。 ### 总结  ## 基本操作 - 判断图 $G$ 是否存在边 $(x, y)$ 或 <$x, y$> 邻接矩阵 $O(1)$ ；邻接表 $O(1)$ ~ $O(|E|)$ 。 - 列出图 $G$ 中与节点 $x$ 邻接的边 邻接矩阵 $O(|V|)$ ；邻接表的出边 $O(1)$ ~ $O(|V|)$ ，入边 $O(|E|)$ 。 - 在图 $G$ 中插入节点 $x$ 邻接矩阵 $O(1)$ ；邻接表 $O(1)$ 。 - 从图 $G$ 中删除节点 $x$ 邻接矩阵 $O(|V|)$ ，将 $x$ 所在的行列置零； - 若无向边 $(x, y)$ 或有向边 <$x, y$> 不存在，则向图 $G$ 中添加该边。 - 求图 $G$ 中节点 $x$ 的第一个邻接点 - 设置和获取边的权值 ## 图的遍历 ### 广度优先搜索 - 图中可能存在环路，需要记录已访问的节点。 - 如果图为非连通图，则一次无法遍历完所有节点，需要遍历所有连通分量。 - 对于无向图来说，调用 BFS 函数的次数等于连通分量数。 - 空间复杂度最坏情况下为 $O(|V|)$ 。 - 邻接矩阵存储的图进行 BFS 的时间复杂度为 $O(|V|^2)$ ，邻接表则为 $O(|V| + |E|)$ 。 #### 广度优先生成树 由广度优先遍历确定的树，邻接表表示的情况下不唯一。  ### 深度优先搜索 - 图中可能存在环路，需要记录已访问的节点。 - 如果图为非连通图，则一次无法遍历完所有节点，需要遍历所有连通分量。 - 对于无向图来说，调用 DFS 函数的次数等于连通分量数。 - 时间复杂度在邻接矩阵的情况下为 $O|V|^2$ ，邻接表则为 $O(|V| + |E|)$ 。 - 空间复杂度来自函数调用栈，最坏的情况下为 $O(|V|)$ 。 深度优先生成树类似广度优先生成树。 ## 最小生成树 对于一个**带权连通无向图** $G = (V, E)$ ，构造的生成树不同，每棵树的权 (树中所有边上的权值之和) 也可能不同。 设 $R$ 为 $G$ 的所有生成树的集合，若 $T$ 为 $R$ 中边的权值之和最小的生成树，则称 $T$ 为 $G$ 的**最小生成树 (Minimum Spanning Tree, MST)** 。 - 最小生成树可能有多个，但边的权值之和总是唯一且最小的。 - 最小生成树的边数 = 顶点数 - 1 。砍掉一条边则不连通，增加一条边则会出现回路。 - 如果一个连通图本身就是一棵树，则其最小生成树就是它本身。 - 只有连通图才有生成树，非连通图只有生成森林。 ### Prim (普里姆) 算法 从某一个顶点开始构建生成树，每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。 #### 算法流程 1. 从一个起始点 $V_0$ 开始，总共需要 $n - 1$ 轮处理；  2. 每一轮就会循环遍历所有节点，找到代价最低且没加入树的节点加入生成树；  3. 再次循环遍历，更新没加入树的顶点的最低代价；  4. 重复 2 和 3 直到所有顶点都加入树。  **时间复杂度**：$O(|V|^2)$ ，适合用于边稠密图。 ### Kruskal (克鲁斯卡尔) 算法 每次选择一条权值最小的边，使这条边的两头连通 (如果两个顶点已经连通就不选) ，直到所有节点都连通。 #### 算法流程 1. 首先将各边按照权值排序； 2. 顺序遍历所有边，检查边的两个顶点是否属于同一集合。若属于则跳过，若不属于则将该边加入生成树。(时间复杂度 $log_2|E|$ ) > 可以使用并查集实现。 **时间复杂度**：$O(|E| log_2 |E|)$ ，适合用于边稀疏图。 ## 最短路径问题 ### 单源最短路径问题 #### BFS 算法 BFS 适合找无权图的最短路径。 前面树的章节提到过，不多记录了。 #### Dijkstra 算法 **带权路径长度**：当图为带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度。 Dijkstra 算法的思想很简单，就是使用贪心：每次选择一个路径最短的未确定的点，将其标记为已确定，然后更新其余未确定点的路径长度，直到所有点都标记为已确定。 > Dijkstra 算法不适合带负权值的图 ##### 算法流程 1. 初始化  2. 循环遍历所有顶点，找到还没确定最短路径，且 `dist` 最小的顶点 $V_i$ ，令 `final[i] = true` 。并检查所有邻接自 $V_i$ 的顶点 $V_j$ ，若 `final[j] == false && dist[i] + arcs[i][j] < dist[j]` ，则令 `dist[j] = dist[i] + arcs[i][j]; path[j] = i` 。(其中 `arcs[i][j]` 表示 $V_i$ 到 $V_j$ 的弧的权值)  - 时间复杂度：$O(|V|^2)$ 。 ### 多源最短路径问题 #### Floyd 算法 Floyd 算法又称为**插点法**，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。易知最短路径问题具有最优子结构，即最短路径的子路径一定也是最短路径；且该问题无后效性，也就是后面路径的选择不会影响之前的最短路径。所以该问题可以用动态规划思想求解。 > Floyd 算法不能解决带有**负权回路**的图 (有负权值的边组成回路) ，这种图有可能没有最短路径。 ##### 算法流程 1. 初始化一个邻接矩阵 `A` 存储各点之间直接可达的路径的长度，最终这个矩阵将存储所有点之间的最短路径长度。如果需要找到最短路径，则可以初始化一个矩阵 `path` ，记录各点之间的中转点。 > 注意无法到达的点之间的距离需要设置为无穷，每个点和自身的距离设置为 0 。 >  2. 假设可以在第一个点 $V_0$ 中转，更新 `A` 中的最短路径，并且将 `path` 中对应的位置设置成 $V_0$ 。  3. 对所有的点进行步骤 2 ，得到最终的结果。  ##### 代码实现 只有五行核心代码的算法： ```c++ for(int k = 0; k < n; k++) // 考虑以 Vk 作为中转点 for(int i = 0; i < n; i++) // 遍历整个矩阵 for(int j = 0; j < n; j++) if(A[i][j] > A[i][k] + A[k][j]) // 松弛操作 A[i][j] = A[i][k] + A[k][j]; // 如果需要加上路径信息，只需要在最里层一起更新 path 即可。 for(int k = 0; k < n; k++) { // 考虑以 Vk 作为中转点 for(int i = 0; i < n; i++) { // 遍历整个矩阵 for(int j = 0; j < n; j++) { if(A[i][j] > A[i][k] + A[k][j]) { // 松弛操作 A[i][j] = A[i][k] + A[k][j]; path[i][j] = k; } } } } ``` - 时间复杂度：$O(|V|^3)$ 。 - 空间复杂度：$O(|V|^2)$ 。  ## 有向无环图 (DAG) 若一个**有向图**中**不存在环**，则称为有向无环图，简称 **DAG 图** (Directed Acyclic Graph) 。 ### DAG 描述表达式 算数表达式可以通过树的方式来表示，但是可能会有很多冗余：  此时可以使用有向无环图将重复的节点合并：  #### 最少顶点的解题方法   ### 拓扑排序 **AOV 网 (Activity On Vertex Network)** ：用 DGA 表示一个工程，顶点表示活动，有向边 <$V_i, V_j$> 表示活动 $V_i$ 必须先于活动 $V_j$ 进行。 **拓扑排序**：在图论中，有一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序： 1. 每个顶点出现且仅出现一次。 2. 若顶点 $A$ 在序列中排在顶点 $B$ 的前面，则图中不存在从顶点 $B$ 到顶点 $A$ 的路径。 或定义为：拓扑排序时对有向无环图的顶点的一种排序，它使得若存在一条从顶点 $A$ 到顶点 $B$ 的路径，则在排序中顶点 $B$ 出现在顶点 $A$ 的后面。每个 AOV 网都有一个或多个拓扑排序。 > 找做事的先后顺序。 #### 实现 1. 从 AOV 网中选择一个没有前驱 (**入度为 0** ) 的顶点并输出； 2. 从网中**删除**该顶点和所有以它为起点的有向边； 3. 重复 1 和 2 直到当前的 **AOV 网为空**或者**不存在没有前驱的顶点**为止。  - 时间复杂度：邻接表为 $O(|V| + |E|)$ ，邻接矩阵为 $O(|V|^2)$ 。 ### 逆拓扑排序 逆拓扑排序就是和拓扑排序相反的过程，每次选择最后要做的事情即可。 #### 实现 1. 从 AOV 网中选择一个没有后继 (**出度为 0** ) 的顶点并输出； 2. 从网中**删除**该顶点和所有以它为终点的有向边； 3. 重复 1 和 2 直到当前的 **AOV 网为空**。  ### 拓扑排序的性质 - 拓扑排序和你拓扑排序序列可能不唯一； - 若图中有环，则不存在拓扑排序或逆拓扑排序序列； ### 关键路径 #### AOE 网 在带权有向图中，**顶点表示事件**，**有向边表示活动**，**边上的权值表示完成该活动的开销** (如完成活动所需要的时间) ，称之为用边表示活动的网络，即 **AOE 网** (Activity On Edge Network) 。 AOE 网具有以下两个性质： 1. 只有在某顶点所代表的事件发生后，从该顶点出发的各个有向边所代表的活动才能开始； 2. 只有在进入某顶点的各有向边所代表的活动都已经结束时，该顶点所代表的事件才能发生。另外，有些活动是可以并行进行的。 > AOE 网中**仅有一个**入度为 0 的顶点，称为**开始顶点 (源点)** ，它表示整个工程的开始； > > 也**仅有一个**出度为 0 的顶点，称为**结束顶点 (汇点)** ，它表示整个工程的结束。 #### 相关概念 从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为**关键路径**，关键路径上的活动称为**关键活动**。 > 因为活动可以并行执行。 完成整个工程的最短时间就是关键路径的长度。若关键活动不能按时完成，则整个工程的完成时间就会延长。 - 事件 $v_k$ 的最早发生时间 $ve(k)$ ：决定了所有从 $v_k$ 开始的活动能够开始的最早时间； - 活动 $a_i$ 的最早开始时间 $e(i)$ ：该活动弧的起点所表示的时间的最早发生时间； - 事件 $v_k$ 的最迟发生时间 $vl(k)$ ：指不推迟整个工程完成时间的前提下，该事件最迟必须发生的时间； - 活动 $a_i$ 的最迟开始时间 $l(i)$ ：活动弧的重点所表示事件的最迟发生时间与该活动所需时间之差； - 活动 $a_i$ 的时间余量 $d(i) = l(i) - e(i)$ ：表示在不增加完成整个工程所需总时间的情况下，活动 $a_i$ 可以拖延的时间。若一个活动的时间余量，则说明活动必须要如期完成。 $d(i) = 0$ ，即 $l(i) = e(i)$ 的活动是**关键活动**。 #### 求关键路径的步骤 1. 求所有事件的最早发生时间 $ve$ ：  2. 求所有事件的最迟发生时间 $vl$ ：  3. 求所有活动的最早发生时间 $e$ ： 若边 <$v_k, v_j$> 表示活动 $a_i$ ，则有 $e(i) = ve(k)$ 。 4. 求所有活动的最迟发生时间 $l$ ： 若边 <$v_k, v_j$> 表示活动 $a_i$ ，则有 $l(i) = vl(j) - weight(v_k, v_j)$ 。 5. 求所有活动的时间余量 $d$ ： $d(i) = l(i) - e(i)$ 。 $d(k) = 0$ 的活动就是关键活动，所有关键活动组成的路径就是关键路径。  #### 特性 - 若关键活动耗时增加，则整个工程的工期将会增加。 - 缩短关键活动的时间，可以缩短整个工程的工期。 - 当缩短到一定程度时，关键活动可能变成非关键活动。 - 可能存在多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快包含在所有关键路径上的关键活动才可以缩短工程的工期。 最后修改：2024 年 05 月 31 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏