1.重连通图
1.重连通图
：在
常用数据结构图
这一篇中介绍过强连通图的概念，对于有向图任意两个节点A、B均符合从A到B有路径连通，从B到A也有路径连通，则称这样的有向图为强连通图。非强连通图中各自强连通的最大子图称为强连通分量。这跟重连通图概念有点像，重连通图指
无向图
中任意两个节点之间都有至少两条通路，称这样的无向图为
重连通图
。
2.关节点/割点
**：在无向图中，删除了某个顶点及其对应的边之后。原来的连通图被分割为二个及以上的连通分量，这样的顶点被叫做
关节点/割点
3.连通度
:重连通图是没有关节点的，也就是说任何一个顶点及其对应的边的删除，都不会破坏图的连通性。但是多删除几个也许就可以。所以我们定义如果删除了K个顶点及其对应的边，重连通图的连通性被破坏了，那么该重连通图的连通度为K。所以说连通度可以显示出一个重连通图的健壮性。
重连通图有着广泛的现实意义：比如现在有覆盖多个城市之间的信号网，如果该网络是一个重连通图，那么其中任何一个信号站出问题，都不会使得其它任何两个城市中不能相互通信。这个网络的连通度越高，整体网络的健壮性就越好。
4.判断重连通图
：重连通图有一个性质，就是所有的顶点都不是关节点。利用反正法，在一个图中只要找到一个关节点，那么这个图就不是重连通图。如果一个都找不到，那个就是重连通图。
如下图所示，是一个图的深度优先搜索树，树中的虚线表示原来图中存在，但是树中不存在的边，称为
回边
。我们正是利用回边也判断关节点的。
有两个原则：
1.如果树的根节点有多个子节点，那个根节点是关节点。(因为删除了根节点之后,树就变成了多个子树，对应图就是多个连通分量)
2.除过根节点和叶子节点之外的节点，如果其每棵子树都至少有一个节点存在到该根节点祖宗节点(这里的祖宗节点是不包括本节点的其它祖先节点)的回边，就不是关节点，否则就是关节点。
如下图：关节点有A、B、D、G
A是有两个子节点的树根，所以是关节点
B有三棵子树，只有C有到A的回边，其它两个子树都没有，所以是关节点。
D和G子树中都没有到祖宗节点的回边。
综上：这棵树对应的无向图不是重连通图。
2.拓扑排序
拓扑排序
是表示有向无环图中各顶点先后关系的一种排序。
如果顶点间两两之间都存在先后关系则成为
全序
(如图1中的二图)，否则为
偏序
(如图1中的一图)
如果用来表示某种有意义的活动的先后次序关系，则成为
AOV
网。比如早饭——午饭——晚饭——宵夜
拓扑排序的方法：不断的寻找图中没有前驱(以该顶点为弧头的弧对应的弧尾，即箭头的尾部顶点)的顶点，从图中删除该顶点和其对应的所有弧，直到图中不存在没有前驱的顶点为止。如下所示，我们先找到了没有前驱V1,删除掉V1和其对应的边之后；有两个没有前驱的顶点V2、V3,我们随机选择了V2,并删除。再依次是V3,V4,知道不存在没有前驱的顶点。
如果是偏序图，则存在不止一条的拓扑序列。比如上面的图，因为顶点2和顶点3的先后顺序无法确定。所以就生成了下面两个拓扑序列。
3.关键路径
上一节我们说能表示某种有意义活动的先后顺序的图称为AOV网，那么给AOV网每条边加上各自的权值就变成了AOE网。其中的权值表示的是活动需要持续的时间，比如a1等于6，表示a1的完成需要6天(天是随便写的)。每个顶点表示之前的活动已经完成，比如V5表示a4,a5都已经完成。
其中V1入度为0，称为源点；V9出度为0，称为汇点。
关键路径就是保证所有的活动都能够完成的最长路径。假如上图是一个项目，图中的各条线是有着先后次序的生产线，关键路径就是保证整个项目能全部完成的生产流水线。
求关键路径需要掌握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)最早发生时间：找顶点对应的最长路径
Vl(j)最晚发生时间：求各顶点最晚发生时间，从后往前推。
e(i)最早开始时间：对应的弧尾顶点的最早发生时间
l(i)最晚开始时间：求各边中最晚开始时间
通过对比e(i)和I(i),我们发现a1、a4、a7、a8、a10、a11都是相等的，所以我们在AOE网络中找到了如下图所示的两条最大路径。
4.最短路径
高德在手，手走就走。对于现在城市人们的出行来说，一部手机，就可以以最快的速度到达自己的目的地。我们将地图看做是一张网，人们的出行就是从一个顶点到达另外一个顶点。如何让人们出行的时间成本最低，就涉及到了最短路径问题。
1.迪杰斯特拉算法
迪杰斯特拉算法求出的是一个顶点到其它所有顶点的最短路径，当人们出行的目的地还没有确定的时候，我们需要给出他们多个候选的地点。这时候列出出行者到其它所有候选地点的最短距离就是有必要的。
该算法的流程就是：不断找到下一个最近点，利用最近点到其它点的距离，更新初始点到其它点的最短距离，直到所有的点都得到最近距离。
我们使用下面的有向图，来演示一下具体的工作流程：
假如我们的初始点为V0,要求出V0到其它所有点的最短距离。我们看到跟V0直接相连的有V2、V4和V5,将各点距离用下面的表格表示出来，和V0之间没有边的顶点对应的距离为无穷大。我们看到离V0最近的点为V2。
然后找到V2到其它点的距离，从V2只能到达V3,V0V2-V3的距离比V0-V3的距离要小，所以更新V0对应V3的距离和路径。
更新之后我们发现V0-V4的距离最近(V2已经使用过，就排除)，所以V4最为下一个最近点。从V4可以到V3和V5,比较之后发现V0-V4-V3的距离小于原来表中的V0-V2-V3,所以更新V0到V3的距离和路径
找到下一个最近点为V3,对比之后发现V0-V4-V3-V5的距离小于从V0直接到V5的距离，所以更新V5。
下一个最近点为V5,V5-V1之间为无穷大，所以V1的距离不会更新，仍为原来的无穷大。至此，所有的点的最近距离都已经得到，算法流程结束。当然迪杰斯特拉算法不止适用于有向图，也适合无向图，具体的操作流程是一样的。
2.弗洛伊德算法
如果要求任意两点之间的最短路径，需要将每个点作为初始点执行一次迪杰斯特拉算法。本节介绍另外一种求解的思路弗洛伊德算法。
弗洛伊德算法思想是：以每一个点作为中间点，看是否会影响到原来点和点之间的最短路径。
我们还是以上一节的有向图学习一下弗洛伊德算法的流程，首先初始化点之间的两两距离如下表所示：
从原图可以看出V0、V1只有出度，没有入度。所以作为中间的不会有贡献。我们直接以V2作为中间点开始，看到图中V0-V3和V1-V5的距离得到了更新。
再以V3为中心点看到V0-V5,V1-V5,V2-V5和V4-V5的距离得到更新
再以V4为中心点，V0-V3,V0-V5的距离得到更新。
因为V5的出度为0，以V5为中心点也不会有什么贡献。相当于所有点都已经做过中心点，整体的遍历完成，结果如上表所示。
求任意点到点的距离，弗洛伊德算法的时间复杂度和迪杰斯特拉算法一样都为O(n^3)
5.总结
本篇我们聊了重连通图，无向图中任意两点之间有2条或2条以上的通路存在。拓扑排序，按照先后次序关系对顶点进行排列，如果顶点是有意义的事件，我们成为AOV网；给AOV网加上权重(代表活动执行的时间长度)，叫做AOE网络。然后介绍了求AOE网络中关键路径的方式，关键路径可以保证整个项目按时完成。最后介绍了两种求最优路径的方式弗洛伊德算法和迪杰斯特拉算法，迪杰斯特拉算法是不断的找下一个最近点，利用最近点到其它点的距离更新初始点到其他点的最短距离。弗洛伊德算法是以每一个点作为中间点，更新两两距离矩阵。
6.我将以暗影重生
黑夜如此的干净，所有的一切都成为最纯粹的。我听着歌，任思绪飞舞。只是太阳一出现，那所谓的五颜六色就都显露出来了。在我看来一切都是乱七八糟的，白天就是乱七八糟，各种混乱，各种丑陋！满世界的找到寥寥无几的几片美，却也是美的可怜。黑夜是一条道路，满是花椒的郁烈；黑夜是一个美人，带着幽兰的芳香。满天飞舞的亡灵，优雅，美丽，像是凤凰在浴火重生！他们已经被压抑了千年，这个世界本来就属于黑暗，阳光才是入侵者，将一切毫无保留的掠夺。我们那伟大的力量隐藏在夜中的一个角落里，要让世界刮起一阵前所未有的旋风，让一切都飞舞起来。黑夜亡灵，永不为奴！
【高清重制】亡灵序曲-史上最给力最震撼版