3

巡回有向グラフがあり、任意の 2 つのノード間で共通の子孫のリストを作成するアルゴリズム (できれば最適なもの) があるかどうか疑問に思っていましたか? Lowest Common Ancestor (LCA) とはほぼ反対のことです。

4

3 に答える 3

2

user1990169 が示唆するように、DFS を使用して開始頂点のそれぞれから到達可能な頂点のセットを計算し、交差点を返すことができます。

これを同じグラフで繰り返し実行する予定がある場合は、最初に強力なコンポーネントを計算して、一連の頂点を表す超頂点に縮小することをお勧めします。副次的な効果として、スーパーバーテックスでトポロジカルな順序を得ることができます。これにより、データ並列アルゴリズムは、同時に複数の開始頂点から到達可能性を計算できます。すべての頂点ラベルを に初期化し{}ます。開始頂点ごとvに、ラベルを に設定し{v}ます。wここで、すべての頂点をトポロジー順にスイープし、wのラベルとxxwのラベルです。セットをコンパクトで効率的に表現するには、ビットセットを使用します。欠点は、単一の到達可能性の計算のようにプルーニングできないことです。

于 2014-08-22T14:32:51.647 に答える
0

エッジの方向を逆にして、LCA を使用しないのはなぜですか?

于 2016-02-29T13:12:01.670 に答える
0

DFS（深さ優先検索）の使用をお勧めします。

For each input node
    Create a collection to store reachable nodes
    Perform a DFS to find reachable nodes
        When a node is reached
            If it's already stored stop searching that path // Prevent cycles
            Else store it and continue

Find the intersection between all collections of nodes

注:必要に応じて、代わりに同じロジックでBFS (幅優先検索) を簡単に使用できます。

これを実装するときは、次のような検索をさらに最適化するために探すことができるいくつかの特別なケースがあることに注意してください。

  • 入力ノードに頂点がない場合、共通ノードはありません
  • 1 つの入力ノード (A) が別の入力ノード (B) に到達すると、A は B が到達できるすべてのノードに到達できます。
    これは、アルゴリズムを B で実行する必要がないことを意味します。
  • 等
于 2014-08-22T14:32:30.923 に答える