Graph


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

Komentar

Posting Komentar

Postingan populer dari blog ini

Dimensi Array

Gambar
Dimensi Array Array adalah sesuatu yang berbaris atau berderet-deret sedemikian rupa sehingga alamatnya saling bersambungan atau bersebelahan/berdampingan (contiuous). Array dibagi menjadi berikut yaitu: Berikut penjabarannya ...  Array satu dimensi  Sebuah variabel yang menyimpan sekumpulan data yang memiliki tipe sama dan elemen yang akan diakses hanya melalui 1 indeks. Bentuk umum: Tipe_data nama_array_[jumlah_maks_data] Contoh : int Nilai[5] : nilai [1], nilai [2], nilai [3] , nilai [4], nilai [5] 75  85  80  70  65 Berikut adalah contoh program menggunakan Array satu dimensi yang di dalam programnya proses deklarasi dan proses penampilan nilai yang terdapat pada elemen array. Contoh program satu dimensi :  #include <iostream> using namespace std; int main(){      // Deklarasi sekaligus inisialisasi (pengisian awal)      // Array 'ARnilai' dengan 5 buah elemen berisi int   ...
Baca selengkapnya

Program Tree C++

Gambar
Program Tree C++ Saya kali ini akan membuat program Tree melalui program C++ Berikut contoh codingan program Tree C++ : #include<stdio.h> typedef struct node{   char data;   node *kiri;   node *kanan; }; node *akar=NULL; addNode(node **akar, char isi) {   if((*akar)==NULL){   node *baru;   baru= new node;   baru->data = isi;   baru->kiri = NULL;   baru->kanan = NULL;   (*akar)=baru;   } } preOrder(node *akar) {   if(akar !=NULL) {   printf("%c ", akar->data);   preOrder(akar->kiri);   preOrder(akar->kanan);   } } inOrder(node *akar) {   if(akar !=NULL) {   inOrder(akar->kiri);   printf("%c ", akar->data);   inOrder(akar->kanan);   } } postOrder(node *akar) {   if(akar !=NULL) {   postOrder(akar->kiri);   postOrder(akar->kanan);   printf("%...
Baca selengkapnya

Stack

Gambar
Stack Struktur Data Dalam dunia komputer, penggunaan stack atau tumpukan merupakan salah satu komponen penting untuk menjamin proses penanganan suatu data disampingi hal lain seperti quenue (antrian), linked list, dan tree.  Stack adalah suatu koleksi atau kumpulan item data yang terorganisasi dalam bentuk linear yang operasi pemasukan dan penghapusan datanya dilakukan pada salah satu sisinya. Sedangkan pengertian Stack pada struktur data adalah tumpukan dari benda, sekumpulan data yang seolah-olah diletakkan di atas data yang lain. koleksi dari objek-objek homogen atau suatu urutan elemen yang dapat diambil dan ditambah hanya pada posisi akhir (top) saja. Stack bersifat LIFO (Last In First Out) yaitu benda yang terakhir masuk ke dalam stack akan menjadi yang pertama keluar dari stack. Operasi-operasi yang biasanya terdapat pada stack yaitu: Push : digunakan untuk menambah item pada stack yang terdapat pada tumpukan paling atas Pop : digunakan untuk...
Baca selengkapnya