Minimum Spanning Tree – Algoritma Prim

DEFINISI

Pohon rentangan adalah total weight (bobot) semua edge dalam pohon dan tidak jarang pohon rentangan bisa berjumlah lebih dari satu. Istilah Minimum spanning tree merujuk kepada pohon rentangan yang memiliki kompleksitas terendah di antara semua pohon rentangan. Sama halnya dengan pohon rentangan pada umumnya, (pohon rentangan minimum) juga bisa berjumlah lebih dari satu.

ALGORITMA PRIM

Algoritme Prim juga menggunakan pendekatan greedy untuk menemukan minimum spanning tree. Dalam algoritme Prim, kita mengembangkan spanning tree dari posisi asal. Bagian yang berbeda dari algoritme Kruskal adalah ditambahkannya edge ke growing spanning tree; sedangkan pada algoritme Prim, verteks yang ditambahkan ke growing spanning tree.

LANGKAH ALGORITMA

Terdapat dua disjoint set verteks. Salah satu disjoint set berisi verteks dalam growing spanning tree, dan yang lainnya berisi verteks yang tidak dalam growing spanning tree.
Pilih verteks paling ringan yang terhubung dengan growing spanning tree dan yang tidak dalam growing spanning tree lalu tambahkan ke growing spanning tree. Hal ini dapat dilakukan menggunakan Priority Queue. Sisipkan verteks yang ada dalam growing spanning tree ke dalam Priority Queue.
Pastikan tidak ada siklus yang terjadi. Untuk melakukan hal tersebut, tandai node yang sudah dipilih dan hanya sisipkan node yang tidak bertanda ke dalam Priority Queue.

TAHAP 1

Simpul r sebagai simpul start.