Gabowアルゴリズム【nocowから回転】

Gabowアルゴリズム
[編集]図強度への接続成分がある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;
  }
}