Jelaskan Algoritme dari Pohon rentang minimum

Algoritme pertama yang dipakai untuk mencari pohon rentang minimum dikembangkan oleh ilmuwan Ceko Otakar Borůvka pada tahun 1926 (lihat algoritme Borůvka). Kegunaan awalnya adalah membuat sistem kelistrikan yang efisien di daerah Moravia. Algoritme ini bekerja dalam deretan tahapan yang disebut langkah Boruvka. Kompleksitas algoritmenya adalah O(m log n).

Algoritme kedua adalah algoritme Prim. Algoritme ini ditemukan oleh Vojtěch Jarník pada tahun 1930 dan ditemukan ulang oleh Prim pada tahun 1957 dan Dijkstra pada tahun 1959. Secara sederhana, algoritme ini mengembangkan MST (T) garis demi garis. Awalnya, T terdiri dari titik bebas. Pada tiap langkah, T ditambahkan garis berbobot minimum (x, y) dengan x ada dalam T dan y belum ada dalam T. Dengan sifat pemotongan, semua garis yang ditambahkan adalah MST. Kompleksitas algoritmenya adalah math|O(m log n) atau O(m + n log n) tergantung struktur data yang dipakai.

Algoritme ketiga yang sering dipakai adalah algoritme Kruskal. Kompleksitas algoritmenya adalah O(m log n).

Algoritme keempat yang jarang dipakai adalah algoritme hapus mundur yang merupakan kebalikan dari algoritme Kruskal. Kompleksitas algoritmenya adalah O(m log n (log log n)3).

Keempat algoritme tersebut termasuk algoritme rakus (greedy).