常用数据结构之重连通图_拓扑排序_关键路径_最短路径

曾经终败给现在 2022-12-12 04:42 197阅读 0赞

## 1.重连通图 ##

**1.重连通图**：在[常用数据结构图][Link 1]这一篇中介绍过强连通图的概念，对于有向图任意两个节点A、B均符合从A到B有路径连通，从B到A也有路径连通，则称这样的有向图为强连通图。非强连通图中各自强连通的最大子图称为强连通分量。这跟重连通图概念有点像，重连通图指**无向图**中任意两个节点之间都有至少两条通路，称这样的无向图为**重连通图**。  
**2.关节点/割点**\*\*：在无向图中，删除了某个顶点及其对应的边之后。原来的连通图被分割为二个及以上的连通分量，这样的顶点被叫做**关节点/割点**  
**3.连通度**:重连通图是没有关节点的，也就是说任何一个顶点及其对应的边的删除，都不会破坏图的连通性。但是多删除几个也许就可以。所以我们定义如果删除了K个顶点及其对应的边，重连通图的连通性被破坏了，那么该重连通图的连通度为K。所以说连通度可以显示出一个重连通图的健壮性。  
重连通图有着广泛的现实意义：比如现在有覆盖多个城市之间的信号网，如果该网络是一个重连通图，那么其中任何一个信号站出问题，都不会使得其它任何两个城市中不能相互通信。这个网络的连通度越高，整体网络的健壮性就越好。  
**4.判断重连通图**：重连通图有一个性质，就是所有的顶点都不是关节点。利用反正法，在一个图中只要找到一个关节点，那么这个图就不是重连通图。如果一个都找不到，那个就是重连通图。  
如下图所示，是一个图的深度优先搜索树，树中的虚线表示原来图中存在，但是树中不存在的边，称为**回边**。我们正是利用回边也判断关节点的。  
有两个原则：  
1.如果树的根节点有多个子节点，那个根节点是关节点。(因为删除了根节点之后,树就变成了多个子树，对应图就是多个连通分量)  
2.除过根节点和叶子节点之外的节点，如果其每棵子树都至少有一个节点存在到该根节点祖宗节点(这里的祖宗节点是不包括本节点的其它祖先节点)的回边，就不是关节点，否则就是关节点。  
如下图：关节点有A、B、D、G  
A是有两个子节点的树根，所以是关节点  
B有三棵子树，只有C有到A的回边，其它两个子树都没有，所以是关节点。  
D和G子树中都没有到祖宗节点的回边。  
综上：这棵树对应的无向图不是重连通图。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center]

## 2.拓扑排序 ##

**拓扑排序**是表示有向无环图中各顶点先后关系的一种排序。  
如果顶点间两两之间都存在先后关系则成为**全序**(如图1中的二图)，否则为**偏序**(如图1中的一图)  
如果用来表示某种有意义的活动的先后次序关系，则成为**AOV**网。比如早饭——午饭——晚饭——宵夜  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center 1]  
拓扑排序的方法：不断的寻找图中没有前驱(以该顶点为弧头的弧对应的弧尾，即箭头的尾部顶点)的顶点，从图中删除该顶点和其对应的所有弧，直到图中不存在没有前驱的顶点为止。如下所示，我们先找到了没有前驱V1,删除掉V1和其对应的边之后；有两个没有前驱的顶点V2、V3,我们随机选择了V2,并删除。再依次是V3,V4,知道不存在没有前驱的顶点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center 2]  
如果是偏序图，则存在不止一条的拓扑序列。比如上面的图，因为顶点2和顶点3的先后顺序无法确定。所以就生成了下面两个拓扑序列。  
![在这里插入图片描述][20201005230201129.png_pic_center]

## 3.关键路径 ##

