Implementation (Part 1)
Coddy'nin Kruskal Algoritması - Graf Algoritmaları kursunda ders 5 / 9.
Döngü tespit motoru olan union-find ile başlıyoruz.
Görev
OrtaKruskal'ın döngü testi union-find yapısına dayanır. Bağlı bileşenleri saymak için önce bunu inşa edelim.
n ve düz edges dizisini (üçlüler [u, v, w, ...], yönsüz; buradaki ağırlıkları yoksayın) alan ve union-find ile hesaplanan bağlı bileşenlerin sayısını döndüren countSets adında bir fonksiyon yazın.
Örneğin, 4 köşe ve [0,1,5, 2,3,5] kenarları ile 2 bileşen vardır: {0,1} ve {2,3}.
Kendin dene
#include <stdlib.h>
int countSets(int n, int* edges, int edges_size) {
// Buraya kod 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