有向图的强连通分量及应用

有向图的强连通分量应用非常广泛,比如有向图的强连通分量数量巨大的时候,为了更加高效必须要用缩点法。深度优先遍历是求有向图的强连通分量的一个有效方法,根据实现方式的不同,总体上,求有向图的强连通分量有三种算法,分别是Kosaraju算法,Gabow算法和Tarjan算法。三种算法的时间复杂度均为O(n+e)(n为顶点数,e为边数)。