Implementation (Part 2)
Coddy'nin Kruskal Algoritması - Graf Algoritmaları kursunda ders 6 / 9.
Şimdi MST tamamlanana kadar en ucuz güvenli kenarı ekleyin.
Görev
OrtaŞimdi MST'yi oluşturun.
n değerini ve bağlı bir grafiğin düz edges dizisini (üçlüler, yönsüz) alan ve bu grafiğin Minimum Yayılan Ağacının toplam ağırlığını döndüren kruskal adında bir fonksiyon yazın.
Sürekli olarak en ucuz kullanılmamış kenarı alın; eğer uç noktaları farklı kümelerdeyse, onları birleştirin ve ağırlığını ekleyin; aksi takdirde bu kenarı atlayın.
Önceki dersteki union-find fikrini tekrar kullanın.
Kendin dene
#include <stdlib.h>
int kruskal(int n, int* edges, int edges_size) {
// Kodu buraya yazın
return 0;
}
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