图

博主： wmicheng
发布时间：2025 年 02 月 10 日
35 次浏览
暂无评论
18646字数
分类：数据结构

## 图的基本概念

> #### 图的定义

- **图`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∈V, v∈V$}，用$|E|$表示图G中边的条数。
- 注意：线性表可以是空表，树可以是空树，但图不可以是空，即**V一定是非空集**

![图的定义](https://wmicheng.top/images/note/img/图的定义.png)

> #### 无向图、有向图

![图的定义1](https://wmicheng.top/images/note/img/图的定义1.png)

> #### 简单图、多重图

![图的定义2](https://wmicheng.top/images/note/img/图的定义2.png)

> #### 顶点的度、入度、出度

![图的定义3](https://wmicheng.top/images/note/img/图的定义3.png)

> #### 顶点-顶点的关系描述

| 顶点之间有可能不存在路径        | 有向图的路径也是有向的          |
| ------------------------------- | ------------------------------- |
| ![图的定义4](https://wmicheng.top/images/note/img/图的定义4.png) | ![图的定义5](https://wmicheng.top/images/note/img/图的定义5.png) |

- **路径**：顶点**v~p~**到顶点**v~p~**之间的一条路径是指顶点序列，$v_{p}, v_{i_{1}}, v_{i_{2}}, \cdots, v_{i_{m}}, v_{q}$
- **回路**：第一个顶点和最后一个顶点相同的路径称为回路或环
- **简单路径**：在路径序列中，顶点不重复出现的路径称为简单路径。
- **简单回路**：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
- **路径长度**：路径上边的数目
- **点到点的距离**：从顶点`u`出发到顶点`v`的**最短路径**若存在，则**此路径的长度称为从`u`到`v`的距离**。若从`u`到`v`根本**不存在路径**，则**记该距离为无穷$（∞）$**。
- **无向图**中，若从顶点v到顶点w有路径存在，则称v和w是`连通`的
- **有向图**中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是`强连通`的

> #### 连通图、强连通图

![图的定义6](https://wmicheng.top/images/note/img/图的定义6.png)

> #### 研究图的局部——子图

| 无向图                          | 有向图                          |
| ------------------------------- | ------------------------------- |
| ![图的定义7](https://wmicheng.top/images/note/img/图的定义7.png) | ![图的定义8](https://wmicheng.top/images/note/img/图的定义8.png) |

> #### 连通分量

![图的定义9](https://wmicheng.top/images/note/img/图的定义9.png)

- `无向图`中的**极大联通子图**称为**连通分量**
- 子图必须连通，且包含尽可能多的顶点和边

> #### 强连通分量

![图的定义10](https://wmicheng.top/images/note/img/图的定义10.png)

- `有向图`中的**极大强联通子图**称为有向图的**强连通分量**
- 子图**必须强连通**，同时保留尽可能多的边

> #### 生成树

![图的定义11](https://wmicheng.top/images/note/img/图的定义11.png)

- 连通图的生成树是包含图中全部顶点的一个极小连通子图
- 边尽可能的少，但要保持连通
- 若图中顶点数为n，则它的生成树含有n-1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。

> #### 生成森林

![图的定义12](https://wmicheng.top/images/note/img/图的定义12.png)

在**非连通图**中，**连通分量的生成树**构成了非连通图的生成森林。

> #### 边的权、带权图/网

![图的定义13](https://wmicheng.top/images/note/img/图的定义13.png)

- `边的权`：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的**权值**。
- `带权图/网`：边上带有权值的图称为**带权图**，也称**网**。
- `带权路径长度`：当图是带权图时，一条**路径上所有边的权值之和**，称为该路径的带权路径长度

> #### 几种特殊形态的图

|                                 |                                 |
| ------------------------------- | ------------------------------- |
| ![特殊的图1](https://wmicheng.top/images/note/img/特殊的图1.png) | ![特殊的图2](https://wmicheng.top/images/note/img/特殊的图2.png) |
| ![特殊的图3](https://wmicheng.top/images/note/img/特殊的图3.png) | ![特殊的图4](https://wmicheng.top/images/note/img/特殊的图4.png) |
| ![特殊的图5](https://wmicheng.top/images/note/img/特殊的图5.png) | ![特殊的图6](https://wmicheng.top/images/note/img/特殊的图6.png) |

- 无向完全图：无向图中任意两个顶点之间都存在边
- 有向完全图：有向图中任意两个顶点之间都存在方向相反的两条弧
- 边数很少的图称为稀疏图反之称为稠密图
- 没有绝对的界限，一般来说$|E| < |V|log|V|$时，可以将G视为稀疏图
- 树：不存在回路，且连通的无向图
- 有向树：一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树
  
  - n个顶点的树，必有n-1条边。
- n个顶点的图，若$|E|>n-1$，则一定有回路

> #### 图的概念总结

| 总结                              | 常考内容                          |
| --------------------------------- | --------------------------------- |
| ![图的定义14](https://wmicheng.top/images/note/img/图的定义14.png) | ![图的定义15](https://wmicheng.top/images/note/img/图的定义15.png) |

## 图的存储结构

### 邻接矩阵法

> #### 定义

- 无向图：
  
  - 第i个结点的`度`=`第i行（或第i列）`的非零元素个数
- 有向图：
  
  - 第i个结点的`出度`=`第i行`的非零元素个数
  - 第i个结点的`入度`=`第i列`的非零元素个数
- 第i个结点的`度`=`第i行`、`第i列`的非零元素个数之和
- 邻接矩阵法`求顶点的度、出度、入度`的时间复杂度为**$O(|V|)$**

> #### 邻接矩阵法存储带权图（网)

![邻接矩阵法1](https://wmicheng.top/images/note/img/邻接矩阵法1.png)

> #### 邻接矩阵法的性能分析

- 空间复杂度：$O(|V|^2)$ ——只和顶点数相关，和实际的边数无关
- 适合用于存储稠密图
- 无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上三角区/下三角区）

> #### 邻接矩阵法的性质

| 邻接矩阵法的性质                                | 邻接矩阵法的性质                                |
| ----------------------------------------------- | ----------------------------------------------- |
| ![邻接矩阵法的性质1](https://wmicheng.top/images/note/img/邻接矩阵法的性质1.png) | ![邻接矩阵法的性质2](https://wmicheng.top/images/note/img/邻接矩阵法的性质2.png) |

> #### 邻接矩阵法要点回顾

• 如何计算指定顶点的度、入度、出度（分无向图、有向图来考虑）？时间复杂度如何？
• 如何找到与顶点相邻的边（入边、出边）？时间复杂度如何？
• 如何存储带权图？
• 空间复杂度——$O(|V|^2)$，适合存储稠密图
• 无向图的邻接矩阵为对称矩阵，如何压缩存储？
• 设图G的邻接矩阵为A（矩阵元素为0/1），则An的元素`An[i][j]`等于由顶点`i`到顶点`j`的长度为n
的路径的数目

### 邻接表法

> #### 为什么要使用邻接表

- 邻接矩阵是使用数组实现的顺序存储，空间复杂度高，不适合存储稀疏图
- 邻接表是**顺序+链式存储**

> #### 定义：

![邻接表法](https://wmicheng.top/images/note/img/邻接表法.png)

- 其实这和树的孩子表示法是类似的，孩子表示法：顺序存储各个结点，每个结点中保存孩子链表头指针
- 边结点的数量是$2|E|$，整体空间复杂度为$O(|V| + 2|E|)$
- 边结点的数量是$|E|$，整体空间复杂度为$O(|V| + |E|)$
- 只要确定了顶点编号，图的邻接矩阵表示方式唯一，图的邻接表表示方式并不唯一

> #### 邻接矩阵和邻接表的对比

![邻接表法2](https://wmicheng.top/images/note/img/邻接表法2.png)

|                  | 邻接表                                      | 邻接矩阵           |
| ---------------- | ------------------------------------------- | ------------------ |
| 空间复杂度       | 无向图$O(|V|+2|E|)$;有向图$O(|V| +|E|)$     | $O(|V|^2)$         |
| 适合用于         | 存储稀疏图                                  | 存储稠密图         |
| 表示方式         | 不唯一                                      | 唯一               |
| 计算度/出度/入度 | 计算有向图的度、`入度`不方便,其余很方便 | 必须遍历对应行或列 |
| 找相邻的边       | 找有向图的`入边`不方便,其余很方便       | 必须遍历对应行或列 |

### 十字链表、邻接多重表

> #### 关系：

- 十字链表储存有向图
- 邻接多重表储存无向图

> #### 十字链表存储有向图：

![十字链表存储有向图](https://wmicheng.top/images/note/img/十字链表存储有向图.png)

- 空间复杂度：$O(|V|+|E|)$
- 如何找到指定顶点的所有出边？顺着绿色线路找
- 如何找到指定顶点的所有入边？顺着橙色线路找

> #### 邻接矩阵、邻接表存储有向图无向图

| 存储有向图                                                   | 存储无向图                                                   |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
| ![邻接矩阵、邻接表存储有向图](https://wmicheng.top/images/note/img/邻接矩阵、邻接表存储有向图.png) | ![邻接矩阵、邻接表存储无向图](https://wmicheng.top/images/note/img/邻接矩阵、邻接表存储无向图.png) |

> #### 邻接多重表储存无向图

![邻接多重表](https://wmicheng.top/images/note/img/邻接多重表.png)

> #### 总结

|              | 邻接矩阵                               | 邻接表                                  | 十字链表     | 邻接多重表   |
| ------------ | -------------------------------------- | --------------------------------------- | ------------ | ------------ |
| 空间复杂度   | $O(|V|^2)$                             | 无向图$O(|V|+2|E|)$ 有向图$O(|V| +|E|)$ | $O(|V|+|E|)$ | $O(|V|+|E|)$ |
| 找相邻边     | 遍历对应行或列 时间复杂度为0(\|V\|)    | 找有向图的入边必须遍 历整个邻接表       | 很方便       | 很方便       |
| 删除边或顶点 | 删除边很方便,删除顶 点需要大量移动数据 | 无向图中删除边或顶点 都不方便           | 很方便       | 很方便       |
| 适用于       | 稠密图                                 | 稀疏图和其他                            | 只能存有向图 | 只能存无向图 |
| 表示方式     | 唯一                                   | 不唯一                                  | 不唯一       | 不唯一       |

## 图的基本操作

- **Adjacent(G,x,y)**：判断图G是否存在边<x, y>或(x, y)。
- **Neighbors(G,x)**：列出图G中与结点x邻接的边。
- **InsertVertex(G,x)**：在图G中插入顶点x。
- **DeleteVertex(G,x)**：从图G中删除顶点x。
- **AddEdge(G,x,y)**：若无向边(x, y)或有向边<x, y>不存在，则向图G中添加该边。
- **RemoveEdge(G,x,y)**：若无向边(x, y)或有向边<x, y>存在，则从图G中删除该边。
- `FirstNeighbor(G,x)`：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。
- `NextNeighbor(G,x,y)`：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。
- **Get_edge_value(G,x,y)**：获取图G中边(x, y)或<x, y>对应的权值。
- **Set_edge_value(G,x,y,v)**：设置图G中边(x, y)或<x, y>对应的权值为v。
- 注意：上面的操作都只针对邻接矩阵和邻接表

### 图的广度优先遍历（BFS）

> #### 树和图的广度优先遍历：

- 树的广度优先遍历：通过根结点，可以找到下一层的结点2，3，4.通过234又可以找到再下一层的结点5678
  
  - 若树非空，则根结点入队
  - 若队列非空，队头元素出队并访问，同时将该元素的孩字依次入队
  - 重复第二步直到队列为空
- **图**的`广度优先遍历`类似于树的广度优先遍历（**层序遍历**）
- 区别：
  
  - 树不存在“回路”，搜索相邻的结点时，不可能搜到已经访问过的结点
  - 图搜索相邻的顶点时，有可能搜到已经访问过的顶点

> #### 代码实现：

- 找到与一个顶点相邻的所有顶点
  
  - `FirstNeighbor(G,x)`：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。
  - `NextNeighbor(G,x,y)`：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。
  - 使用上面两个基本操作
- 标记哪些顶点被访问过
  
  - ![BFS3](https://wmicheng.top/images/note/img/BFS3.png)
  - 都初始化为false
- 需要一个辅助队列

| 顶点被访问                                                   | 辅助队列                                                     |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
|  |  |
|  |  |
|  |  |

**遍历序列的可变性：**

![遍历序列的可变性](https://wmicheng.top/images/note/img/遍历序列的可变性.png)

> **从`顶点1`出发得到的⼴度优先遍历序列**：

$1，2，5，6，3，7，4，8$

> **从`顶点3`出发得到的⼴度优先遍历序列**：

$3，4，6，7，8，2，1，5$

**算法存在的问题和解决方案：**

如果是非连通图，则无法遍历完所有结点

| 算法存在的问题        | 解决方案              |
| --------------------- | --------------------- |
| ![BFS1](https://wmicheng.top/images/note/img/BFS1.png) | ![BFS2](https://wmicheng.top/images/note/img/BFS2.png) |

| 复杂度分析                        |                                     |
| --------------------------------- | ----------------------------------- |
| ![复杂度分析](https://wmicheng.top/images/note/img/复杂度分析.png) | ![复杂度分析1](https://wmicheng.top/images/note/img/复杂度分析1.png) |

**广度优先生成树&森林：**

| 广度优先生成树                                      | 广度优先生成森林                                      |
| --------------------------------------------------- | ----------------------------------------------------- |
| ![广度优先生成树&森林](https://wmicheng.top/images/note/img/广度优先生成树&森林.png) | ![广度优先生成树&森林2](https://wmicheng.top/images/note/img/广度优先生成树&森林2.png) |

- 广度优先生成树由广度优先遍历过程确定。
- 由于邻接表的表示方式不唯一，因此基于邻接表的广度优先生成树也不唯一
- 对非连通图的广度优先遍历，可得到广度优先生成森林

![BFS](https://wmicheng.top/images/note/img/BFS.png)

### 图的深度优先遍历（DFS）

**树和图的深度优先遍历：**

- 树的深度优先遍历（先根、后根）
  
  - 从根结点出发，能往更深处走就尽量往深处走。
  - 每当访问一个结点的时候，要检查是否还有与当前结点相邻的且没有被访问过的结点，如果有的话就往下一层钻。
- 图的深度优先遍历类似于树的先根遍历。
- 图的深度优先遍历是递归实现的，广度优先办理是队列实现的

**图的深度优先遍历：**

![DFS](https://wmicheng.top/images/note/img/DFS.png)

**算法存在的问题和解决方案：**

如果是非连通图，则无法遍历完所有结点

![DFS1](https://wmicheng.top/images/note/img/DFS1.png)

**复杂度分析：**

| 空间复杂度            | 时间复杂度              |
| --------------------- | ----------------------- |
| ![DFS2](https://wmicheng.top/images/note/img/DFS2.png) | ![DFS23](https://wmicheng.top/images/note/img/DFS23.png) |

**深度优先序列：**

![DFS4](https://wmicheng.top/images/note/img/DFS4.png)

- 和图的邻接表是一个原理，树中各个孩子结点在邻接表中出现的顺序是可变的
- 因此如果采用这种数据结构存储树，那么可能会有不同的遍历序列

**深度优先生成树：**

- 同一个图的`邻接矩阵`表示方式`唯一`，因此深度优先`遍历序列唯一`，深度优先`生成树也唯一`
- 同一个图`邻接表`表示方式`不唯一`，因此深度优先`遍历序列不唯一`，深度优先`生成树也不唯一`
- 对无向图进行BFS/DFS遍历

|                       |                       |
| --------------------- | --------------------- |
| ![DFS5](https://wmicheng.top/images/note/img/DFS5.png) | ![DFS6](https://wmicheng.top/images/note/img/DFS6.png) |

**图的遍历与图的连通性：**

- 调用BFS/DFS函数的次数=连通分量数
- 对于`连通图`，**只需调用1次**BFS/DFS
- 对`有向图`进行BFS/DFS遍历
- 调用BFS/DFS函数的次数要具体问题具体分析，若起始顶点到其他各顶点都有路径，则只需调用1次BFS/DFS函数
- 对于`强连通图`，从任一结点出发都只需调用1次BFS/DFS

![DFS7](https://wmicheng.top/images/note/img/DFS7.png)

## 最小生成树

> #### 生成树：

![生成树](https://wmicheng.top/images/note/img/生成树.png)

- **连通图**的`生成树`是**包含图中全部顶点的一个极小连通子图**。
- 若图中**顶点数**为`n`，则**它的生成树**含有`n-1`条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路

| 广度优先生成树                            | 深度优先生成树                            |                                             |
| ----------------------------------------- | ----------------------------------------- | ------------------------------------------- |
| ![广度优先生成树](https://wmicheng.top/images/note/img/广度优先生成树.png) | ![深度优先生成树](https://wmicheng.top/images/note/img/深度优先生成树.png) | ![深度优先生成树1](https://wmicheng.top/images/note/img/深度优先生成树1.png) |

**最小生成树（最小代价树）：**

- 对于一个带权连通无向图G = (V, E)，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同
- 设R为G的所有生成树的集合，若T为R中边的权值之和最小的生成树，则T称为G的最小生成树（Minimum-Spanning-Tree, MST）
- 最小生成树可能有多个，但边的权值之和总是唯一且最小的
- 最小生成树的边数 = 顶点数 - 1
- 砍掉一条则不连通，增加一条边则会出现回路
- 如果一个连通图本身就是一棵树，则其最小生成树就是它本身
- 只有连通图才有生成树，非连通图只有生成森林
- ![最小生成森林](https://wmicheng.top/images/note/img/最小生成森林.png)

### `Prim` 算法（普里姆）

算法思想：

- 从某一个顶点开始构建生成树；
- 每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。
- 时间复杂度：$O(|V|^2)$，适合用于边稠密图

> #### 数据结构

| Prim 算法                   | （普里姆）                  |                             |
| --------------------------- | --------------------------- | --------------------------- |
| ![普里姆1](https://wmicheng.top/images/note/img/普里姆1.png) | ![普里姆2](https://wmicheng.top/images/note/img/普里姆2.png) | ![普里姆3](https://wmicheng.top/images/note/img/普里姆3.png) |
| ![普里姆4](https://wmicheng.top/images/note/img/普里姆4.png) | ![普里姆5](https://wmicheng.top/images/note/img/普里姆5.png) | ![普里姆6](https://wmicheng.top/images/note/img/普里姆6.png) |

实现步骤：

- 从$V_0$开始，总共需要 `n-1` 轮处理
- 循环遍历所有个结点，找到`lowCost`最低的，且还没加入树的顶点，`isJoin`对应结点标记为`true`
- 再次循环遍历，更新还没加入的各个顶点的`lowCost`值
- 重复上面步骤，直到所有结点都加入树，生成的树即为最小生成树

### `Kruskal` 算法（克鲁斯卡尔）

**算法思想：**

- 每次选择一条权值最小的边，使这条边的两头连通（原本已经连通的就不选）
- 直到所有结点都连通
- 时间复杂度：$O( |E|log_2|E| )$，适合用于边稀疏图

> #### 数据结构

| Kruskal 算法                        | （克鲁斯卡尔）                      |                                     |
| ----------------------------------- | ----------------------------------- | ----------------------------------- |
| ![克鲁斯卡尔1](https://wmicheng.top/images/note/img/克鲁斯卡尔1.png) | ![克鲁斯卡尔2](https://wmicheng.top/images/note/img/克鲁斯卡尔2.png) | ![克鲁斯卡尔3](https://wmicheng.top/images/note/img/克鲁斯卡尔3.png) |
| ![克鲁斯卡尔4](https://wmicheng.top/images/note/img/克鲁斯卡尔4.png) | ![克鲁斯卡尔5](https://wmicheng.top/images/note/img/克鲁斯卡尔5.png) | ![克鲁斯卡尔6](https://wmicheng.top/images/note/img/克鲁斯卡尔6.png) |

让各条边按照权值顺序排序

实现步骤：

- 共执行 e 轮，每轮判断两个顶点是否属于同一集合
- 检查第e条边的两个顶点是否连通（是否属于同一个集合）
- 若不联通则连起来
- 若联通则不操作
- 重复上面的步骤直到所有边都被遍历过

## 最短路径问题之Dijkstra算法

> #### Dijkstra简介

![迪杰斯特拉](https://wmicheng.top/images/note/img/迪杰斯特拉.png)

> #### BFS算法的局限性

![BFS局限性](https://wmicheng.top/images/note/img/BFS局限性.png)

> #### 算法思想

| 实现                            | `初始`：从$V_0$开始，初始化三个数组信息 |
| ------------------------------- | ------------------------------------------- |
| ![Dijkstra1](https://wmicheng.top/images/note/img/Dijkstra1.png) | ![Dijkstra2](https://wmicheng.top/images/note/img/Dijkstra2.png)             |

| 实现                              | 第1轮：循环遍历所有结点，找到还没确定最短路径，且`dist` 最小的顶点$V_i$，令`final[i]=ture` |
| :-------------------------------- | :----------------------------------------------------------- |
| ![Dijkstra3](https://wmicheng.top/images/note/img/Dijkstra3.png)   | ![Dijkstra4](https://wmicheng.top/images/note/img/Dijkstra4.png)                              |
| ![Dijkstra5](https://wmicheng.top/images/note/img/Dijkstra5.png)   | ![Dijkstra6](https://wmicheng.top/images/note/img/Dijkstra6.png)                              |
| ![Dijkstra7](https://wmicheng.top/images/note/img/Dijkstra7.png)   | ![Dijkstra8](https://wmicheng.top/images/note/img/Dijkstra8.png)                              |
| …                                 | …                                                            |
| ![Dijkstra10](https://wmicheng.top/images/note/img/Dijkstra10.png) | ![Dijkstra11](https://wmicheng.top/images/note/img/Dijkstra11.png)                            |

> #### 如何使用数组信息

$V0$到$V2$的最短(带权)路径长度为：`dist[2] = 9`

通过`path[]`可知，$V0$到$V2$的最短(带权)路径：

$V2<-－ V1<-－ V4<--V0$

> #### 实现流程

- 初始：从V0开始，初始化三个数组信息
- 循环遍历所有结点，找到还没确定最短路径，且dist 最小的顶点Vi，令final\[i\]=ture。
- 检查所有邻接自 Vi 的顶点，若其 final 值为false，则更新 dist 和 path 信息
- 重复上述步骤，知道所有结点的final都标记为true

> #### 代码实现思路：

![Dijkstra12](https://wmicheng.top/images/note/img/Dijkstra12.png)

> #### 用于负权值带权图

![Dijkstra13](https://wmicheng.top/images/note/img/Dijkstra13.png)

## 最短路径问题之Floyd算法

> #### `Robert W. Floyd`简介

![Floyd](https://wmicheng.top/images/note/img/Floyd.png)

> #### 算法思想

- **Floyd算法：求出每一对顶点之间的最短路径**
- 使用**动态规划思想**，将问题的求解分为多个阶段
- 对于n个顶点的图G，求任意一对顶点 $Vi —> Vj$ 之间的最短路径可分为如下几个阶段：
  
  - 初始：不允许在其他顶点中转，最短路径是？
  - `0`：若允许在 $V_0$ 中转，最短路径是？
  - `1`：若允许在 $V_0$、$V_1$ 中转，最短路径是？
  - `2`：若允许在 $V_0$、$V_1$、$V_2$ 中转，最短路径是？
  - …
  - `n-1`：若允许在  $V_0$、$V_1$、$V_2$ …… $V_{n-1}$ 中转，最短路径是？

> #### 实现步骤

| 步骤                      | 实现                                                        |
| ------------------------- | ----------------------------------------------------------- |
| ![Floyd4](https://wmicheng.top/images/note/img/Floyd4.png) |  |
| ![Floyd6](https://wmicheng.top/images/note/img/Floyd6.png) |  |
| ![Floyd7](https://wmicheng.top/images/note/img/Floyd7.png) |  |

> #### 代码实现

![Floyd2](https://wmicheng.top/images/note/img/Floyd2.png)

> #### 注意点

- Floyd算法可以用于负权图
- Floyd 算法`不能解决带有“负权回路”的图`（有负权值的边组成回路），这种图有可能没有最短路径（每走一圈路径越小）

![Floyd1](https://wmicheng.top/images/note/img/Floyd1.png)

## 最短路径问题总结

![Floyd23](https://wmicheng.top/images/note/img/Floyd23.png)

## 有向无环图（DAG图）的描述表达式

> #### 定义

![DAG6](https://wmicheng.top/images/note/img/DAG6.png)

若一个`有向图`中`不存在环`，则称为有向无环图，简称`DAG图`（Directed Acyclic Graph）

> #### 例子

| 转换前                                                       | 转换后                                                  |
| ------------------------------------------------------------ | ------------------------------------------------------- |
|  |  |
|       |  |
|                                                              |                                                         |
|       |  |

> #### 解题方法

1. 把各个操作数不重复地排成一排
2. 标出各个运算符的生效顺序（先后顺序有点出入无所谓）
3. 按顺序加入运算符，注意“分层”
4. 从底向上逐层检查同层的运算符是否可以合体

## 拓扑排序

> #### AOV网

`AOV网`(Activity On Vertex NetWork，用顶点表示活动的网)

`用DAG图（有向无环图）`表示一个工程。顶点表示活动，有向边$<V_i, V_j>$表示活动Vi必须先于活动$V_j$进行

> #### 拓扑排序

`拓扑排序`：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：

1. 每个顶点出现且只出现一次。
2. 若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。

**或定义为**：

- 拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。

`每个AOV网都有一个或多个拓扑排序序列`。

> #### 拓扑排序的实现

- 从AOV网中选择一个没有前驱（入度为0）的顶点并输出。
- 从网中删除该顶点和所有以它为起点的有向边。
- 重复前面的步骤直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。

> #### 代码实现

![AOE4](https://wmicheng.top/images/note/img/AOE4.png)

> #### 逆拓扑排序

> #### 逆拓扑排序的实现

对一个AOV网，如果采用下列步骤进行排序，则称之为`逆拓扑排序`：

1. 从AOV网中选择一个没有后继`（出度为0）`的顶点并输出。
2. 从网中删除该顶点和所有以它为终点的有向边。
3. 重复上面步骤直到当前的AOV网为空。

- 用邻接表实现会更简单一些
- 使用逆邻接表：邻接表的顶点对应储存的信息是指向该顶点的边的信息
- 使用深度优先算法实现逆拓扑排序，顶点输出的序列就是逆拓扑排序序列
- DFS实现逆拓扑排序：在顶点退栈前输出

![AOE58](https://wmicheng.top/images/note/img/AOE58.png)

## 关键路径

> #### AOE网

- 在带权有向图中，以`顶点表示事件`，以`有向边表示活动`，以`边上的权值表示完成该活动的开销`（如完成活动所需的时间）
- 称之为用边表示活动的网络，简称`AOE`网 (Activity On Edge NetWork)

> $AOE$**网具有以下`两个性质`：

1. 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
2. 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。

**另外，有些活动是可以并行进行的**

> #### 关键路径

> #### 求关键路径的步骤

> #### 关键活动、关键路径的特性

- 若关键活动耗时增加，则整个工程的工期将增长
- 缩短关键活动的时间，可以缩短整个工程的工期
- 当缩短到一定程度时，关键活动可能会变成非关键活动
- 可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

![关键路径](https://wmicheng.top/images/note/img/关键路径.png)

最后修改：2025 年 02 月 11 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

图

wmicheng • 2025 年 02 月 10 日

## 图的基本概念

> #### 图的定义

![图的定义](https://wmicheng.top/images/note/img/图的定义.png)

> #### 无向图、有向图

![图的定义1](https://wmicheng.top/images/note/img/图的定义1.png)

> #### 简单图、多重图

![图的定义2](https://wmicheng.top/images/note/img/图的定义2.png)

> #### 顶点的度、入度、出度

![图的定义3](https://wmicheng.top/images/note/img/图的定义3.png)

> #### 顶点-顶点的关系描述

> #### 连通图、强连通图

![图的定义6](https://wmicheng.top/images/note/img/图的定义6.png)

> #### 研究图的局部——子图

> #### 连通分量

![图的定义9](https://wmicheng.top/images/note/img/图的定义9.png)

- `无向图`中的**极大联通子图**称为**连通分量**
- 子图必须连通，且包含尽可能多的顶点和边

> #### 强连通分量

![图的定义10](https://wmicheng.top/images/note/img/图的定义10.png)

- `有向图`中的**极大强联通子图**称为有向图的**强连通分量**
- 子图**必须强连通**，同时保留尽可能多的边

> #### 生成树

![图的定义11](https://wmicheng.top/images/note/img/图的定义11.png)

> #### 生成森林

![图的定义12](https://wmicheng.top/images/note/img/图的定义12.png)

在**非连通图**中，**连通分量的生成树**构成了非连通图的生成森林。

> #### 边的权、带权图/网

![图的定义13](https://wmicheng.top/images/note/img/图的定义13.png)

> #### 几种特殊形态的图

> #### 图的概念总结

## 图的存储结构

### 邻接矩阵法

> #### 定义

> #### 邻接矩阵法存储带权图（网)

![邻接矩阵法1](https://wmicheng.top/images/note/img/邻接矩阵法1.png)

> #### 邻接矩阵法的性能分析

> #### 邻接矩阵法的性质

> #### 邻接矩阵法要点回顾

### 邻接表法

> #### 为什么要使用邻接表

- 邻接矩阵是使用数组实现的顺序存储，空间复杂度高，不适合存储稀疏图
- 邻接表是**顺序+链式存储**

> #### 定义：

![邻接表法](https://wmicheng.top/images/note/img/邻接表法.png)

> #### 邻接矩阵和邻接表的对比

![邻接表法2](https://wmicheng.top/images/note/img/邻接表法2.png)

### 十字链表、邻接多重表

> #### 关系：

- 十字链表储存有向图
- 邻接多重表储存无向图

> #### 十字链表存储有向图：

![十字链表存储有向图](https://wmicheng.top/images/note/img/十字链表存储有向图.png)

- 空间复杂度：$O(|V|+|E|)$
- 如何找到指定顶点的所有出边？顺着绿色线路找
- 如何找到指定顶点的所有入边？顺着橙色线路找

> #### 邻接矩阵、邻接表存储有向图无向图

> #### 邻接多重表储存无向图

![邻接多重表](https://wmicheng.top/images/note/img/邻接多重表.png)

> #### 总结

## 图的基本操作

### 图的广度优先遍历（BFS）

> #### 树和图的广度优先遍历：

> #### 代码实现：

**遍历序列的可变性：**

![遍历序列的可变性](https://wmicheng.top/images/note/img/遍历序列的可变性.png)

> **从`顶点1`出发得到的⼴度优先遍历序列**：

$1，2，5，6，3，7，4，8$

> **从`顶点3`出发得到的⼴度优先遍历序列**：

$3，4，6，7，8，2，1，5$

**算法存在的问题和解决方案：**

如果是非连通图，则无法遍历完所有结点

**广度优先生成树&森林：**

![BFS](https://wmicheng.top/images/note/img/BFS.png)

### 图的深度优先遍历（DFS）

**树和图的深度优先遍历：**

**图的深度优先遍历：**

![DFS](https://wmicheng.top/images/note/img/DFS.png)

**算法存在的问题和解决方案：**

如果是非连通图，则无法遍历完所有结点

![DFS1](https://wmicheng.top/images/note/img/DFS1.png)

**复杂度分析：**

**深度优先序列：**

![DFS4](https://wmicheng.top/images/note/img/DFS4.png)

- 和图的邻接表是一个原理，树中各个孩子结点在邻接表中出现的顺序是可变的
- 因此如果采用这种数据结构存储树，那么可能会有不同的遍历序列

**深度优先生成树：**

**图的遍历与图的连通性：**

![DFS7](https://wmicheng.top/images/note/img/DFS7.png)

## 最小生成树

> #### 生成树：

![生成树](https://wmicheng.top/images/note/img/生成树.png)

**最小生成树（最小代价树）：**

### `Prim` 算法（普里姆）

算法思想：

- 从某一个顶点开始构建生成树；
- 每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。
- 时间复杂度：$O(|V|^2)$，适合用于边稠密图

> #### 数据结构

实现步骤：

### `Kruskal` 算法（克鲁斯卡尔）

**算法思想：**

- 每次选择一条权值最小的边，使这条边的两头连通（原本已经连通的就不选）
- 直到所有结点都连通
- 时间复杂度：$O( |E|log_2|E| )$，适合用于边稀疏图

> #### 数据结构

让各条边按照权值顺序排序

实现步骤：

## 最短路径问题之Dijkstra算法

> #### Dijkstra简介

![迪杰斯特拉](https://wmicheng.top/images/note/img/迪杰斯特拉.png)

> #### BFS算法的局限性

![BFS局限性](https://wmicheng.top/images/note/img/BFS局限性.png)

> #### 算法思想

> #### 如何使用数组信息

$V0$到$V2$的最短(带权)路径长度为：`dist[2] = 9`

通过`path[]`可知，$V0$到$V2$的最短(带权)路径：

$V2<-－ V1<-－ V4<--V0$

> #### 实现流程

> #### 代码实现思路：

![Dijkstra12](https://wmicheng.top/images/note/img/Dijkstra12.png)

> #### 用于负权值带权图

![Dijkstra13](https://wmicheng.top/images/note/img/Dijkstra13.png)

## 最短路径问题之Floyd算法

> #### `Robert W. Floyd`简介

![Floyd](https://wmicheng.top/images/note/img/Floyd.png)

> #### 算法思想

> #### 实现步骤

> #### 代码实现

![Floyd2](https://wmicheng.top/images/note/img/Floyd2.png)

> #### 注意点

- Floyd算法可以用于负权图
- Floyd 算法`不能解决带有“负权回路”的图`（有负权值的边组成回路），这种图有可能没有最短路径（每走一圈路径越小）

![Floyd1](https://wmicheng.top/images/note/img/Floyd1.png)

## 最短路径问题总结

![Floyd23](https://wmicheng.top/images/note/img/Floyd23.png)

## 有向无环图（DAG图）的描述表达式

> #### 定义

![DAG6](https://wmicheng.top/images/note/img/DAG6.png)

若一个`有向图`中`不存在环`，则称为有向无环图，简称`DAG图`（Directed Acyclic Graph）

> #### 例子

> #### 解题方法

## 拓扑排序

> #### AOV网

`AOV网`(Activity On Vertex NetWork，用顶点表示活动的网)

`用DAG图（有向无环图）`表示一个工程。顶点表示活动，有向边$<V_i, V_j>$表示活动Vi必须先于活动$V_j$进行

> #### 拓扑排序

`拓扑排序`：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：

1. 每个顶点出现且只出现一次。
2. 若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。

**或定义为**：

- 拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。

`每个AOV网都有一个或多个拓扑排序序列`。

> #### 拓扑排序的实现

> #### 代码实现

![AOE4](https://wmicheng.top/images/note/img/AOE4.png)

> #### 逆拓扑排序

> #### 逆拓扑排序的实现

对一个AOV网，如果采用下列步骤进行排序，则称之为`逆拓扑排序`：

1. 从AOV网中选择一个没有后继`（出度为0）`的顶点并输出。
2. 从网中删除该顶点和所有以它为终点的有向边。
3. 重复上面步骤直到当前的AOV网为空。

![AOE58](https://wmicheng.top/images/note/img/AOE58.png)

## 关键路径

> #### AOE网

> $AOE$**网具有以下`两个性质`：

**另外，有些活动是可以并行进行的**

> #### 关键路径

> #### 求关键路径的步骤

> #### 关键活动、关键路径的特性

![关键路径](https://wmicheng.top/images/note/img/关键路径.png)

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

图

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款