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 dengan Node adalah elemen graph yang berisi informasi sedangkan ARC (Edge ) adalah Path yang menghubungkan dua buah node. Dua buah node yang dihubungkan  dengan edge juga disebut Adjacent Node

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 :

Ø Directed Graph ( DiGraph )

Jika sepasang  node yang berbentuk edge dalam Graph mempunyai arah.

Representasi Graph

Graph dapat direpresentasi 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 :

1. Adjancency List

Direpresentasikan sebagai suatu list bisa dinyatakan  dengan LINKED-LIST atau ARRAY 

--------------------------------------------------
      NODE                  EDGE LIST
--------------------------------------------------
     a                               b    c
     b                               c    d   e

     c                               b    e   f
     d                              b    e   
     e                              b    c    d   f
     f                               c     e
---------------------------------------------------

2. Adjancency Matrix

Direpresentasikan dengan array 2 dimensi. Tipe komponen dari Array bisa digunakan BOOLEAN atau INTEGER ( untuk WEIGHTED GRAPH )

---------------------------------------------------------
|      |   a    |    b   |    c   |    d  |   e    |    f    |
---------------------------------------------------------
a      |   0    |   1    |    1   |  0    |    0    |   0   |
b      |   1    |   0    |    1   |  1    |    1    |   0   |
c      |    1   |    0   |    0    |  0    |    1   |   1   |
d      |   0    |   1    |    0    |  0    |    1   |   0   |
e      |   0    |   1    |    1    |  1    |    1   |   1   |
f       |   0    |   0    |    1    |   0   |    0   |   0   |
----------------------------------------------------------

1) 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

Adjacecy List

A:          F, C, B

B:          G, C

C:           F

D:          C

E:           D, C, J

F:           D

G:          C, E

J:           D, K

K:          E, G

2. 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.

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