Minimum Spanning TreeLesson 38Preview gratis
Minimum Spanning Tree
Lesson ini bagian dari DSA · Semua level
Ringkasan
Minimum spanning tree adalah subgraph yang menyertakan seluruh simpul dengan total bobot minimum tanpa membentuk siklus. Dua algoritma klasik untuk membangunnya adalah Prim yang tumbuh dari satu simpul dan Kruskal yang menyambung sisi terkecil. MST berguna untuk merancang jaringan murah seperti kabel dan pipa.
Poin kunci
- MST menyertakan semua simpul tanpa siklus dengan bobot minimum
- Pada graf berbobot terhubung, MST memiliki V-1 sisi
- Prim tumbuh dari satu simpul, Kruskal mengurutkan semua sisi
- Penerapan: desain jaringan, klasterisasi, dan pipeline
Materi lengkap
Contoh kode dan kuis
Materi lengkap, contoh kode, dan kuis tersedia untuk pelanggan. 5 soal.