algorithm - 修正を加えた MST

Question

特定のエッジ (u,v) を含める必要があるように、最小スパニング ツリーのクラスカルのアルゴリズムを変更する方法を考えられる人はいますか?

Answer 1

混乱するかもしれませんが、私が覚えている限りでは、kruskal は負の重みを処理できるので、このエッジの-infinity重みを与えることができます。

• もちろん、実際には ではありませんが、E の各 e の-infinityように、無視できないほど十分に重要な数値です。-1 * sigma(|weight(e)|)

Answer 2

グラフ構造を変更できる場合は、頂点uとを削除vし、以前のエッジ u と v を持つ新しい頂点 w に置き換えることができます。エッジが重複している場合は、重みが最小のものを選択します。

Answer 3

(u,v) の辺の重みがわかっていれば、それを並べ替えた辺の重みのリストの前に追加することもできます (Kruskal が辺の重みを昇順で並べ替えるため)。この場合、エッジ (u,v) がツリーに含まれる最初のエッジになり、Kruskal は通常どおり実行され、(u,v) で最小の重みのスパニング ツリーを見つけます。