1

これまで、グラフの強連結成分を見つけるために次のアルゴリズムを使用しました。

  1. DFS（G）を呼び出して、すべての頂点vの終了時間f [v]を計算し、Gの頂点を終了時間の降順で並べ替えます。

  2. Gの転置GTを計算します。

  3. Gで別のDFSを実行します。今回は、メインのforループで、f[v]の降順でGの頂点を通過します。

  4. DFSフォレスト（2番目のDFSによって形成される）の各ツリーの頂点を、個別の強連結成分として出力します。

。

しかし、 1つのDFSだけですべての強く接続されたコンポーネントを見つけることができるかどうか疑問に思いました。

この点での助けをいただければ幸いです。

4

2 に答える 2

2

Steven Skiena による Algorithm Design Manual を参照してください。1 つの DFS で SCC を計算します。これは、到達可能な最も古い頂点の概念に基づいています。

最初に、各頂点の到達可能な頂点と SCComponent# をそれ自体に初期化します。

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

有向グラフで DFS を実行します。バック エッジとクロス エッジのみに関心があります。バック エッジに遭遇し、別のコンポーネントから 1 つのコンポーネントに入る場合、これらの 2 つのエッジからわかるからです。

  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 == BACK) { if (entry_time[y] < entry_time[ low[x] ] ) low[x] = y; }

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

頂点 'v' から到達可能な最も低い頂点がそれ自体である場合は常に、新しい強連結コンポーネントが検出されます (ループは、a->b->c->a と言うことができ、a の到達可能な最も低い頂点は a です)。

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

頂点の DFS が完了したら (隣接する頂点の DFS も完了しているはずです)、到達可能な最下位の頂点を確認します。

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];

pop_component(...) は、このコンポーネントが見つかるまでスタックからポップします。a->b->c->a がスキャンされた場合、スタックは a(bottom)->b->c(top).. 頂点 'a' が表示されるまでポップします。「a」の SCC を取得します。同様に、1 つの DFS ですべての接続されたコンポーネントを取得します。

于 2012-10-23T23:13:31.790 に答える
2

強く接続されたコンポーネントのウィキペディアのページでこれを見つけました：

Kosaraju のアルゴリズム、Tarjan のアルゴリズム、およびパスベースの強成分アルゴリズムはすべて、有向グラフの強連結成分を効率的に計算しますが、Tarjan のアルゴリズムとパスベースのアルゴリズムは、深さ優先探索が 2 つではなく 1 つしか必要ないため、実際には好まれます。

これはあなたの質問にかなり答えると思います:)

于 2012-10-23T15:11:04.753 に答える