咱科薩拉朱演算法

Kosaraju 演算法（嘛予人號做Kosaraju–Sharir 演算法）是一个佇線性時間內底走揣一个有向圖內底的強連通元件的演算法。阿爾佛雷德 ・ 艾侯，約翰 ・ 霍普克洛夫特佮傑馮瑞 ・ 烏爾曼相信這個演算法來自 S ・ 拉奧 ・ 科薩拉朱佇一九七八年編寫的一篇無發表論文之中。米卡 ・ 夏爾也獨立發現這个算法並且一九八一年共其發表。該演算法巧妙地利用一个定理：「 一个圖的顛倒向圖佮原圖有仝款的模樣連通元件」。

簡介

該演算法主要是用於列舉圖內底每一个強調通元件內的所有頂點。該演算法會由以下四部份組成：

一 . 嘿有向圖 $ G $ 取逆，得著 $ G $ 的反向圖 $ G ^ { R } $ 二 . 利用深度優先搜揣出 $ G ^ { R } $ 的倒反排序三 . 著 $ G $ 照理述逆後排序的序列進行深度優先搜揣四 . 仝一个深度優先搜揣遞迴子程式內底存取的所有頂點攏佇仝一个強連通元件內底

複雜度

當圖是使用鄰接表形式的組建的，Kosaraju 演算法需要對規張圖來進行了兩擺的完整的存取，逐改閣存取佮頂點數 $ V $ 佮邊仔數 $ E $ 之和 $ V + E $ 成正比，所以會當佇線性時間 $ O ( V + E ) $ 內存取完成。該演算法佇實際操作中愛比 Tarjan 演算法佮基於路徑的強連通元件演算法愛慢，這兩種演算法攏只要對圖來進行一擺完整的存取。

當圖是使用鄰接矩陣形式組建的，演算法的時間複雜度做 $ O ( V ^ { 二 } ) $。

文獻佮連結

• （[/ / web . archive . org / web / 二十五空一千九百空四石一千三百一十一孵五千六百一十八 / http : / / www . sciencedirect . com / science / article / pii / 八百九十八分一千二百二十一分八千一百九十五空八十頁面存檔備份，存在網路檔案館）Micha Sharir . A strong connectivity algorithm and its applications to data flow analysis . _ Computers and Mathematics with Applications _ 七 ( 一 ) : 六十七–七十二 , 一千九百八十一] ]
• Kosaraju's 的簡要介紹佮證明