次のような有向非巡回グラフを想像してください。
- "A" はルートです (ルートは常に 1 つだけ存在します)。
- 各ノードはその親を知っています
- ノード名は任意です - それらから何も推測できません
- 別の情報源から、ノードが A から G の順序でツリーに追加されたことがわかります (たとえば、バージョン管理システムでのコミットです)。
任意の 2 つのノードの最小共通祖先 (LCA) を決定するためにどのアルゴリズムを使用できますか。たとえば、次の共通祖先は次のとおりです。
- B と E は B
- D と F は B
ノート:
- ルートから特定のノードへの単一のパスがあるとは限りません (たとえば、「G」には 2 つのパスがあります)。そのため、ルートから 2 つのノードへのパスを単純にたどって、最後の等しい要素を探すことはできません。
- ツリー、特にバイナリ ツリーの LCA アルゴリズムを見つけましたが、ノードは複数の親を持つことができるため (つまり、これはツリーではない)、ここでは適用されません。