Time and Space Complexity
Coddy'nin Kruskal Algoritması - Graf Algoritmaları kursunda ders 7 / 9.
Zaman Karmaşıklığı:
- E kenarlarını sıralamak O(E log E) süresidir; yol sıkıştırma (path compression) ile her union-find işlemi neredeyse O(1)'dir, bu nedenle klasik Kruskal O(E log E) süresidir. Burada oluşturduğumuz minimum seçim versiyonu O(E2) süresidir, bu da küçük grafikler için uygundur.
Alan Karmaşıklığı:
- Ebeveyn dizisi (artı girdi kenarları) için O(V).
Özet:
- Kruskal, döngüleri test etmek için union-find kullanarak her adımda en ucuz döngüsüz kenarı ekleyerek bir MST büyütür.
- Tüm MST'ler aynı toplam ağırlığı paylaşır, bu nedenle cevap benzersizdir.
Kendin dene
Bu ders bir kod alıştırması içermiyor.
Kendini test etBu ders kısa bir quiz içerir. Soruları yanıtlamak ve ilerlemeni kaydetmek için derse başla.
Kruskal Algoritması - Graf Algoritmaları bölümündeki tüm dersler
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity