最小生成树、最短路径、拓扑排序、关键路径

向右看齐 2023-02-17 15:54 61阅读 0赞

## 一、最小生成树 ##

普利姆算法和克鲁斯卡尔算法是两个利用MST性质构造最小生成树的算法。

### 1、普利姆算法（“加点法”） ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70]

### 2、克鲁斯卡尔算法 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 1]

## 二、最短路径 ##

### 1、迪杰斯特拉算法 ###

**（从某个源点到其余各顶点的距离）**  
时间复杂度为O(n^2)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 3]

### 2、弗洛伊德算法 ###

**（每一对顶点之间的最短路径）**  
时间复杂度为O(n^3)

## 三、拓扑排序 ##

**1、AOV-网**  
用顶点表示活动，用弧表示活动间的优先关系的图称为顶点表示活动的网，简称**AOV-网**。  
注意：  
（1）在AOV-网中，不应该出现有向环；  
（2）检测是否存在有向环的办法是对有向图的顶点进行拓扑排序；  
**2、拓扑排序**  
**概念：**  
所谓的拓扑排序就是将AOV-网中所有顶点排成一个线性序列，该序列满足：若在AOV-网中由顶点Vi到顶点Vj只有一条路径，则在该线性序列中顶点Vi必定在顶点Vj之前。  
**过程：**  
（1）在有向图中选一个无前驱的顶点且输出它；  
（2）从图中删除该顶点和所有以他为尾的弧；  
（3）重复（1）和（2），直至不存在无前驱的顶点；  
（4）若此时输出的顶点个数小于有向图中的顶点个数，则说明有向图中存在环，否则输出的顶点序列即为一个拓扑序列；

## 四、关键路径 ##

**1、AOE-网**  
AOE-网是一个带权的有向无环图，其中，顶点表示事件，弧表示活动，权表示活动持续的时间。通常，AOE-网可用来估算工程完成的时间。  
**2、几个定义：**  
（1）源点：网中只有一个入度为零的点；  
（2）汇点：网中只有一个出度为零的点；  
（3）带权路径长度：一条路径各弧上的权值之和；  
（4）关键路径：找一条从源点到汇点的带权路径长度最长的路径；  
**3、关键路径求解的过程**  
（1）对图中顶点进行排序，在排序过程中按拓扑序列求出每个事件的最早发生时间ve(i);  
（2）按逆拓扑序列求出每个事件的最迟发生时间vl(i)；  
（3）求出每个活动ai的最早开始时间e(i)；  
（4）求出每个活动ai的最晚开始时间l(i)；  
（5）找出e(i)=l(i)的活动ai，即为关键活动。由关键活动形成的由源点到汇点的每一条路径就是关键路径（关键路径有可能不止一条）；  
**4、几个时间的求法**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 4]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020061422402266.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020061720104730.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020061909530891.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2020061909592297.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200624110242341.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw==,size_16,color_FFFFFF,t_70