(资料图片仅供参考)

1、 在计算机科学中，Kosaraju的算法（也称为Kosaraju-Sharir算法）是线性时间的算法来找到一个有向图的强连通分量。

2、 Aho, Hopcroft 和Ullman相信这个算法是由S. Rao Kosaraju在1978在一个未发表的论文上提出的。

3、 相同的算法还从Micha Sharir 1981年自己出版的书上被单独的发现，这个算法利用了一个事实，即转置图（同图中的每边的方向相反）具有和原图完全一样的强连通分量。

文章到此就分享结束，希望对大家有所帮助。

标签： 连通分量 方向相反 计算机科学 找到一个