GRAPH

Konsep Dasar 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. Adjacency List

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

2. Adjancency Matrix

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

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

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.

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 

Path Terpendek

Persoalan mencari lintasan terpendek di dalam graf merupakan persoalan salah satu optimasi. Graf yang digunakan dalam pencarian lintasan terpendek ialah graf berbobot (weighted graph), yaitu graf yang setiap sisinya diberikan suatu nilai atau bobot.

Bobot pada sisi graf dapat menyatakan jarak antar kota, waktu pengiriman pesan, ongkos pembangunan, dan sebagainya. Asumsi yang kita gunakan di sini adalah bahwa semua bobot bernilai positif. Kata “terpendek” jangan selalu diartikan secara fisik sebagai jarak minimum, sebab kata “terpendek” berbeda-beda maknanya bergantung pada tipikal persoalan yang diselesaikan. Namun, secara umum “terpendek” berarti meminimasi bobot pada suatu lintasan di dalam graf. 

Contoh terapan pencarian lintasan terpendek misalnya simpul pada graf dapat merupakan kota, sedangkan sisi menyatakan jalan yang menghubungkan dua buah kota. 

Bobot sisi graf dapat menyatakan jarak antara dua buah kota atau rata-rata waktu tempuh antara dua buah kota. Apabila terdapat lebih dari satu lintasan dari kota A ke kota B, maka persoalan lintasan terpendek disini adalah menentukan jarak terpendek atau waktu tersingkat dari kota A ke kota B. Ada beberapa macam persoalan lintasan terpendek, antara lain: 

1. Lintasan terpendek antara dua buah simpul tertentu.
2. Lintasan terpendek antara semua pasangan simpul.
3. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain.
4. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu. 

Spanning Tree (Pohon Perentang) 

Spanning Tree (Pohon Perentang) adalah pohon yang merupakan subset dari suatu graf yang tidak mengandung sirkuit, dimana semua simpul pada pohon merentang sama dengan simpul pada graf. Misalkan G = (V, E) adalah graf takberarah terhubung yang bukan pohon, yang berarti di G terdapat beberapa sirkuit.

G ini dapat diubah menjadi pohon T = (V1, E1) dengan cara memutuskan sirkuit-sirkuit yang ada. Caranya mula-mula dipilih sebuah sirkuit, lalu hapus satu buah sisi dari sirkuit ini. G akan tetap terhubung dan jumlah sirkuitnya berkurang satu. Bila proses ini dilakukan berulang-ulang sampai semua sirkuit di G hilang, maka G menjadi sebuah pohon T, yang dinamakan pohon merentang (spanning tree). 

Disebut pohon merentang karena semua simpul pada pohon T sama dengan semua simpul pada graf G, dan sisi-sisi pada pohon T ⊆ sisi-sisi pada graf G. Dengan kata lain V1 = V dan E1 ⊆ E (Munir, 2012). Dari setiap graf terhubung mempunyai paling sedikit satu buah pohon merentang (Spanning Tree). Pada satu Spanning Tree, sisi pada spanning tree T disebut dengan sebuah cabang (branch) dari T sedangkan sisi dari graf G yang tidak terdapat di dalam spanning tree disebut dengan tali (chord). Suatu sisi bisa saja merupakan branch untuk suatu spanning tree T tetapi merupakan chord untuk spanning tree yang lainnya.

sebuah graf G dapat dibangun pohon (tree) dengan cara menghapus sirkuit satu demi satu sehingga diperoleh tree seperti terlihat pada gambar berikut ini.

======

artikel ini disarikan dari slide materi kuliah SOD bu Habibah Nurfauziah, S.Kom, M.Si