Prim のアルゴリズムと Kruskal のアルゴリズムはどちらも最小全域木を生成します。cut プロパティによると、ツリーの総コストはこれらのアルゴリズムで同じになりますが、複数の選択肢に直面したときにアルファベット順に選択することを考えると、これら 2 つのアルゴリズムが同じ総コストで異なる MST を与える可能性はありますか? . たとえば、エッジ A->B および B->C について max(source,dest) を比較し、A->B からの A と B->C からの B を比較します。
ありがとうございました
コンパレータが両方のエッジのコストが等しく、同じ max(source, dest) 文字を持つ場合を処理すると仮定すると、2 つのエッジが等しいと宣言されることはありません。複数の MST が存在する可能性があるためには、グラフ内の少なくとも 2 つのエッジが等しくなければなりません。したがって、MST は一意であり、Prim のアルゴリズムと Kruskal のアルゴリズムの両方が同じ結果を返します。
一方、コンパレータがエッジ A->B (コスト 1) と A->C (コスト 1) が等しいと宣言した場合、アルゴリズムが最初に考慮するエッジに応じて、異なる MST を生成する可能性があります。 (A->B または A->C)。