Algoritma PrimMinimum Spanning Tree

Tentang Algoritma Prim Dikembangkan dari Algoritma Dijkstra untuk mencari jarak terpendek. Mencari MST dengan menambahkan edge dengan bobot terkecil ke sebuah set sedemikian rupa sehingga penambahan tersebut tetap membentuk tree.

Tentang Algoritma Prim (2) Termasuk algoritma greedy karena mencoba semua kemungkinan yang ada untuk menambahkan edge pada set yang dicari. Membutuhkan input untuk menentukan root tree.

Istilah-Istilah Undirected-weighted graph : graf berbobot tak berarah

Istilah-Istilah Cut set : graf kecil bagian dari graf utama

Istilah-Istilah Cross edge : edge yang menghubungkan cut set dan graf utama

Istilah-Istilah Light edge : edge dengan bobot paling kecil

Istilah-Istilah Cross-light edge : light edge yang menghubungkan cut set dan graf utama

MST - Algoritma Prim

Contoh Problem MSTTentukan minimum spanning tree dari graf berikut dengan menggunakan algoritma Prim dengan vertex a sebagai root tree!

Penyelesaian dengan Algoritma Prim

Penyelesaian dengan Algoritma Prim

Penyelesaian dengan Algoritma Prim

Penyelesaian dengan Algoritma Prim

Penyelesaian dengan Algoritma Prim

Penyelesaian dengan Algoritma Prim

Penyelesaian dengan Algoritma Prim

Penyelesaian dengan Algoritma Prim

Hasil Penyelesaian dengan Algoritma Prim

Daftar PustakaCormen, Thomas H, dkk. 2009.Introduction to Algorithms Third Edition.

London: The MIT Press