algorithm - 最小全域木から 2 つの頂点間のサブパスを計算する

Question

特定のグラフから最小スパニング ツリー (MST) を取得しました。任意の 2 つの頂点の一意のサブパス (グラフではなく、MST の一部である必要があります) を計算しようとしていますが、効率的な方法を見つけるのに苦労しています。

これまでのところ、クラスカルのアルゴリズム (Disjoint Data 構造を使用) を使用して MST を計算しました (例: A から J までの 10 個の頂点)。 (グラフが無向であると仮定します)。

任意の提案をいただければ幸いです。

Answer 1

これらのパスの 1 つだけが必要な場合は、ツリーの保存方法にもよりますが、ツリーで DFS を実行するのがおそらく最も簡単な解決策です。適切なグラフの場合、DFS を実行するのは簡単ですが、親ポインターのみを保存する場合は、2 つのノードの共通点が最も少ない祖先を見つけるのがより簡単になる可能性があります。

これを行うには、両方のノード u、v からルート r まで歩いてから、r->u パスと r->v パスを比較します。それらが異なる最初のノードは、最も一般的でない祖先です。

線形前処理を使用すると、最も一般的でない祖先クエリに一定の時間で答えることができます。ノードのペア間のパスを頻繁に見つけたい場合は、そのデータ構造の実装を検討することをお勧めします。この論文はそれを非常にうまく説明していると思います。