这个算法固然实现简单，然则并不好懂得。nullzx的博客园这篇博文静得很好，看完后算是懂得了Kosaraju算法那神奇的做法…

上图是一个含有两个强连通分量的有向图。强连通分量和强连通分量之间不会形成环，不然这两个连通分量就是一个整体，即算作同一个强连通分量。如不雅将连通分量缩小成一个顶点，那么上图就是一个含有两个顶点的无环图，且左边的顶点指向了右边的顶点。

如下，中心和右侧的图对应着膳绫擎两种情况。

如B3, A2, A0, A1, B4, B5，按照这个序列调用DFS，就能包管DFS必定会被调用两次。当然序列是不独一的，在DFS中有一种常见的序列可以包管这种关系，即逆后序。

[图片上传掉败…(image-f58914-1510374691562)]

所谓逆后序就是在DFS递归调用返回之前，将该顶灯揭捉?入栈中获得的序列。例如dfs(s) -> dfs(v)这个递归调用栈，表示了一条s -> v的路径，v将比s先返回，故先存入v，再存入s，栈中的次序是sv。

如今可以说说Kosaraju算法的思路：

• 将原图取反。
• 对反向图作深度优先遍历，获得顶点的逆后序分列。
• 回到原图，按照膳绫擎获得的逆后序序列的次序，对原图进行深度优先搜刮。(而不是按照0, 1, 2…如许的顶点次序)

我们来看，为什么反向图的逆后序就是我们须要的序列。

下面是寻找无向图的所有连通分量的代码，所用的无向图就是膳绫擎那副有3个连通分量的图。

对该算法的分析我都认为蛋疼…嫌麻烦的直接记住结论即可。

上图是取反后的有向图。设原图为G，取反后的图为Gr。深度优先搜刮Gr有两种可能：

• 大年夜强连通分量A中随便率性一?顶点开端，须要调用两次DFS，第一次A0、A1、A2入栈;第二次B3、B4、B5入栈。这种情况下，强连通分量B所有顶点都在强连通分量A之前。
• 大年夜强连通分量B中的随便率性一?顶点开端，只需调用一个DFS即可遍历到所有顶点。因为是逆后序，因为B中最先被拜访的顶点，最后才会返回，是以它在栈中位于栈顶的地位。

反向图的逆后序实际上是它的一个伪拓补序列(“伪”是因为可能有环构造)，将连通分量缩小成一个顶点后，有向图无环了，反向图的逆后序就成了一个拓补序列——入度为0的顶点的老是排在前面。则在原图中，该拓补序列就变成了出度为0的顶点排在前面了，膳绫擎有分析到，对那些出度为0的分量(已看作顶点)先辈行DFS的话，就可以包管每一次调用DFS拜访的顶点都处于同一个强连通分量下。

要确切地证实Kosaraju算法的┞俘确性，须要证实这个命题：按照反向图的逆后次序序在原图中进行DFS，每一次DFS中所拜访的所有顶点都在同一个连通分量之中。膳绫擎说了这么多，只是定性说清楚明了为什么应用反向图的逆后序如许的序列可以达到目标，命题的后半句…在膳绫擎的分析中我们假设它是精确的，实际上这个命题须要严格的证实，下面就来证实在命题前半句的前提下，后半句的┞俘确性。

要证实这个命题，有两点须要证实(按照反向图逆后序的次序进行DFS的前提下)：

• 每个和s强连通的顶点v必定会在调用dfs(G, s)中被拜访到;
• dfs(G, s)所达到的随便率性顶点v都必定是和s强连通的。

第一点，用反证法：假设存在一个顶点v不是在调用dfs(G,s)中被拜访到的，因为存在s -> v的路径，解释v在调用dfs(G, s)之前就已经被拜访过了(不然和假设不符);又因为也存在v -> s的路径，所以在调用dfs(G , v)后，s肯定也会被标记已拜访，如许就调用不到dfs(G ,s)了，与我们假设会调用dfs(G, s)的前提抵触了。所以原命题成立。

膳绫擎两种情况都包管了B中至少有一个顶点在A全部顶点之前，回到原图中就会先对B中的顶点先辈行DFS。推广到拥有多个强连通分量的有向图，上述推论依然是成立的。

第二点，dfs(G, s)能达到顶点v，解释存在s -> v的路径，要证实s和v是强连通的，只需再证实在原图G中还存在一条v -> s的路径，等价于在反向图Gr中找到一条s -> v的路径。因为是按照逆后序进行深度优先搜刮，在Gr中dfs(Gr, v)必定是在dfs(Gr, s)之前返回的，不然逆后序就变成了[v, s]，原图在dfs调用时就会先调用dfs(G, v)，此时如不雅原图存在v -> s的路径，那么dfs(G, v)被调用后，s会被标记已拜访，大年夜而dfs(G, s)不会被调用到——这和我们假设的前提dfs(G, s)会被调用且达到v顶点抵触。所以在Gr中dfs(Gr, v)必定会在dfs(Gr, s)之前返回，这有两种情况

• dfs(Gr, v)在dfs(Gr, s)之前调用，并且也在dfs(Gr, s)的调用停止前停止。即dfs(Gr, v)调用 -> dfs(Gr, v)停止 -> dfs(Gr, s)调用 -> dfs(Gr, s)停止
• dfs(Gr, v)在dfs(Gr, s)之后调用，并且在dfs(Gr, s)的调用停止前停止。即dfs(Gr, s)调用 -> dfs(Gr, v)调用 -> dfs(Gr, v)停止 -> dfs(Gr, s)停止

第一种情况是弗成能的。因为Gr中存在v -> s(G中有s -> v)，所以第一种情况中的调用弗成能出现。第二种情况正好说清楚明了Gr中存在一条s -> v的路径。得证!

　　推荐阅读

　　40岁的IT巨人微软 究竟是什么在支撑着它继续前进？

Tech Neo技巧沙龙 | 11月25号，九州云/ZStack与您一路商量云时代收集界线治理实践 上周，微软颁布了其2018财年第一季度的财报。毫无不测埠，微软在这一季度大年夜赚了一笔。微软颁布财报后>>>详细阅读

本文标题：数据结构与算法–图论之寻找连通分量、强连通分量

地址：http://www.17bianji.com/lsqh/38858.html

 1/2    1