Struktur Data graf (Part 2)

Handout No: 23

[Handout berikutnya, sebelumnya, atau kembali ke halaman utama]

Struktur Data graf: representasi & algoritma-algoritma

26 April 1999

Goal: Masalah MST, Algoritma Prim's, Algoritma Kruskal, Masalah Pengurutan Topologis, Masalah Graf Lain

Masalah Pencarian Pohon Rentangan Minimum

Dalam aplikasinya problem ini misalnya

hendak direntangkan jaringan kabel listrik yang menghubungkan sejumlah lokasi dengan panjang kabel yang digunakan sependek-pendeknya mungkin,
melihat pengelompokan data yang tersebar pada suatu ruang,
perencanaan jaringan transportasi/distribusi barang. Terdapat sejumlah algoritma, namun akan dibahas hanya dua algoritma yang paling terkenal: algoritma Prim dan Algoritma Kruskal.

Contoh Suatu Graph dengan MST dari Graph ybs

dalam contoh di atas sisi {E,D} bisa digantikan oleh sisi {I,J} yang membentuk MST lain dengan total panjang rentangan yang sama.

Algoritma Prim

Pada setiap iterasi terdapat kondisi di mana himpunan verteks V terbagi dua dalam:

W yaitu himpunan verteks yang sudah dievaluasi sebagai node di dalam pohon, serta
(V-W) yaitu himpunan verteks yang belum dievaluasi.
Di awal algoritma W diinisialisasi berisi verteks awal v.
Selanjutnya, di dalam iterasinya:

Pada setiap adjacency dari tiap verteks dalam W dengan verteks dalam (V-W) dicari sisi dengan panjang minimal.
setelah diperoleh, sisi tersebut ditandai sebagai sisi yang membentuk tree dan verteks adjacent sisi tersebut dalam (V-W) dipindahkan ke W (menjadi anggota W).
Jika sisi tersebut tidak ada maka proses selesai.

Dari contoh di atas misalnya dilakukan pencarian mulai dari verteks A (ingat tidak harus selalu dari verteks A!). Maka algoritma ini menghasilkan tahapan-tahapan iterasi pencarian sbb.:

No iterasi W V-W Sisi-sisi yang dievaluasi verteks berikutnya

1 {A} {B, C, D, E, F, G, H, I, J, K, L, M} {A,B}=24, {A,C}=43, {A.D}=33, {A,F}=31 B karena {A,B} adalah minimum

2 {A, B} {C, D, E, F, G, H, I, J, K, L, M} {A,C}=43, {A.D}=33, {A,F}=31, {B,C}=18, {B,H}=45 C karena {B,C} adalah minimum

3 {A, B, C} {D, E, F, G, H, I, J, K, L, M} {A.D}=33, {A,F}=31, {B,H}=45, {C,E}=16, {C,G}=22, {C,H}=35, {C,I}=15 I karena {C,I} adalah minimum

4 {A, B, C, I} {D, E, F, G, H, J, K, L, M} {A.D}=33, {A,F}=31, {B,H}=45, {C,E}=16, {C,G}=22, {C,H}=35, {G, I}=21, {H,I}=25, {I,J}=19, {I,M}=35 E karena {C,E} adalah minimum

5 {A, B, C, E, F, I} {D, G, H, J, K, L, M} {A.D}=33, {B,H}=45, {C,G}=22, {C,H}=35, {E.D}=19, {G, I}=21, {H,I}=25, {I,J}=19, {I,M}=35 F karena {E,F} adalah minimum

6 {A, B, C, E, F, I} {D, G, H, J, K, L, M} {A.D}=33, {B,H}=45, {C,G}=22, {C,H}=35, {E.D}=19, {F,D}=22, {G, I}=21, {H,I}=25, {I,J}=19, {I,M}=35 D karena {D,E} adalah minimum

7 {A, B, C, D, E, F, I} {G, H, J, K, L, M} {B,H}=45, {C,G}=22, {C,H}=35, {D,G}=39, {D,K}=13, {D,L}=27, {G, I}=21, {H,I}=25, {I,J}=19, {I,M}=35 K karena {D,K} adalah minimum

8 {A, B, C, D, E, F, I, K} {G, H, J, L, M} {B,H}=45, {C,G}=22, {C,H}=35, {D,G}=39, {D,L}=27, {K,G}=13, {K,J}=10 ,{K,L}=19, {G, I}=21, {H,I}=25, {I,J}=19, {I,M}=35 J karena {K,J} adalah minimum

9 {A, B, C, D, E, F, I, J, K} {G, H, L, M} {B,H}=45, {C,G}=22, {C,H}=35, {D,G}=39, {D,L}=27, {G,K}=13, {G, I}=21, {H,I}=25, {I,M}=35, {J,M}=15, {K,L}=19 G karena {K,G} adalah minimum

