algorithm - 重みが 1 と 2 のみのスパニング ツリーを見つけるアルゴリズム

Question

各辺の重みが 1 と 2 だけの、重み付き接続された単純な無向グラフ G が与えられた場合、O(V+E) で G の MST を見つけます。何か案は？

質問の言い回しで申し訳ありませんが、できる限り翻訳してみました。

Answer 1

Prim のアルゴリズムでは、最小の重みでエッジにアクセスして削除できるように、アクティブなエッジを保存する方法が必要です。

通常、さまざまな重みがあり、エッジを格納するためにある種のヒープ データ構造が使用されます。

ただし、この場合、重みは 1 または 2 であるため、重み 1 のエッジ用と重み 2 のエッジ用の 2 つの個別のリストにエッジを格納するだけです。

重みが最小のエッジを見つけるには、最初のリストから 1 つを取得します。空の場合は、2 番目のリストからエッジを取得します。

リストからの要素へのアクセスと削除は O(1) なので、Prim のアルゴリズムは O(V+E) で実行されます。

Answer 2

Prim のアルゴリズムは、エッジに任意の重みがある場合に最小全域木を計算します。

プリムのアルゴリズムは、任意のノードから開始し、エッジを優先キューに保持する、一種の幅優先検索を実行することによって機能します。最も重みの低いエッジを抽出し続け、検索を拡張せずにそれを破棄するか (エッジが既にツリー内のノードにつながる場合)、それを結果に追加して、反対側のノードをツリー内としてマークし、検索を拡張します。

先ほど説明した素朴な方法で行われた Prim のアルゴリズムは、|E|エッジを優先キューに入れたりキューから取り出したりするコストによって支配されます。各エンキュー/デキューにはO(log |E|)時間がかかるため、総漸近コストはO(|E| log |E|)時間、より正確にはO(|E| log |E| + |V|).

これらのエンキューとデキューを一定時間で行う方法があれば、合計実行時間はO(|E| + |V|)...