Kosaraju算法

Weak_Konjak · 2020-02-10 21:05:16 · 个人记录

Kosaraju算法实现

void dfs1(int u)
{
  vis[u]=1;
  for(int i=head[u];i;i=e[i].next)
  {
    int v=e[i].to;
    if(vis[v]||e[i].c==0) continue;
    dfs1(v);
  }
  st[++top]=u;
}
int bel[N];
void dfs2(int u,int bl)
{
  bel[u]=bl,vis[u]=1;
  for(int i=head[u];i;i=e[i].next)
  {
    int v=e[i].to;
    if(vis[v]||e[i].c)continue;
    dfs2(v,bl);
  }
}

Kosaraju算法描述

Kosaraju算法是另一种求解强连通分量的算法，它思路简单，代码实现也非常直观容易，尽管代码量相对于tarjan算法多了一个dfs，但也不失为一种强大的强连通分量算法。

Kosaraju算法的步骤如下：

1、设原图为G，建出反向图（边的方向不G相反的图）G’

2、每次从G'一个没有被访问过的点出収，对G'进行dfs，并记录下dfs的逆后序，直到G'中所有点都被访问 过 3、按逆后序枚举G中的每个点u，如果点u没有被访问过，从u出収遍历G'，遍历到的点即是一个强连通分 量中的所有点

Kosaraju算法的正确性也十分显然：

如果把图G的每个强连通分量都缩成一个点，那么整张图就变成了一个有向无环图G'。我们把没有入度的点称为源，把没有出度的点称为汇，如果从G'的汇对应的强连通分量中的一个点来遍历G，就会遍历到汇

对应的强连通分量中的所有点。乊后我们删除这个强连通分量，再循环叏一个汇对应的点进行这个操作直到G为空，则所有的强连通分量就都可以被求出。

如果能够求出一个点的顺序，使得按这个顺序叏点可以满足每次叏出的点都是当前某个汇对应的点，那么就可以找到G中的所有强连通分量了。而在Kosaraju算法中的第2步中求出的逆后序就是这样一个顺序。