3

目標:

グラフ内のノードが 0、1、または 2 つの親を持つことができるグラフの最適な共通祖先を見つけるアルゴリズムを探しています。「最良の共通祖先」の用語がよくわかりません。より適切な用語は、「最小の共通の祖先」または「最近の共通の祖先」などです。より適切な用語がある場合は、そのような用語を説明する URL を提供してください。

このアルゴリズムは、完全なグラフ データ構造にアクセスできます。

特定のノードがゼロ、1 つ、または 2 つの親を持つことができます。私が Web で見たアルゴリズムは、特定のノードに 0 または 1 つの親があり、2 つの親はないと想定しているため、これが重要です (以下の参考文献を参照)。たとえば、下の図の m1 ノードはルートであるため、親がありません (グラフの複数のルートが存在する可能性があります)。d3 には 2 つの親があり、1 つは d2 で、もう 1 つは b2 です。

ノードには、存在する場合は両方の親への参照があり、存在する場合はすべての子への参照があるため、ツリーを上下にトラバーサルするのは公正なゲームです。ノードは 0 個以上の子を持つことができます。データ構造を変更することはオプションではありません。

2 つの入力ノードに近いノードは、遠いノード (つまり、グラフのルートに近いノード) よりも優先されます。

例として、考えられるグラフの 1 つを以下の図に示します。このシナリオでは、アルゴリズムへの入力はノード b5 と d4 になります。ノード b5 と d4 の最良の共通祖先は b2 です。b3 は b5 につながる血統にあるため、c2 はありません。

アルゴリズムの可能な答えは最大で 1 つのノードであり、空のセットは 2 つの入力ノードの共通の祖先がない場合の有効な答えです。

参考資料

Tarjan のオフラインの最小共通祖先アルゴリズムは、0 または 1 つの親を暗示しているように見えるため、それが解決策である場合、そのアルゴリズムで 2 つの親がどのように考慮されるかについての説明を回答に含める必要があります。最低共通祖先のウィキペディアのページも、ノードが 2 つではなく、0 または 1 つの親を持つデータ構造のみを説明しているようです。

各ノードがその親を指すツリー データ構造では、...

図：

グラフ図

4

1 に答える 1

1

家系図のウェブサイトを運営しており、以前に次のアルゴリズムでこの問題を解決しました。

両方のノードに対して、再帰を使用して、ノード名と世代をリンクする配列を生成します。あなたの例を使用すると、b4はb5より1世代上です。b3 は 2 世代です。等：

$b5Tree = array('b4'=>1, 'b3'=>2, 'c3'=>2, 'b2'=>3, 'c2'=>3, ...);
$d4Tree = array('d3'=>1, 'b2'=>2, 'd2'=>2, 'b1'=>3, 'd1'=>3, ...);

基本的なケースは、最初のノードが 2 番目のノードのツリーに表示されるかどうかを確認することです。存在する場合は、答えがあります。

それ以外の場合は、ツリーの 1 つを繰り返し処理し、共通のノード ID を見つけて、最小世代を追跡します。

$minNodeID = null;
foreach ($b5Tree as $nID => $gen)
{
    if (($d4Tree[$nID] != 0) and (($d4Tree[$nID]  + $gen) < $minSummedGen))
    {
        $minSummedGen = $d4Tree[$nID] + $gen;
        $minNodeID = $nID;
    }
}
return $minNodeID;
于 2011-05-25T00:10:27.680 に答える