32

次のような有向非巡回グラフを想像してください。

  • "A" はルートです (ルートは常に 1 つだけ存在します)。
  • 各ノードはその親を知っています
  • ノード名は任意です - それらから何も推測できません
  • 別の情報源から、ノードが A から G の順序でツリーに追加されたことがわかります (たとえば、バージョン管理システムでのコミットです)。

有向非巡回グラフ

任意の 2 つのノードの最小共通祖先 (LCA) を決定するためにどのアルゴリズムを使用できますか。たとえば、次の共通祖先は次のとおりです。

  • B と E は B
  • D と F は B

ノート：

4

11 に答える 11

5

同じ問題の解決策を探していたところ、次の論文で解決策を見つけました。

http://dx.doi.org/10.1016/j.ipl.2010.02.014

つまり、最下位の共通祖先を探しているのではなく、このペーパーで定義されている最下位の SINGLE 共通の祖先を探しているのです。

于 2013-02-18T03:08:29.603 に答える
2

ちょっとワイルドな考え。両方の入力ノードをルートとして使用し、2 つの BFS を段階的に同時に実行するのはどうでしょうか。あるステップで、BLACK セット (訪問したノードの記録) に重複がある場合、アルゴリズムは停止し、重複したノードが LCA になります。このようにして、他の共通の祖先は、私たちが発見したものよりも距離が長くなります.

于 2014-05-22T22:48:42.393 に答える
0

DAG（有向非巡回グラフ）でLCAを見つけるためにも、まったく同じことが必要です。LCA の問題は、RMQ (Range Minimum Query Problem) に関連しています。

LCA を RMQ に縮小し、有向非巡回グラフから任意の 2 つのノードの目的の LCA を求めることができます。

このチュートリアルの詳細と良いことがわかりました。こちらも実装予定です。

于 2013-03-14T07:16:04.120 に答える
0

グラフにサイクルがある場合、「祖先」は大まかに定義されます。おそらく、DFS または BFS のツリー出力の先祖のことでしょうか? または、おそらく「先祖」とは、からのホップ数を最小化するダイグラフ内のノードを意味しますEかB?

複雑さを気にしなければ、すべてのノードから と の両方への A* (またはダイクストラの最短経路) を計算できEますB。Eと の両方に到達できるノードについては、Bを最小化するノードを見つけることができますPathLengthToE + PathLengthToB。

編集：いくつかのことを明確にしたので、あなたが探しているものを理解していると思います.

ツリーを「上る」ことしかできない場合は、 から BFS を実行し、Eさらにから BFS を実行することをお勧めしますB。グラフ内のすべてのノードには、それに関連付けられた 2 つの変数があります: hops fromBと hops from E. グラフ ノードのリストのコピーをBとの両方にします。のリストは からのホップ数でソートされ、のリストは からのホップ数でソートされます。EBBEE

のリスト内の各要素について、Bのリストでそれを見つけようとしますE。一致するものを 3 番目のリストに配置し、 からのホップB+ からのホップでソートしEます。Bのリストを使い果たした後、3 番目にソートされたリストの先頭に LCA が含まれているはずです。これにより、1 つの解、複数の解 ( の BFS 順序付けによって任意に選択B)、または解なしが可能になります。

于 2013-02-14T00:09:58.497 に答える