Algoritma Prims - Irul

Algoritma Prim Mata Kuliah : [ CF-1333 Alpro 2 ]

Disusun oleh : Khairu Rahman

5207 100 030

Jurusan Sistem Informasi Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Surabaya

1

ALGORITMA PRIM

Algoritma Prim adalah sebuah algoritma dalam graph theory untuk mencari pohon rentang minimum untuk sebuah graf terhubung berbobot [wikipedia]. Untuk lebih jelas akan saya berikan contoh dengan gambar :

A

F

B

C

E

D

Terdapat sebuah rangkaian seperti pada gambar di atas. Setiap titik disebut dengan vertex. Terdapat 6 vertex yaitu A, B, C, D, E, dan F. Yang ingin dilakukan di sini adalah menghubungkan semua vertex yang ada dengan melalui jalur yang menghabiskan cost paling minimal. Dengan menggunakan algoritma prim kita dapat menentukan jalur tersebut.

Adapun langkah-langkah penyelesainnya adalah sebagai berikut :

Cara I 1. tentukan titik start. Dalam kasus ini saya tentukan titik startnya adalah vertex B. 2. kemudian buatlah dua buah himpunan. Misalkan himpunan T dan S. Dimana elemen dari T adalah vertex-vertex yang sudah saling terhubung dan elemen himpunan S adalah vertex-vertex yang belum terhubung. Pada akhir proses, seluruh elemen F akan berpindah menjadi elemen T dan F menjadi himpunan kosong. 3. pada awal proses elemen T hanyalah vertex yang menjadi titik start (vertex B) dan himpunan F berisi vertex-vertex sisanya.

2

4. T={B} ; F={A,C,D,E,F} B(- , -) : A(B,1) D(B,1) C(B,5) E(- ,  ) F(- , ) Tuliskan semua vertex yang memiliki kemungkinan terhubung dengan vertex

B

secara

langsung.

Penulisan

A(B,1)

artinya

titik

A

bisa

dihubungkan secara langsung dengan vertex B(titik start) dengan cost 1. Pada langkah ini vertex E dan F tidak dapat terhubung secara langsung sehingga kita menuliskannya dengan E(- ,  ) dan F(- , ). Kemudian pilihlah jalur yang menghabiskan cost paling minimal. Pada langkah ini terdapat 2 jalur yang memiliki cost paling minimum, pilih saja yang lebih dulu yaitu A(B,1). Dan selanjutnya himpunan T dan F menjadi T={B,A} ; F={ C,D,E,F} .

A

F

B

C

E

D

5. T={B,A} ; F={C,D,E,F} A(B , 1) : D(B,1) C(A,3) F(A , 3 ) E(- , )

Saat ini vertex B dan A telah terhubung. Kemudian tuliskan semua kemungkinan vertex yang bisa dihubungkan secara langsung dengan vertex – vertex yang telah saling terhubung (bisa vertex A atau B). Pada langkah ini vertex E tidak memiliki kemungkinan dihubungkan secara langsung maka dituliskan dengan menghabiskan cost paling kecil.

3

E(- , ). Kemudian pilih jalur yang

A

F

B

C

E

D

proses selanjutnya dilakukan dengan cara yang sama. Lanjutkan hingga seluruh vertex terhubung atau dengan kata lain sampai himpunan F menjadi himpunan kosong.

6. T={B,A,D} ; F={C,E,F} D(B,1): C(D,2) E(D , 4) F(A , 3 )

A

B

F

C

D

7. T={B,A,D,C} ; F={E,F} C(D,2) : E(C,1) F(A,3)

4

E

A

F

B

C

E

D

8. T={B,A,D,C} ; F={C,D,E,F} E(C,1): F(A,3)

A

B

F

C

D

E

9. Selesai. Semua vertex telah terhubung dengan cost 8 (cost optimal).

Begitulah cara kerja dari algoritma Prim. Cukup mudah dipahami bukan? Namun jika kita ingin membuat program dari algoritma prim, menurut saya sangatlah sulit membuat programnya jika kita berpatokan dengan cara I yang telah dijelaskan di atas. Untuk membuat programnya lebih baik jika kita menggunakan cara II yang akan saya jelaskan setelah ini. Cara II lebih mudah jika diimplementasikan ke dalam bentuk program.

