Implementasi (Bagian 2)
Pelajaran 6 dari 9 dalam kursus Algoritma Kruskal: Algoritma Graf di Coddy.
Sekarang tambahkan sisi aman termurah hingga MST selesai.
Tantangan
SedangSekarang bangun MST.
Tulis fungsi bernama kruskal yang menerima n dan array edges datar (tripel, tak berarah) dari graf terhubung, lalu mengembalikan total bobot Minimum Spanning Tree-nya.
Ambil berulang kali edge belum terpakai dengan bobot paling kecil. Jika kedua titik ujungnya berada dalam set yang berbeda, gabungkan keduanya dan tambahkan bobot edge tersebut. Jika tidak, lewati edge itu.
Gunakan kembali ide union-find dari pelajaran sebelumnya.
Coba sendiri
#include <stdlib.h>
int kruskal(int n, int* edges, int edges_size) {
// Tulis kodemu di sini
return 0;
}
Uji dirimuPelajaran ini berisi kuis singkat. Mulai pelajarannya untuk menjawab kuis dan melacak progresmu.
Semua pelajaran di Algoritma Kruskal: Algoritma Graf
2Algoritma
Bagaimana cara kerjanya?Kode SemuImplementasi (Bagian 1)Implementasi (Bagian 2)
Kompleksitas Waktu dan RuangLatihan sendiri: Compiler C online