Gabow算法

来自NOCOW

[编辑] 求解有向图强连通分量的Gabow算法

Gabow算法与Tarjan算法的核心思想实质上是相通的,就是利用强连通分量必定是DFS的一棵子树这个重要性质,通过找出这个子树的根来求解强分量.具体到实现是利用一个栈S来保存DFS遇到的所有树边的另一端顶点,在找出强分量子树的根之后,弹出S中的顶点一一进行编号. 二者不同的是,Tarjan算法通过一个low数组来维护各个顶点能到达的最小前序编号,而Gabow算法通过维护另一个栈来取代low数组,将前序编号值更大的顶点都弹出,然后通过栈顶的那个顶点来判断是否找到强分量子树的根

int Gabow(Graph G) {
  // 初始DFS用到的全局变量
  S = StackInit(G->V);  // S用来保存所有结点
  P = StackInit(G->V);  // P用来维护路径
  int v;
  for (v = 0; v < G->V; ++v)
    pre[v] = G->sc[v] = -1;
  cnt = id = 0;
  // DFS
  for (v = 0; v < G->V; ++v)
    if (pre[v] == -1)
      GabowDFS(G, v);
  // 释放栈空间
  StackDestroy(S);
  StackDestroy(P);
  return id;  // 返回id的值,这恰好是强连通分量的个数
}
 
void GabowDFS(Graph G, int w) {
  Link t;
  int v;
  pre[w] = cnt++;  // 对前序编号编号
  StackPush(S, w);  // 讲路径上遇到的树边顶点入栈
  StackPush(P, w);
  for (t = G->adj[w]; t; t = t->next) {
    if (pre[v = t->v] == -1)                  // 如果当前顶点以前未遇到,则对其进行DFS
      GabowDFS(G, v);
    else if (G->sc[v] == - 1)                 // 否则如果当前顶点不属于强分量
      while (pre[StackTop(P)] > pre[v])  // 就将路径栈P中大于当前顶点pre值的顶点都弹出
        StackPop(P);
  }
  if (StackTop(P) == w) {  // 如果P栈顶元素等于w,则找到强分量的根,就是w
    StackPop(P);
    do {
      v = StackPop(S);  // 把S中的顶点弹出编号
      G->sc[v] = id;
    } while (v != w);
    ++id;
  }
}