Minimum Spanning Tree dengan Algoritma Prim dan Kruskal

Algoritma Prim dan Algoritma Kruskal adalah dua buah algoritma greedy untuk mencari pohon merenang minimum (minimum spanning tree).implementasi program Prim dan Kruskal dengan Bahasa C++. Program menerima input berupa file teks (misal graf.txt) yang berisi matrik ketetanggaan sebuah graf.

Algoritma Prim

Algoritme Prim adalah sebuah algoritme dalam teori graf untuk mencari pohon rentang minimum untuk sebuah graf berbobot yang saling terhubung. Ini berarti bahwa sebuah himpunan bagian dari edge yang membentuk suatu pohon yang mengandung node, di mana bobot keseluruhan dari semua edge dalam pohon diminimalisasikan. Bila graf tersebut tidak terhubung, maka graf itu hanya memiliki satu pohon rentang minimum untuk satu dari komponen yang terhubung. Algoritme ini ditemukan pada 1930 oleh matematikawan Vojtěch Jarník

Algoritma Kruskal

Algoritma Kruskal adalah algoritma dalam teori graph yang menemukan suatu pohon rentang minimum untuk terhubung dalam graf berbobot . Ini berarti menemukan subset dari tepi yang membentuk sebuah pohon yang mencakup setiap titik , di mana berat total dari semua tepi di atas pohon diminimalkan.

Output Algoritma Prim dan Kruskal