ALGORITMA DAN STRUKTUR DATA : BAB 14

14.1 Graph

Graph adalah suatu struktur data yang berbentuk network / jaringan dimana hubungan antara
elemen-elemennya adalah many-to-many . contoh dalam kehidupan sehari-hari yang berbentuk
graph ini cukup banyak , misalnya: hubungan dosen dengan mahasiswa, dimana satu dosen bisa
mengajar lebih dari satu mahasiswa, dan satu mahasiswa dapat memiliki lebih dari satu dosen.
Graph terdiri dari Node ( VERTEX) dan ARC ( EDGE ). Yang dimaksud degan Node adalah
elemen graph yang berisi informasi sedangkan ARC (Edge ) dalah Path yang menghubungkan
dua buah node. Dua buah node yang dihubungkan dengan edge juga disebut Adjacent Node.

Gambar

Teminologi

Suatu subset / bagian dari Graph dinamakan SubGraph. Sedangkan yang disebut dengan Path
adalah hubungan dari kumpulan node-node dimana tiap node dengan node berikutnya
dihubungkan dengan Edge. Sebuah path dikatakan simple path bila setiap node hanya “muncul”
satu kali dalam path tersebut.

Graph dibedakan atas dua tipe , yaitu :

• Undirected GRAPH
Jika sepasang node yang membentuk edge dalam graph tidak berarah seperti ditunjukkan
oleh gambar di bawah ini :

Gambar
Gambar 14.2: Undirected Graph

Gambar

Bila ada minimal sepasang node mempunyai hubungan maka graph tersebut UnConnected Graph
seperti gambar di bawah ini :

Gambar

Jika node pertama dan node terakhir dalam graph adalah sama,maka graph tersebut dinamakan
Cycle Graph. Apabila semua edge dalam graph diberi nilai ( value ) , maka graph tersebut
dinamakan Weight Graph.

1. Representasi Graph
Graph dapat direpresentasi Graph dengan dua cara yaitu : Adjancency List dan Adjacency Matrix.
Dengan mempergunakan gambar di bawah ini sebagai contoh maka representasi graph dengan
masing-masing cara dapat dijelaskan sebagai berikut :

Gambar

a) Adjacency List

Gambar

14.2 Graph Traversal
Sama seperti Tree , maka dalam graph juga dikenal operasi Graph Traversal, yaitu penelusuran
semua node di dalam graph. Ada 2 cara untuk melakukan Traversal dalam Graph yaitu ;
Breadth First Search dan Depth First Search.

prosedur pencarian Breadth-First Search menggunakan ADT Queue dalam pemrosesan
node, sebaliknya untuk Depth First Search kita mengunakan ADT Stack.
Selama pemrosesan dari algoritma, setiap node didalam graph akan berada pada 3 keadaan
dibawah ini, yang disebut status dari n, 3 keadaan tersebut sebagai berikut:
STATUS = 1: (Ready status) keadaan awal dari setiap node.

STATUS = 2: (Waiting status) node N sudah berada pada queue atau stack, menunggu untuk
pemrosesan selanjutnya.

STATUS = 3: (Processed status) node N sudah diproses.

• Breadth-First Search
Inti dari Breadth First Search(BFS) sendiri adalah pencarian yang dimulai dari root A. Pertama
kita periksa root-nya A, setelah itu node – node yang bertetanggaan dengan A. Setelah
selesai baru kita periksa semua node tetangga A yang bertentanggaan lagi, dan seterusnya.
Selanjutnya kita harus mengikuti semua tetangga dari A dengan cermat, jangan sampai ada
satu node yang diproses lebih dari satu kali. Semuanya dapat dilakukan dengan bantuan
queue yang menyimpan node yang menunggu untuk diproses dan dengan menggunakan field
STATUS untuk mengetahui status dari node.
Algoritmanya:

1. inisialisasi semua node dalam keadalam ready. (STATUS = 1).
2. letakkan root in queue dan ganti statusnya menjadi tunggu (STATUS = 2).
3. ulangi langkah 4 dan 5 sampai queue kosong:
4. pindahkan depan node N di queue. Proses N dan ganti statusnya menjadi sudah
diproses (STATUS = 3).
5. tambahkan ke belakang dari queue semua tetangga dari N yang dalam status ready
saja (STATUS = 1), lalu ganti statusnya (STATUS = 2)
6. exit.
Catatan: algortima diatas akan memeriksa hanya node yang dapat di capai oleh node A saja.

Gambar

A      FRONT = 1                                       QUEUE: A
REAR = 1                                          ORIG: 0

B      FRONT = 2                                       QUEUE: A, F, C, B
REAR = 4                                          ORIG: 0, A, A, A

C      FRONT = 3                                       QUEUE: A, F, C, B, D
REAR = 5                                          ORIG: 0, A, A, A, F

D      FRONT = 4                                       QUEUE: A, F, C, B, D
REAR = 5                                          ORIG: 0, A, A, A, F

E      FRONT = 5                                       QUEUE: A, F, C, B, D, G
REAR = 6                                          ORIG: 0, A, A, A, F, B

F      FRONT = 6                                       QUEUE: A, F, C, B, D, G
REAR = 6                                          ORIG: 0, A, A, A, F, B

G      FRONT = 7                                      QUEUE: A, F, C, B, D, G, E
REAR = 7                                        ORIG: 0, A, A, A, F, B, G

H       FRONT = 8                                      QUEUE: A, F, C, B, D, G, E, J
REAR = 8                                         ORIG: 0, A, A, A, F, B, G, E

Dikarenakan J adalah tujuannya maka berhenti proses tersebut dan balik arah dari J ke A dengan
menggunakan array ORIG untuk mendapatkan path, sehingga didapatkan:
J < E < G < B < A

• Depth-First Search
ide dari DFS ini hampir sama dengan BFS, hanya saja pada DFS kita akan menggunakan
struktur data Stack. Prosesnya pun sama dengan menggunakan ketiga status yang kita
gunakan juga pada BFS.

Algortimanya:
1. inisialisasi semua node dalam keadalam ready. (STATUS = 1).
2. letakkan root in queue dan ganti statusnya menjadi tunggu (STATUS = 2).
3. ulangi langkah 4 dan 5 sampai queue kosong:
4. pindahkan depan node N di queue. Proses N dan ganti statusnya menjadi sudah
diproses (STATUS = 3).
5. tambahkan ke belakang dari queue semua tetangga dari N yang dalam status ready
saja (STATUS = 1), lalu ganti statusnya (STATUS = 2)
6. exit.
Catatan: algortima diatas akan memeriksa hanya node yang dapat di capai oleh node A saja.

Contoh DFS:
Misalkan kita akan mencari semua node yang bisa di jangkau oleh node J:

a. push J kedalam stack
STACK: J

b. pop, dan cetak elemen teratas J, kemudian push kedalam stack semua neighbor J (yang
berada pada status READY)
PRINT: J STACK: D, K

c. pop, dan cetak elemen teratas K, kemudian push kedalam stack semua neighbor K (yang
berada pada status READY)
PRINT: K STACK: D, E, G

d. pop, dan cetak elemen teratas G, kemudian push kedalam stack semua neighbor dari G (yang
berada pada status READY)
PRINT: G STACK: D, E, C

e. pop, dan cetak elemen teratas C, kemudian push kedalam stack semua neighbor dari C (yang
berada pada status READY)
PRINT :C STACK: D, E, F

f. pop, dan cetak elemen teratas F, kemudian push kedalam stack semua neighbor dari F (yang
berada pada status READY)
PRINT: F STACK: D, E

g. pop, dan cetak elemen teratas E, kemudian push kedalam stack semua neighbor dari E (yang
berada pada status READY)
PRINT: E STACK: D

h. pop, dan cetak elemen teratas D, kemudian push kedalam stack semua neighbor dari D (yang
berada pada status READY)
PRINT: D STACK:

Stack dalam keadaan kosong sekarang, selesainya proses traversal DFS dari node J. Hasilnya
yang tercetak adalah:
J,K, G, C, F, E, D

Iklan

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s