上一节我们说能表示某种有意义活动的先后顺序的图称为AOV网，那么给AOV网每条边加上各自的权值就变成了AOE网。其中的权值表示的是活动需要持续的时间，比如a1等于6，表示a1的完成需要6天(天是随便写的)。每个顶点表示之前的活动已经完成，比如V5表示a4,a5都已经完成。  
其中V1入度为0，称为源点；V9出度为0，称为汇点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center 3]  
关键路径就是保证所有的活动都能够完成的最长路径。假如上图是一个项目，图中的各条线是有着先后次序的生产线，关键路径就是保证整个项目能全部完成的生产流水线。  
求关键路径需要掌握4个关键的指标：  
对于每个顶点来说有两个关键时间Ve(j)最早发生时间和Vl(j)最晚发生时间  
对于每条线来说也有两个关键时间e(i)最早开始时间和l(i)最晚开始时间  
Ve(j)最早发生时间：从原点到j顶点路径最长时间。比如V5节点最早发生时间为a1+a4=7,而不是a2+a5=5  
Vl(j)最晚发生时间：保证工期的前提下，该顶点最晚开始时间。如果总工期为18，那么V7的最晚发生时间为18-2=16  
e(i)最早开始时间：如果弧ai表示为<Vk,Vj>，则ai的最早开始时间，就是Vk的最早发生时间；即弧尾顶点的最早发生时间。  
l(i)最晚开始时间：如果弧ai表示为<Vk,Vj>，则ai的最晚开始时间为Vj-len(ai)，即弧头顶点最晚发生时间减去ai所需时间。  
如果一条边的最早开始时间等于最晚开始时间，则称这条边为关键活动，由关键活动组成的路径叫做关键路径。  
**求解过程**：  
所以求解关键路径的过程，就是将上面的四个分量统计出来，然后找到所有e(i)等于l(i)的边，就找到了关键路径。还是以上面的图为例：  
Ve(j)最早发生时间：找顶点对应的最长路径  
![在这里插入图片描述][20201006000834180.png_pic_center]  
Vl(j)最晚发生时间：求各顶点最晚发生时间，从后往前推。  
![在这里插入图片描述][20201006000858240.png_pic_center]  
e(i)最早开始时间：对应的弧尾顶点的最早发生时间  
![在这里插入图片描述][2020100600092944.png_pic_center]  
l(i)最晚开始时间：求各边中最晚开始时间  
![在这里插入图片描述][20201006000949792.png_pic_center]  
通过对比e(i)和I(i),我们发现a1、a4、a7、a8、a10、a11都是相等的，所以我们在AOE网络中找到了如下图所示的两条最大路径。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center 4]

## 4.最短路径 ##

高德在手，手走就走。对于现在城市人们的出行来说，一部手机，就可以以最快的速度到达自己的目的地。我们将地图看做是一张网，人们的出行就是从一个顶点到达另外一个顶点。如何让人们出行的时间成本最低，就涉及到了最短路径问题。

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

迪杰斯特拉算法求出的是一个顶点到其它所有顶点的最短路径，当人们出行的目的地还没有确定的时候，我们需要给出他们多个候选的地点。这时候列出出行者到其它所有候选地点的最短距离就是有必要的。  
该算法的流程就是：不断找到下一个最近点，利用最近点到其它点的距离，更新初始点到其它点的最短距离，直到所有的点都得到最近距离。  
我们使用下面的有向图，来演示一下具体的工作流程：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center 5]  
假如我们的初始点为V0,要求出V0到其它所有点的最短距离。我们看到跟V0直接相连的有V2、V4和V5,将各点距离用下面的表格表示出来，和V0之间没有边的顶点对应的距离为无穷大。我们看到离V0最近的点为V2。  
![在这里插入图片描述][20201006125935185.png_pic_center]  
然后找到V2到其它点的距离，从V2只能到达V3,V0V2-V3的距离比V0-V3的距离要小，所以更新V0对应V3的距离和路径。  
![在这里插入图片描述][20201006125948582.png_pic_center]  
更新之后我们发现V0-V4的距离最近(V2已经使用过，就排除)，所以V4最为下一个最近点。从V4可以到V3和V5,比较之后发现V0-V4-V3的距离小于原来表中的V0-V2-V3,所以更新V0到V3的距离和路径  
![在这里插入图片描述][20201006130007734.png_pic_center]  
找到下一个最近点为V3,对比之后发现V0-V4-V3-V5的距离小于从V0直接到V5的距离，所以更新V5。  
![在这里插入图片描述][20201006130101870.png_pic_center]  
下一个最近点为V5,V5-V1之间为无穷大，所以V1的距离不会更新，仍为原来的无穷大。至此，所有的点的最近距离都已经得到，算法流程结束。当然迪杰斯特拉算法不止适用于有向图，也适合无向图，具体的操作流程是一样的。

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

