User:Q515949148/Cache

这是我用于临时转存某些页面用的页面

Kosaraju

为了免于自己以后需要重新学习自己的代码的时候还要去看那个一眼看不怎么懂的wikipedia，我决定跟那个字符串匹配算法一样，也把它写出来。查找强连通子图的算法有若干个，Kosaraju是我最喜欢的，因为实现起来最方便。这个算法主要就是把下面的图：

图一

的CD给group到一起，曰强连通子图，因为这个子图每个从任何结点出发都可以到其他的任何节点。

方法也很简单明了。

第一步

我们随便给这个图的节点随便安排一个顺序，譬如说ABCDEF，ABCDEF的顺序并不重要。我们从A开始，然后把A能去的地方都染色，譬如这样：

图二

染完色就全部拿走，然后从下一个开始。显然，我们得到了两组颜色，分别是F(A)={ACDEF}和F(B)={B}，认准F(A)和F(B)这个顺序。

第二步

我们分别把每一组颜色里面的图，从第一个节点开始，譬如说F(A)就是A，做深度优先排序。出度的若干结点的顺序不重要，譬如C可以到D和E，随便哪个先来都可以，就得到了G(A)={ACEDF}和G(B)={B}。然后我们把G(A)、G(B)等等的顺序倒过来，因为这里只有两个图，所以就是G(B)和G(A)。然后把这些G都展开，得到一个列表H={BACEDF}。这个顺序很重要。

第三步

我们把这个图的箭头都倒过来：

图三

然后按照H={BACEDF}里面的顺序，继续染色。重复染色是不允许的。首先是B：

图四

然后是A：

图五

然后是C。注意C可以走到D，所以一起染色：

图六

C后面是E，E后面是D（但是D已经有颜色了跳过），然后是F：

图七

这个算法就完成了。C和D因为互相连通，被我们搞到了一起。其余的ABEF两两都不互相连通，所以是互相独立的。

尾声

第一次看到这个算法的时候整个人都不好了，真是太过于简单以至于我一开始都不相信。查找强连通子图的算法是很常用的，譬如说我们编译TypeScript的import语句，每一个文件就是一个圈，每一个import就是一个箭头，然后我们把关系整理出来之后就来做这个图。如果我们真的找到了任何子图的节点超过1，我们就知道他们互相import了，这是不好的。最重要的是，我们可以生成错误信息了，C.ts和D.ts互相import。

还有类的继承关系也是，C继承D，D继承E，E继承C，这当然是不对的。所以我们要告诉他们，是CDE乱伦了。而不是直接丢一个E给码农让他们自己去找到底乱伦的是哪个部分。