algorithm - 最小スパニングツリーのカットについて

Question

最小スパニングツリーアルゴリズムについて読んでいます。カットについて言及されています。無向グラフのカット（S、VS）G =（V、E）は、Vのパーティションです。エッジは、その重みがカットを横切るエッジの最小値である場合、カットを横切るライトエッジです。

上記の定義は、クラスカル法とプリム法でどのように使用されますか？

KruskalsとPrimのアルゴリズムでカットがどのように使用されているのかわかりません

ありがとう

Answer 1

プリムのアルゴリズムでは、最初に頂点（任意）が選択されます。ここで、選択した頂点がに属しS、残りがになるようにカットしますV-S。ここで、最も軽いウェイトエッジを選択し、接続する頂点をに追加しSます。そして、すべての頂点がになるまでそれを続けますS。

クラスカルのアルゴリズムでは、グラフの最小重みエッジをセットに追加し続けますS。グラフは任意の方法でカットできますが、そのカットが最小ウェイトエッジを通過する場合、そのエッジが最も軽いエッジになります。また、最小スパニングツリーに追加する必要があります（2つの異なるツリーを接続する場合）。

それがお役に立てば幸いです。