ツリー構造のデータで機能するツールを書きたいと思います。(実際には、git リビジョン DAG のツリーのようなサブセットで動作しますが、それはこの質問では重要ではありません)。特に、特定の入力セットのすべての「結合ポイント」からなるツリーのサブセットを再構築するアルゴリズムが必要です。
具体的に私が欲しいと思うのは
H「最小共通祖先」関数を持つ型がありlcaます。これによりH、ツリーのような構造が得られます。このアルゴリズムは、 のサブセット
SをH入力として受け取ります。t出力は、 の値でラベル付けされたノードを持つ多元木になりますH。tプロパティを満たす必要がありますすべて
sのSラベルの一部のノードtの葉は、 の
t要素によってのみラベルを付けることができますSのノードが 1 つ以下
hのラベルの任意の要素Hth1labelsn1とh2labelsの場合、との最小共通祖先にラベルをn2付けます。lca(h1, h2)n1n2t
私の質問は、「これは既知のアルゴリズムの既知の問題ですか?」です。そうだと思います。トポロジカルソートに非常に似ているようです。マージソートに基づくアルゴリズムのアイデアはありますが、既知のアルゴリズムが既に存在する場合、独自のアルゴリズムを思いつく理由はありません。