10 {A, B, C, D, E, F, G, I, J, K} {H, L, M} {B,H}=45, {C,H}=35, {D,L}=27, {H,I}=25, {I,M}=35, {J,M}=15, {K,L}=19 M karena {J,M} adalah minimum

11 {A, B, C, D, E, F, G, I, J, K, M} {H, L} {B,H}=45, {C,H}=35, {D,L}=27, {H,I}=25, {K,L}=19, {L,M}=25 L karena {K,L} adalah minimum

12 {A, B, C, D, E, F, G, I, J, K, L, M} {H} {B,H}=45, {C,H}=35, {H,I}=25 I karena {H,I} adalah minimum

13 {A, ..., M} {} selesai

Aplikasi untuk graph lebih umum

jika proses tidak menemukan sisi tersebut maka satu connected component telah lengkap diproses, dan
jika masih ada verteks yang tersisa dalam (V-W), yang berarti juga masih ada connected component lain, maka verteks sebarang di (V-W) dimasukkan dalam W sebagai verteks awal dilanjutkan dengan iterasi tersebut.
Proses baru berhenti setelah tidak ada lagi verteks tersisa dalam (V-W).

Aspek implementasi

Cara lain yang lebih efisien adalah dengan menggunakan dua struktur linked list: linked list untuk W dan untuk (V-W), sehingga dapat mengurangi jumlah iterasi yang perlu dilakukan dalam memeriksa adjacency.

Algoritma Kruskal

mendapatkan satu demi satu sisi mulai dari yang berbobot terkecil untuk membentuk tree; suatu sisi walaupun berbobot kecil tidak akan diambil jika membentuk siklik dengan sisi yang sudah termasuk dalam tree.

Salah satu pemecahaannya adalah dengan subsetting yaitu pembentukan subset-subset yang disjoint dan secara bertahap dilakukan penggabungan atas tiap dua subset yang berhubungan dengan suatu sisi dengan bobot terpendek. Algoritma lengkapnya:

Tahap pertama, jika dalam V terdapat n verteks maka diinisialisasi n buah subset yang disjoint, masing-masing berisi satu verteks, sebagai subset-subset awal.
Tahap berikutnya, urutkan sisi-sisi dengan bobot yang terkecil hingga terbesar.
Mulai dari sisi dengan bobot terkecil hingga terbesar lakukan dalam iterasi:

jika sisi tsb. menghubungkan dua verteks dalam satu subset (berarti membentuk siklik) maka skip sisi tersebut dan periksa sisi berikutnya
jika tidak (berarti membentuk siklik) maka kedua subset dari verteks-verteks yang bersangkutan digabungkan menjadi satu subset yang lebih besar.
Iterasi akan berlangsung hingga semua sisi terproses.

Dari contoh di atas maka berturut-turut diperiksa sisi-sisi sbb.:

{J,K}=10, OK karena tidak membentuk siklik
{D,K}=13, OK karena tidak membentuk siklik
{G,K}=13, OK karena tidak membentuk siklik
{C,I}=15, OK karena tidak membentuk siklik
{E,F}=15, OK karena tidak membentuk siklik
{J,M}=15, OK karena tidak membentuk siklik
{C,E}=16, OK karena tidak membentuk siklik
{B,C}=18, OK karena tidak membentuk siklik
{D,E}=19, OK karena tidak membentuk siklik
{I,J}=19, membentuk siklik
{L,K}=19, OK karena tidak membentuk siklik
{G,I}=21, membentuk siklik
{C,G}=22, membentuk siklik
{D,F}=22, membentuk siklik
{A,B}=24, OK karena tidak membentuk siklik
{H,I}=25, OK karena tidak membentuk siklik
selesai karena semua verteks telah tergabung dalam MST

Aplikasi untuk graph lebih umum

Aspek implementasi

Cara lain yang lebih efisien adalah dengan linked-list; setiap subset adalah satu linked list.

Mengingat bahwa representasi matriks untuk graph berbobot menggunakan harga bilangan INFINITY maka proses akan berakhir jika bobot sisi yang diperiksa berbobot INFINITY atau memang sudah tidak ada lagi sisi yang lain.

Masalah Pengurutan Topologis

Verteks-verteks dengan indegree = 0 dimasukkan dalam list L.
Dalam iterasi: dapatkan verteks-verteks dengan indegree = 0 dalam subgraph tanpa mengikutkan verteks-verteks dalam L, kemudian verteks-verteks ini ditambahkan dalam L setelah verteks-verteks yang telah masuk sebelumnya.
Iterasi dilakukan hingga semua verteks masuk dalam L.

Implementasi

Contoh

Pada tahap inisialisasi indegree dari masing-masing vertex adalah:

A	B	C	D	E	F	G	H	I	J	K	L	M
0	1	2	1	2	3	2	2	2	1	4	1	3