5

Cara II

1. langkah awal pada Cara II sama dengan langkah 1 sampai 3 pada Cara I. 2. kemudian buatlah sebuah tabel(array) yang menyimpan cost – cost antar vertex dari persoalan yang diberikan (persoalan yang akan diselesaikan di sini sama dengan persoalan yang diberikan pada Cara I). Jika terdapat dua vertex yang tidak bisa terhubung secara langsung berikanlah nilai

.

Tabel ini sebagai pengganti gambar.

Tabel data Vertex

A

B

C

D

E

F

A

0

1

3





3

B

1

0

5

1





C

3

5

0

2

1



D



1

2

0

4



E





1

4

0

5

3. buatlah tabel (Array) yang menyimpan nilai cost minimal yang ditempuh dari vertex-vertex yang telah saling terhubung ke vertex yang belum terhubung. Bingung? Tidak masalah , teruskan saja membaca dan perhatikan dengan seksama. Insyaallah anda akan mengerti fungsi dari tabel ini.

A

B

D

E

F

d[]

4. kemudian saya memebuat sebuah tabel lagi (tabel set) yang berisi data bertipe boolean. Fungsi dari tabel ini adalah untuk mengenali suatu vertex, apakah vertex tersebut masuk ke dalam himpunan T atau himpunan F. Jika vertex tersebut masuk ke dalam T maka diberi nilai true

6

dan jika masuk ke dalam F diberi nilai false. Pada kondisi awal, semua isi tabel set diberi nilai false kecuali pada vertex yang menjadi titik start.

A set

B

False

D

True

E

False

F

False

False

5. selanjutnya saya akan menjelaskan proses pencarian jalur paling optimal dengan menggunakan cara II ini. Prosesnya sebagai berikut : 

step 1 : T={B} ; F={A,C,D,E,F} Maka tabel set; A set

False

B True

C

D

E

F

False

False

False

False

Dan tabel d ;

d[]

Ingat

A

B

C

D

E

F

1

0

5

1





kembali

fungsi

tabel

d

ini

yang

telah

dijelaskan

sebelumnya. Yaitu untuk menyimpan nilai cost minimal yang ditempuh dari vertex-vertex yang telah saling terhubung ke vertex yang belum terhubung. Isi d[A] berarti cost minimal antara vertex-vertex yang telah saling terhubung

ke vertex A.

Atau dengan kata lain jarak minimal antara salah satu vertex yang terdapat dalam himpunana T menuju vertex A. Karena himpunan T pada step ini hanya berisi B, maka isi dari d[A] adalah cost dari jalur yang menghubungkan langsung vertex B dan A. Nilai cost yang diperlukan tentu saja diambil dari tabel data. Jika kedua vertex tidak dapat terhubung langsung beri nilai tak hingga. Dan pada d[B] diberi nilai 0 karena tidak ada jarak.

7

Bagaimana jika himpunan T berisi lebih dari 1 vertex? Jika demikian maka pilihlah satu vertex dalam himpunan T yang dapat terhubung langsung dengan vertex-x yang terdapat dalam himpunan F. Kemudian bagaimana jika vertex yang dapat terhubung langsung lebih dari 1. Maka bandingkanlah vertexvertex yang dapat terhubung langsung tersebut, dan pilih yang costnya paling minimal. Lanjutkanlah sampai semua tabel d terisi.

Jika semua telah terisi, pilih salah satu vertex yang masih berada dalam himpunan F yang costnya paling kecil. Jika terdapat lebih dari 1 vertex yang memiliki cost sama dan paling minimal pilih vertex yang lebih dulu . Kemudian pada step selanjutnya vertex tersebut dipindahkan ke dalam himpunan T atau nilai pada tabel set yang semula bernilai False diganti dengan True.

Dan yang

perlu juga diperhatikan pada tiap step, jika suatu vertex telah masuk ke dalam himpunan T, maka nilainya pada tabel d tidak boleh diganti pada step-step selanjutnya.