如果要求任意两点之间的最短路径，需要将每个点作为初始点执行一次迪杰斯特拉算法。本节介绍另外一种求解的思路弗洛伊德算法。  
弗洛伊德算法思想是：以每一个点作为中间点，看是否会影响到原来点和点之间的最短路径。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center 6]  
我们还是以上一节的有向图学习一下弗洛伊德算法的流程，首先初始化点之间的两两距离如下表所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center 7]  
从原图可以看出V0、V1只有出度，没有入度。所以作为中间的不会有贡献。我们直接以V2作为中间点开始，看到图中V0-V3和V1-V5的距离得到了更新。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center 8]  
再以V3为中心点看到V0-V5,V1-V5,V2-V5和V4-V5的距离得到更新  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center 9]  
再以V4为中心点，V0-V3,V0-V5的距离得到更新。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center 10]  
因为V5的出度为0，以V5为中心点也不会有什么贡献。相当于所有点都已经做过中心点，整体的遍历完成，结果如上表所示。  
求任意点到点的距离，弗洛伊德算法的时间复杂度和迪杰斯特拉算法一样都为O(n^3)

## 5.总结 ##

本篇我们聊了重连通图，无向图中任意两点之间有2条或2条以上的通路存在。拓扑排序，按照先后次序关系对顶点进行排列，如果顶点是有意义的事件，我们成为AOV网；给AOV网加上权重(代表活动执行的时间长度)，叫做AOE网络。然后介绍了求AOE网络中关键路径的方式，关键路径可以保证整个项目按时完成。最后介绍了两种求最优路径的方式弗洛伊德算法和迪杰斯特拉算法，迪杰斯特拉算法是不断的找下一个最近点，利用最近点到其它点的距离更新初始点到其他点的最短距离。弗洛伊德算法是以每一个点作为中间点，更新两两距离矩阵。

## 6.我将以暗影重生 ##

黑夜如此的干净，所有的一切都成为最纯粹的。我听着歌，任思绪飞舞。只是太阳一出现，那所谓的五颜六色就都显露出来了。在我看来一切都是乱七八糟的，白天就是乱七八糟，各种混乱，各种丑陋！满世界的找到寥寥无几的几片美，却也是美的可怜。黑夜是一条道路，满是花椒的郁烈；黑夜是一个美人，带着幽兰的芳香。满天飞舞的亡灵，优雅，美丽，像是凤凰在浴火重生！他们已经被压抑了千年，这个世界本来就属于黑暗，阳光才是入侵者，将一切毫无保留的掠夺。我们那伟大的力量隐藏在夜中的一个角落里，要让世界刮起一阵前所未有的旋风，让一切都飞舞起来。黑夜亡灵，永不为奴！

【高清重制】亡灵序曲-史上最给力最震撼版

[Link 1]: https://editor.csdn.net/md/?articleId=108923320
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/fd8a6ee54095471fa960e9195b98741e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/69f26f69eb1b42c5b8248b142bf8972c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/52b061d5447049c68dc4291d741537ad.png
[20201005230201129.png_pic_center]: /images/20221123/92c41751449c4e48b266eb549a359284.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/67516ac225954f8a8f5f8661b3137685.png
[20201006000834180.png_pic_center]: /images/20221123/f3b5713c148f497fb33e444bfafd265e.png
[20201006000858240.png_pic_center]: /images/20221123/7ca59bf4690742d2a34aeab142ba379c.png
[2020100600092944.png_pic_center]: /images/20221123/7b596e8bf107496f9d4e4ee0219e9382.png
[20201006000949792.png_pic_center]: /images/20221123/36463ec3bf7f4e9c9a6c96c257e758c7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/5aca59686b33463995be6514e1c8de3b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/9e8af6800f3e48b68c79566072e57554.png
[20201006125935185.png_pic_center]: /images/20221123/228829f76b8f4cfdbe2131c0ae02c28c.png
[20201006125948582.png_pic_center]: /images/20221123/1df49feaf8a64db1acc55ccaa78f4f3f.png
[20201006130007734.png_pic_center]: /images/20221123/bb42cef773d346c8b1a03b0210e57a0a.png
[20201006130101870.png_pic_center]: /images/20221123/feb569fa2eb4450e828979ca46d9d2b5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/758b328536af465897bd48a3da12e056.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/3a1d18a304fa477ca54d79c68b72d5cd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221123/1041f8df17594079ae6656dfa3af7c20.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221123/69258e0333424f9abe4801e18ccb2484.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221123/0b004f52f1ad4d8db5297f495a5cb777.png