Pada iterasi pertama A adalah satu-satunya yang memiliki indegree berharga 0. Setelah A "dimasukkan ke dalam L" maka inorder dari verteks-verteks adjacent dari A diupdate, menghasilkan.

A	B	C	D	E	F	G	H	I	J	K	L	M
0	0	1	0	2	2	2	2	2	1	4	1	3

Iterasi	A	B	C	D	E	F	G	H	I	J	K	L	M	"Masuk L"
1	0	0	0	0	2	2	2	1	2	1	4	1	3	C
2	0	0	0	0	1	2	1	0	1	1	4	1	3	D
3	0	0	0	0	0	1	0	0	1	1	3	0	3	E	(dan seterusnya....)

Masalah-masalah NP-Complete

Travelling Salesperson Problem

Solusi masalah ini adalah kombinatorik, berarti eksponensial (non polinomial), tepatnya masalah NP-complete. Untuk mencapai waktu polimnomial maka sejumlah algoritma tersedia namun hanya menghasilkan solusi aproksimasi (hasil yang diperoleh tidak minimal).

Masalah-masalah nonpolinomial lain

Masalah-masalah graph tersebut misalnya: k-colorability problem, pencarian k-clique, pencarian vertex-cover, pencarian hamiltonian circuit.

Handout berikutnya, sebelumnya, atau kembali ke halaman utama

No iterasi	W	V-W	Sisi-sisi yang dievaluasi	verteks berikutnya
1	{A}	{B, C, D, E, F, G, H, I, J, K, L, M}	{A,B}=24, {A,C}=43, {A.D}=33, {A,F}=31	B karena {A,B} adalah minimum
2	{A, B}	{C, D, E, F, G, H, I, J, K, L, M}	{A,C}=43, {A.D}=33, {A,F}=31, {B,C}=18, {B,H}=45	C karena {B,C} adalah minimum
3	{A, B, C}	{D, E, F, G, H, I, J, K, L, M}	{A.D}=33, {A,F}=31, {B,H}=45, {C,E}=16, {C,G}=22, {C,H}=35, {C,I}=15	I karena {C,I} adalah minimum
4	{A, B, C, I}	{D, E, F, G, H, J, K, L, M}	{A.D}=33, {A,F}=31, {B,H}=45, {C,E}=16, {C,G}=22, {C,H}=35, {G, I}=21, {H,I}=25, {I,J}=19, {I,M}=35	E karena {C,E} adalah minimum
5	{A, B, C, E, F, I}	{D, G, H, J, K, L, M}	{A.D}=33, {B,H}=45, {C,G}=22, {C,H}=35, {E.D}=19, {G, I}=21, {H,I}=25, {I,J}=19, {I,M}=35	F karena {E,F} adalah minimum
6	{A, B, C, E, F, I}	{D, G, H, J, K, L, M}	{A.D}=33, {B,H}=45, {C,G}=22, {C,H}=35, {E.D}=19, {F,D}=22, {G, I}=21, {H,I}=25, {I,J}=19, {I,M}=35	D karena {D,E} adalah minimum
7	{A, B, C, D, E, F, I}	{G, H, J, K, L, M}	{B,H}=45, {C,G}=22, {C,H}=35, {D,G}=39, {D,K}=13, {D,L}=27, {G, I}=21, {H,I}=25, {I,J}=19, {I,M}=35	K karena {D,K} adalah minimum
8	{A, B, C, D, E, F, I, K}	{G, H, J, L, M}	{B,H}=45, {C,G}=22, {C,H}=35, {D,G}=39, {D,L}=27, {K,G}=13, {K,J}=10 ,{K,L}=19, {G, I}=21, {H,I}=25, {I,J}=19, {I,M}=35	J karena {K,J} adalah minimum
9	{A, B, C, D, E, F, I, J, K}	{G, H, L, M}	{B,H}=45, {C,G}=22, {C,H}=35, {D,G}=39, {D,L}=27, {G,K}=13, {G, I}=21, {H,I}=25, {I,M}=35, {J,M}=15, {K,L}=19	G karena {K,G} adalah minimum
10	{A, B, C, D, E, F, G, I, J, K}	{H, L, M}	{B,H}=45, {C,H}=35, {D,L}=27, {H,I}=25, {I,M}=35, {J,M}=15, {K,L}=19	M karena {J,M} adalah minimum
11	{A, B, C, D, E, F, G, I, J, K, M}	{H, L}	{B,H}=45, {C,H}=35, {D,L}=27, {H,I}=25, {K,L}=19, {L,M}=25	L karena {K,L} adalah minimum
12	{A, B, C, D, E, F, G, I, J, K, L, M}	{H}	{B,H}=45, {C,H}=35, {H,I}=25	I karena {H,I} adalah minimum
13	{A, ..., M}	{}	selesai