2019-05-22

有向图的强连通分支之Kosaraju算法

缘起

【3】给出了有向图的强连通分支（下简称scc）的定义，【1】和【2】给出了求解scc的深搜算法和tarjan算法. 这里介绍kosaraju算法

分析

经过分析, 其实kosaraju算法就是【1】. kosaraju算法和另外2种算法——tarjan、gabo比较，后两者只需要一次深搜，但是本算法需要2次深搜。虽然三种算法都是线性的. O(n+e), 但是kosaraju算法性能较低（实测低30%左右）. 但是kosaraju的好处在于第一次dfs之后就已经将所有的scc已经拓扑排序了.

参考

【1】https://yfsyfs.github.io/2019/05/22/%E6%9C%89%E5%90%91%E5%9B%BE%E7%9A%84%E5%BC%BA%E8%BF%9E%E9%80%9A%E5%88%86%E6%94%AF%E4%B9%8B%E6%9C%B4%E7%B4%A0%E6%B1%82%E6%B3%95-%E5%88%A9%E7%94%A8%E6%B7%B1%E6%90%9C/

【2】

https://yfsyfs.github.io/2019/05/22/%E6%9C%89%E5%90%91%E5%9B%BE%E7%9A%84%E5%BC%BA%E8%BF%9E%E9%80%9A%E5%88%86%E6%94%AF%E4%B9%8BTarjan%E7%AE%97%E6%B3%95/

【3】https://yfsyfs.github.io/2019/05/22/%E6%9C%89%E5%90%91%E5%9B%BE%E7%9A%84%E5%BC%BA%E8%BF%9E%E9%80%9A%E5%88%86%E6%94%AF/