Lanjutkan sampai semua vertex masuk ke dalam himpunan T. Atau

dengan kata lain semua vertex telah bernilai True pada

tabel set. atau bisa juga dikatakan proses dilanjutkan sampai step ke-n (n=banyak vertex).

Cara kerja pada step-step selanjutnya sama. Sehingga saya tidak perlu menjelaskan secara detail lagi.



step 2 : T={B, A} ; F={ C,D,E,F} Maka tabel set;

set

A

B

True

True

8

C False

D False

E False

F False

Dan tabel d ;

d[]



A

B

C

D

E

F

1

0

3

1



3

step 3 :

T={B, A,D} ; F={ C, E,F} Maka tabel set;

set

A

B

True

True

C False

D True

E

F

False

False

Dan tabel d ;

d[]



A

B

C

D

E

F

1

0

2

1

4

3

step 4 :

T={B, A, D, C} ; F={ E,F} Maka tabel set;

set

A

B

C

D

True

True

True

True

E

F

False

False

Dan tabel d ;

d[]

A

B

C

D

E

F

1

0

2

1

1

3

9



step 5 : T={B, A, D, C,E} ; F={F} Maka tabel set;

set

A

B

C

D

E

F

True

True

True

True

True

False

Dan tabel d ;

d[]



A

B

C

D

E

F

1

0

2

1

1

3

step 6 : T={B, A, D, C, E, F} ; F={ } Maka tabel set;

set

A

B

C

D

E

F

True

True

True

True

True

True

Dan tabel d ;

d[]

A

B

C

D

E

F

1

0

2

1

1

3

6. setelah menyelesaikan step ke-6 ini artinya proses telah selesai. Dari isi tabel d yang terakhir kita dapat dengan mudah menghitung cost paling minimal yang diperlukan untuk menghubungkan semua vertex yang ada. Caranya dengan menjumlahkan semua nilai yang ada pada tabel d. Kita juga dapat menampilkan jarak antar vertex yang terhubung secara langsung dan juga bisa menampilkan urutan vertex yang dihubungkan, mulai dari vertex yang dijadikan titik start sampai vertex yang paling terakhir dihubungkan.

10

Dari cara kedua ini , saya dapat membuat pseudocode untuk proses inti Algoritma Prim. Proses yang dilakukan pada pseudocode ini adalah proses pada cara II yang telah dijelaskan di atas. Yang perlu diperhatikan di sini adalah, indeks terkecil yang saya pakai adalah 1, bukan 0. sehingga jika anda ingin membuat programnya dalam bahasa java, perlu sedikit penyesuaian. Tentunya bukanlah hal yang sulit untuk melakukan hal itu jika anda telah benar-benar memahami prosesnya. Pseudocodenya adalah sebagai berikut :

PRIM(n,set,d,data) 1 for x  1 to n 2 do for i  1 to n 3 do if set[i] = False 4 then d[i] = COMPARE(i,n,set,d,data) // mencari isi d[] yg paling minimal dan memilih vertex yg dilalui selanjutnya 5 b   6 for i  to n 7 do if d[i] < b && d[i] 8 then b  d[i] 9 min = i 10 cek[min]  True

 0 && cek[i] = False

COMPARE(j,n,set,d,data) 1 2 3 4 5 6 7

b   for i  1 to n do if cek[i] = True then if data[i][j] < b then b = m[i][j] min = b return min

Bagaimana membuat

programnya??

Silakan

anda

lakukan

sendiri

=).

Tentunya anda akan merasa lebih puas jika membuat dapat programnya sendiri. Memahami proses yang dilakukan dalam Algoritma Prim ditambah lagi pseudocode yang diberikan, itu merupakan modal yang lebih dari cukup untuk dapat membuat programnya. Atau jika anda ingin lebih menantang, anda tidak perlu memperhatikan pseudocode yang saya tuliskan di atas, anda

11

cukup pahami proses Algoritma Prim dan buat pseudocodenya sendiri.. =). Jika anda dapat menyelesaikannya pasti anda akan jauh merasa lebih puas.

SELAMAT MENCOBA !!!

12