Telah kita ketahui bersama bahwa penerapan graph maupun juga tree dalam bidang komputer sangat banyak. Bagian ini membahas bagaimana metode untuk melakukan penelusuran unsureunsur (vertek-vertek) dari graph atau tree tersebut. Juga bagaimana membuat jalur dari satu vertek ke vertek lain yang paling optimun. Beberapa algoritma yang akan dibahasa adalah BFS, DFS, Algoritma Dijstra, Algoritma Kruskal, juga algoritma Prim.
9.1 Representasi Aritmetika Dengan Tree Operasi aritmetika dapat direpresentasikan dengan menggunakan binary tree. Internal vertek untuk menyatakan operator, sedangkan leaf sebagai operand. Root pada setiap subtree akan sebagai operator. Oleh karena itu operator yang paling luar (paling akhir dilakukan) sebagai root. Sebagai ilustrasi perhatikan beberapa contoh berikut : a.
a + b dapat dinyatakan sebagai :
+ a
b.
b
(a+b)*(d/c) dapat dinyatakan sebagai : *
+
a c.
/
b
( a b) c d (b * c) d
d
c
/
+
^ a
d c
b
+
* b
Topik9 Penelusuran dan Optimisasi Pada Graph 9-1
d c
Di dalam operasi matematika yang biasa kita pelajari adalah operasiu infik, yaitu operator diletakkan di antara operand, seperti a+b, a-B, a*b, dan sebagainya. Sebenarnya ada tiga jenis operasi, yaitu : infiks, prefiks, dan postfiks. Untuk membandingkan ketiganya, perhatikan contoh berikut : infiks
prefiks
postfiks
a+b
+ab
ab+
(a+b)-c
-+abc
ab+c-
[a*(c-b)]/d
/*a-cbd
acb-*d/
9.2 Penelusuran Vertek Bagi komputer operasi prefiks maupun postfiks lebih mudah disbanding infiks. Hal ini berlaku sebaliknya untuk manusia. Pada bagian ini akan diuraikan bagaimana menelusuri tree sehingga terjadi pembacaan infiks, prefiks, maupun postfiks. a.
b.
c.
Penelusuran Infiks (Inorder Traversal). 1.
Lakukan inorder traversal pada subtree kiri
2.
Baca root
3.
Lakukan inorder traversal pada subtree kanan
Penelusuran Prefiks (Preorder Traversal) 1.
Baca root
2.
Lakukan inorder traversal pada subtree kiri
3.
Lakukan inorder traversal pada subtree kanan
Penelusuran Postfiks (Postorder Traversal) 1.
Lakukan inorder traversal pada subtree kiri
2.
Lakukan inorder traversal pada subtree kanan
3.
Baca root
Sebagai ilustrasi perhatikan tree berikut : / + ^ a
Inorder
: a-b^c+d/b*c+d
Preorder
: /+^-abcd+*bcd
Postorder
: ab-c^d+bc*d+/
+ d
*
c
b
b
Topik9 Penelusuran dan Optimisasi Pada Graph 9-2
d c
9.3 DFS dan BFS DFS (Depth-First Search Algorithm) merupakan algoritma untuk menelusuri vertek-vertek suatu graph, sehingga akan terbentuk suatu spanning tree dari graph tersebut. Algoritma DFS ini adalah : 1.
Pilih satu vertek (r) sebagai root, dan masukkan vertek r ke dalam T. Beri v sebagai r.
2.
Pilih nilai i terkecil, 2in, sedemikian sehingga {v,vi}V dan vi belum pernah dikunjungi. Jika tidak ada i, maka langsung ke langkah 3. Untuk hal lainnya, lakukan : a.
ambil edge {v,vi}ke dalam T,
b.
beri v sebagai vi,
c.
kembali ke langkah 2.
3.
Jika v=r, maka T adalah spanning tree dari graph G, dan selesai.
4.
Untuk vr, lakukan backtrack dari v. Jika u adalah parent dari vertek v, maka beri nilai v sebagai u, dan kembali ke langkah 2.
Sebagai ilustrasi dari algoritma di atas, maka akan diterapkan untuk graph berikut : g j
c
a
b
i
f e
d h Misalkan vertek-vertek diurut sesuai dengan : a, b, c, d, …..,h, i, j, maka hasilnya adalah : 1. Pertama ambil vertek a sebagai root, dan T={a}, serta v=a. 2. Vertek yang adjacent dengan a adalah : b, c, d. Ambil b, masukkan edge {a,b} ke dalam T. v=b, dan looping Vertek yang adjacent dengan b adalah a, d dan e. (a tidak diambil, sebab sudah dikunjungi) Ambil d, masukkan edge {b,d} ke dalam T. v=d, dan looping Vertek yang adjacent dengan d adalah a dan b (keduanya telah dikunjungi, maka ke langkah 3. 3. v=da, maka ke langkah 4 4. backtrack dari d dan v=b, dan kembali ke langkah 2. 2. Vertek yang adjacent dengan b adalah a, d, dan e. (a dan d sudah dikunjungi) Ambil e, v=e dan masukkan edge {b,e} ke dalam T, lalu looping. Vertek yang adjacent dengan e adalah b, f, h. Ambil f, v=f dan masukkan edge {e,f} ke dalam T, looping Vertek yang adjacent dengan f adalah e (sudah dikunjungi), maka ke langkah 3. 3. v=fa, maka ke langkah 4 4. backtrack dari f dan v=e, dan kembali ke langkah 2. 2. Vertek yang adjacent dengan e adalah b, f, dan h. Ambil h, v=h dan masukkan edge {e,h} ke dalam T, lalu looping Vertek yang adjacent dengan h adalah e (sudah dikunjungi), maka ke langkah 3.
Topik9 Penelusuran dan Optimisasi Pada Graph 9-3
3. v=ha, maka ke langkah 4 4. backtrack dari h dan v=e, dan kembali ke langkah 2. 2. Vertek yang adjacent dengan vertek e adalah b, f, h (sudah dikunjungi semua), maka ke langkah 3. 3. v=ha, maka ke langkah 4 4. backtrack dari h dan v=e, dan kembali ke langkah 2. 2. Vertek yang adjacent dengan vertek e adalah b, h, dan f (semua suadh dikunjungi), maka ke langkah 3. 3. v=ea, maka ke langkah 4 4. backtrack dari e dan v=b, dan kembali ke langkah 2. 2. Vertek yang adjacent dengan vertek b adalah a, d, dan e (semua suadh dikunjungi), maka ke langkah 3. 3. v=ba, maka ke langkah 4 4. backtrack dari b dan v=a, dan kembali ke langkah 2. 2. Vertek yang adjacent dengan vertek a adalah b, c dan d. Ambil c, dan v=c, ambil edge {a,e} ke dalam T, lalu looping. Vertek yang adjacent dengan c adalah a dan g. Ambil g, v=g dan ambil edge {e,g} ke dalam T, lalu looping Vertek yang adjacent dengan g adalah c, i dan j. Ambil i, v=i dan ambil edge {g,i} ke dalam T, lalu looping. Vertek yang adjacent dengan i adalah g (sudah dikunjungi), maka ke langkah 3. 3. v=ia, maka ke langkah 4 4. backtrack dari i dan v=g, dan kembali ke langkah 2. 2. Vertek yang adjacent dengan vertek g adalah c, i, j. Ambil j, v=j dan ambil edge {g,j} ke dalam T, lalu looping. Vertek yang adjacent dengan vertek j adalah g (sudah dikunjungi), maka ke langkah 3. 3. v=ja, maka ke langkah 4 4. backtrack dari j dan v=g, dan kembali ke langkah 2. 2. Vertek yang adjacent dengan vertek g adalah c, i, j (sudah dikunjungi), maka ke langkah 3. 3. v=ca, maka ke langkah 4 4. backtrack dari c dan v=c, dan kembali ke langkah 2. 2. Vertek yang adjacent dengan vertek c adalah a dan g (sudah dikunjungi), maka ke langkah 3. 3. v=ca, maka ke langkah 4 4. backtrack dari c dan v=a, dan kembali ke langkah 2. 2. Vertek yang adjacent dengan vertek a adalah b, c, dan d (sudah dikunjungi), maka ke langkah 3. 3. v=a, maka selesai.
Topik9 Penelusuran dan Optimisasi Pada Graph 9-4
Hasilnya adalah :
a
g c
j
b
f
i
e d h
BFS (Breadth-First Search Algorithm) merupakan algoritma untuk menelusuri vertek-vertek suatu graph, sehingga akan terbentuk suatu spanning tree dari graph tersebut. Perbedaan dengan DFS adalah bahwa pada BFS, pembacaan dilakukan pada seluruh level.yang sama. Oleh karena itu tree yang akan terbentuk cenderung melebar. Algoritma DFS ini adalah : 1.
Pilih satu vertek (r) sebagai root, dan masukkan vertek r ke dalam antraian Q. Serta insialisasi tree T dengan T={r}.
2.
Hapuskan vertek terdepan dari Q. Untuk setiap i terkecil, 2in, sedemikian sehingga {v,vi}E dan vi belum pernah dikunjungi, masukkan edge {v,vi}ke dalam T.
3.
Masukkan vertek yang adjacent dengan vertek v yang dihapus pada langkah (2) tersebut ke dalam Q dengan urutan yang disesuaikan, dan kembali ke langkah 2.
Sebagai ilustrasi dari algoritma di atas, maka akan diterapkan untuk graph berikut : a
g c
j
b
f
i
e d h
Misalkan vertek-vertek diurut sesuai dengan : a, b, c, d, …..,h, i, j, maka hasilnya adalah :
a
g j
b
c i
f e
d h
Topik9 Penelusuran dan Optimisasi Pada Graph 9-5
Latihan 9.1. 1. Untuk graph berikut lakukan : a
c
b d
e
g
f
h
ja
i k
l
o
p q
r s u
t
v
w
a.
Penelusuran secara inorder
b.
Penelusuran secara preorder
c.
Penelusuran secara postorder
2. Perhatikan operasi aritmetika berikut :
ab k (b.c ) r l a.
Buatlah binary tree untuk operasi aritmetika tersebut !
b.
Tentukan notasi infiksnya
c.
Tentukan notasi prefiksnya
d.
Tentukan notasi postfiksnya
3. Suatu complete binary T=(V,E) dengan V={a, b, c, …, i, j, k} dan a sebagai root. Jika hasil penelusuran postorder adalah : d, e, b, h, i, f, j, k, g, c, a. Gambarkan tree ini. a.
Jika tinggi tree ini adalah 3.
b.
Jika tinggi subtree kiri dari tree ini adalah 3.
Topik9 Penelusuran dan Optimisasi Pada Graph 9-6
4.
Perhatikan graph berikut : b a
c
d
g
f
e
h
k i
j
Jika vertek diurut dari a, b, …, j, k, tentukan spanning tree dari graph tersebut dengan menggunakan :
5.
a.
Depth-first search algorithm (DFS)
b.
Bread-first search algorithm (BFS) a
Soal seperti nomor (4) untuk graph :
b
c d f
e
g h
i k
j 6.
Soal seperti nomor (4) untuk graph :
a
b
f e
g d
c
9.3 Optimisasi Optimisasi berkaitan dengan beberapa operasi yang diterapkan pada graph yang terboboti, yaitu graph dengan setiap edge mempunyai bobot yang tidak harus sama. Ada beberapa optimisasi di dalam graph terboboti, yaitu : 1.
Algoritma Dijkstra : untuk mencari path terpendek dari satu vertek ke vertek lainnya di dalam graph tersebut.
2.
Algoritma Kruskal : Algoritma ini untuk mencari spanning tree dari suatu graph dengan panjang path antar vertek minimum. Hasil dari algoritma ini adalah minimum spanning tree.
3.
Algoritma Prim : algortima ini bertujuan sama dengan algoritma Kruskal.
Topik9 Penelusuran dan Optimisasi Pada Graph 9-7
4.
Algoritma Max-Flow Min-Cut : untuk mencari aliran terbesar dari satu vertek ke satu vertek lainnya.
Di dalam bagian ini hanya akan dibahas algoritma Dijkstra saja. Algoritma Dijkstra Algoritma Dikstra (Dikstra’s shortest path algorithm) merupakan algoritma untuk mencari lintasan (path) terpendek dari suatu vertek ke vertek-vertek lainnya dalam suatu graph G=(V,E). Di dalam hal ini edgeedge dalam graph G tersebut mempunyai bobot yang berbeda (disebut weighted graph). Algoritma Dikstra ini adalah sebagai berikut : 1.
Inisialisasi : i=0, S0={v0}. Beri label vertek v0 dengan (0,-) dan setiap vertek vv0 diberi label (,-). Jika n=1, V={v0} dan selesai. Jika n>1, lanjutkan ke langkah 2.
2. Untuk setiap v S i , gantikan (jika mungkin) label pada v dengan (L(v), y), dengan : L(v) = min {L(v), L(u)+wt(u,v)} uSi
y adalah vertek di dalam Si dengan L(v) minimum. 3. Jika setiap vertek di
Si (0in-2) berlabel (,-) maka selesai. Jika tidak, maka lakukan :
a.
Pilih vertek vi+1 dengan label L( vi+1) minimum, lalu :
b.
Si+1=Si{ vi+1}
c.
i=i+1, jika i=n-1, maka selesai. Jika tidak, maka kembali ke langkah 2.
Sebagai ilustrasi algortima di atas, maka perhatikan contoh dengan graph berikut :
7
11
c
f
6
9
11 6
11
4
4
b a
4 7
3
g
9
h
5
5 11 17
Topik9 Penelusuran dan Optimisasi Pada Graph 9-8
Hasil dari graph tersebut adalah :
7
11 (0,-) c
f (6,c)
6
9
11 (22,a) 6
11
4
4
g (14,h)
9
b
4 7
3 a (17,f)
h (10,f)
5
5
11 17 Latihan 9.2. 1. Perhatikan graph berikut :
a
10
5
4 c 20
e
4
g
10
h
15 6
10
d
5
f
b
3
8 30
i
5 6
2 k
j 20 a. Lakukan operasi dengan algoritma Dijkstra untuk memperoleh jarak terpendek dari vertek a ke setiap vertek lainnya. 2.
Soal sama seperti nomor (1) untuk graph berikut :
a
Diketahui bobot edge : {a,c}=10 {a,d}=20 b
{a,e}=15 {a,g}=5 {b,c}=3
{b,d}=2
{b,f}=1
{c,d}=1
{c,g}=1
{d,e}=2
{e,f}=3
{f,g}=2
f e
g d
c
Topik9 Penelusuran dan Optimisasi Pada Graph 9-9
