在一个DFS中求双图的强连通分量

Question

到目前为止，我已经使用了下面的算法来寻找图的强连通分量。

>

调用DFS(G)计算每个顶点v的完成时间F[v]，对G的顶点按完成时间递减的顺序排序；

计算G的转置GT；

Answer 1

请看，史蒂文·斯基纳的算法设计手册。它在一个DFS中计算SCC。它基于最老可达顶点的概念。

一开始就初始化每个顶点的可达顶点和scComponent#。

low[i] = i;
scc[i] = -1;

在有向图上做一个DFS，你只对后边缘和交叉边缘感兴趣，因为这两个边缘会告诉你是否遇到了后边缘，并从另一个分量中输入了一个分量。

  int edge_classification(int x, int y)
  {
    if (parent[y] == x) return(TREE);
    if (discovered[y] && !processed[y]) return(BACK);
    if (processed[y] && (entry_time[y]>entry_time[x])) return(FORWARD);
    if (processed[y] && (entry_time[y]<entry_time[x])) return(CROSS);
     printf("Warning: unclassified edge (%d,%d)\n",x,y);
  }

if (class == CROSS) 
{
            if (scc[y] == -1)  /* component not yet assigned */
                    if (entry_time[y] < entry_time[ low[x] ] )
                            low[x] = y;
}

process_vertex_early(int v)
{
    push(&active,v);
}

if (low[v] == v) 
{     /* edge (parent[v],v) cuts off scc */
          pop_component(v);
}

if (entry_time[low[v]] < entry_time[low[parent[v]]])
          low[parent[v]] = low[v];