Menemukan Pohon Minimum dengan Algoritma Prim

Strategi greedy yang digunakan:

1.       Pada setiap langkah, pilih sisi e dari graf G(V, E) yang mempunyai bobot terkecil dan bersisian dengan simpul-simpul di T  tetapi e tidak membentuk sirkuit di T.

2.       Komplesiats algoritma: O(n²)

3.       Pada algoritma prim, dimulai pada vertex yang mempunyai sisi (edge) dengan bobot terkecil.

4.       Sisi yang dimasukkan ke dalam himpunan T adalah sisi graph G yang bersisian dengan sebuah simpul di T, sedemikian sehingga T adalah Tree (pohon). Sisi dari Graph G ditambahkan ke T jika ia tidak membentuk cycle.

 (NOTE: dua atau lebih edge kemungkinan mempunyai bobot yang sama, sehingga terdapat pilihan vertice,  dalam hal ini dapat diambil salah satunya.)

Contoh Algoritma Prim

1.       Ambil sisi (edge) dari graph yg berbobot minimum, masukkan ke dalam T

2.       Pilih sisi (edge) (i,j) yg berbobot minimum dan bersisisan dengan simpul di T, tetapi (i,j) tidak membentuk cycle di T. tambahkan (i,j) ke dalam T

3.       Ulangi prosedur no 2 sebanyak (n-2) kali

PROCEDURE Prim

(G: weighted connected undirected graph with n vertices)

                BEGIN

                                T := a minimum-weight edge

                                FOR   i := 1 to n-2 DO

                                                BEGIN

                                                                e := a minimum-weight edge one

                                                                       of whose vertices is in T,

                                                                       and one  is not in T

                                                                T := T with e added

                                                END

                                RETURN T

                END

Contoh Soal : Mencari Lintasan Minimum

Jawaban Sesuai Algoritma :

Read More