强连通分量 编辑
在有向图的数学理论中，如果一个图的每一个顶点都可从该图其他任意一点到达，则称该图是强连通的。在任意有向图中能够实现强连通的部分我们称其为强连通分量。判断一个图是否为强连通以及找到一个图强连通分量只需要线性时间。
1
相关
Kosaraju算法是一个在线性时间内寻找一个图中的强连通分量的算法。阿尔佛雷德·艾侯，约翰·霍普克洛夫特和杰弗瑞·乌尔曼相信该算法来自S·拉奥·科萨拉朱于1978年撰写的一篇未发表论文之中。米卡·夏尔也独立发现了该算法并于1981年将其发表。该算法巧妙地利用了一个定理：“一个图的反向图和原图具有一样的强连通分量”。