使用者: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給碼農讓他們自己去找到底亂倫的是哪個部分。