有向非巡回グラフで複数のノードの最も一般的でない祖先を見つけるにはどうすればよいですか?
このトピックに関するかなりの数の論文を見つけましたが、それらはすべて、2 つのノードの DAG で LCA を見つけたようです。
複数のノードに適したアルゴリズムはありますか?
質問する
3201 次
2 に答える
2
ツリーに使用されるアルゴリズムを、DAG にも適用されるように変更できるかもしれません。
ご存知かもしれませんが、ツリーで LCA を見つけるアルゴリズムは、クエリごとにO(nlgn)の前処理とO(1)の処理があるため、 kノードの LCA を見つけるにはO(k)が必要です。このアルゴリズムの詳細については、こちらを参照してください。于 2013-01-03T18:33:39.343 に答える