强连通分量是有向图中的最大顶点子集,其中任意两个顶点之间都存在可达路径。Kosaraju算法通过两次DFS找出所有强连通分量。
强连通分量(Strongly Connected Component, SCC)是有向图中的一个子图,其中任意两个顶点之间都存在相互可达的路径。换句话说,在一个强连通分量中,从任意顶点出发都能到达该分量中的其他所有顶点。强连通分量算法用于将有向图分解为多个强连通子图,这在许多图论应用中非常重要。两种常用的强连通分量算法是Kosaraju算法和Tarjan算法,本教程将主要介绍这两种算法。
假设有一个包含8个顶点(0-7)的有向图,边的关系如下:
...