Apakah algoritma Kruskal dan Prim menghasilkan pohon spanning minimum yang sama?

9

Dengan asumsi ujung-ujungnya tidak diarahkan, memiliki bobot yang unik, dan tidak ada jalur negatif, apakah algoritma ini menghasilkan Pohon Pembentang Minimum yang sama?

graphs trees minimum-spanning-tree Death_by_Ch0colate
sumber
3
Ya, dan mereka tampaknya menghasilkan MST yang sama. Tapi itu tidak pasti.
Death_by_Ch0colate
2
Ok, itu benar, hanya memeriksa.
Evil
Jawabannya tetap positif bahkan jika kita menghapus kondisi "tidak ada jalan negatif"
John L.
Silakan periksa apakah semua pohon merentang minimum dapat dijangkau oleh Kruskal dan Prim? dan Kapan spanning tree minimum untuk grafik tidak unik
John L.

Jawaban:

13

Menemukan ini yang menyatakan bahwa jika semua kondisi yang saya sebutkan di atas terpenuhi, grafik tentu memiliki MST yang unik. Oleh karena itu, dalam hal pertanyaan saya, algoritma Kruskal dan Prim tentu menghasilkan hasil yang sama.

Death_by_Ch0colate
sumber
7

Jika MST itu unik, semua algoritme akan terpaksa memproduksinya.

Jika MST tidak unik, output mungkin berbeda karena pesanan pemrosesan simpul yang berbeda (bahkan dua implementasi berbeda dari algoritma yang sama dapat), tetapi bobot total akan sama. Dalam hal ini, MST adalah istilah yang salah.

Yves Daoust
sumber
Mereka tentu saja mungkin, tetapi apakah mereka?
Raphael
4
@ Raphael: Saya jawab itu.
Yves Daoust
1
@Ya Tidak, kamu tidak. Anda bilang mungkin, " mungkin " bukan jaminan. Misalnya, jika Anda memiliki algoritma pengurutan, dan mereka stabil, mereka tidak menghasilkan output yang sama, terlepas dari algoritma yang digunakan. Jika mereka tidak stabil mereka mungkin menghasilkan hasil yang sama. Jadi pertanyaannya adalah apakah algoritma tersebut memiliki rasa stabilitas terhadap topik dan menunjukkannya.
Luk32
@ Lukuk32: apakah Anda membaca "bahkan dua implementasi berbeda dari algoritma yang sama bisa"? Omong-omong, algoritma penyortiran stabil menghasilkan output yang sama karena didefinisikan secara unik, sehingga mereka tidak punya pilihan. Jika stabilitas tidak diperlukan, solusinya tidak unik dan implementasi yang berbeda mungkin berperilaku berbeda.
Yves Daoust
Cukup adil, tetapi pernyataan itu tidak jelas. Apa yang membuat implementasinya tidak stabil? Apakah ada semacam penyortiran yang terlibat dan stabilitas tergantung pada ini?
Luk32
2

Untuk menambahkan jawaban Yves Daoust , grafik berikut

Segi tiga

Dalam grafik ini, kami memiliki 3 node dan 3 edge, masing-masing memiliki bobot yang sama. Jelas setiap 2 tepi akan membentuk MST untuk grafik ini. Namun, dua sisi yang dipilih akan bergantung pada tidak hanya algoritma, tetapi implementasi algoritma. Misalnya, jika saya menyimpan node dalam daftar, saya dapat mengunjungi mereka dalam urutan yang berbeda daripada jika saya menyimpan node dalam satu set, bahkan jika saya menggunakan algoritma MST yang sama sejak saat itu.

Bahkan, jika implementasi saya bergantung pada aritmatika pointer (yang dilakukan beberapa wadah dalam beberapa bahasa), saya bahkan dapat memilih MST yang berbeda setiap kali saya menjalankan algoritme!

Cort Ammon
sumber
1
Perhatikan bahwa pos asli menyatakan bahwa tepian memiliki bobot yang unik; ini tentu saja menjamin MST yang unik.
wchargin
Poin terakhir itu juga berlaku ketika menggunakan eg setatau dictdalam Python 3.3+: hash digarami dengan nilai yang berbeda untuk setiap proses untuk membuat serangan denial-of-service lebih sulit.
Jasmijn
@ YvesDaoust Sangat menyesal tentang itu!
Cort Ammon
@CortAmmon: jangan khawatir, itu terjadi.
Yves Daoust