Algorithme de Prim et Kruskal

Question

L'algorithme de Prim et Kruskal produisent tous deux l'arbre couvrant minimal. Selon la propriété cut, le coût total de l'arbre sera le même pour ces algorithmes, mais est-il possible que ces deux algorithmes donnent des MST différents avec le même coût total, étant donné que nous le choisissons dans l'ordre alphabétique face aux choix multiples . par exemple, on compare max (source, dest), pour les arêtes A-> B et B-> C, on compare A de A-> B et B de B-> C.

Merci

Answer 1

En supposant que votre comparateur traite le cas où les deux bords sont égaux dans le coût et le même caractère max (source, dest), il ne sera jamais déclarer les deux bords égaux. Pour qu'il y ait la possibilité de plusieurs MST, au moins deux arêtes dans le graphe doivent être égales. Par conséquent, le MST est unique, et l'algorithme de Prim et Kruskal retournera le même résultat. D'un autre côté, si votre comparateur déclare les arêtes A-> B (coût 1) et A-> C (coût 1) égales, il y a une possibilité que les algorithmes génèrent des MST différents, selon ce qui bord qu'ils considèrent en premier (A-> B ou A-> C).