Mini wiki
Kosaraju算法
编辑
Kosaraju算法是一个在线性时间内寻找一个
图
中的
强连通分量
的算法。
阿尔佛雷德·艾侯
,约翰·霍普克洛夫特和
杰弗瑞·乌尔曼
相信该算法来自S·拉奥·科萨拉朱于1978年撰写的一篇未发表论文之中。米卡·夏尔也独立发现了该算法并于1981年将其发表。该算法巧妙地利用了一个定理:“一个图的反向图和原图具有一样的强连通分量”。
1
相关
Tarjan算法
是一个在图中寻找强连通分量的算法。虽然发表时间更早,它仍可以被视为
Kosaraju算法
的一个改进。它的效率跟Gabow算法差不多。