Graph Problem

Apa itu graph ? Grap adalah sekumpulan node ( simpul ) di dalam bidang dua dimensi yang dihubungkan dengan sekumpulan garis (sisi). Graph dapat digunakan untuk merepresentasikan objek – objek diskrit dan hubungan antara objek - objek tertentu dengan objek sebagai node (simpul) , bulatan atau titik (Vertex), sedangkan hubungan antara objek dinyatakan dengan garis (Edge). Graph merupakan suatu cabang yang memiliki banyak terapan, banyak sekali struktur dan masalah yang bisa diselesaikan dengan graph .

Istilah – istilah dalam Graph antara lain :

1. Vertex yaitu himpunan node / titik pada sebuah graph.

2. Edge yaitu himpunan garis yang menghubungkan tiap node / vertex

3. Adjacent sesuai dengan kata Adjacent yang artinya “bersebelahan, berdekatan, berdampingan”.     

Jadi Adjacent adalah dua buah titik dikatakan berdekatan (adjacent) jika dua buah titik tersebut terhubung dengan sebuah sisi yang lain .

perhatikan gambar dibawah ini : 

Keterangan : v = vertex

                      e = edge

1. Titik v4 adjacent dengan titik v2 dan v3
2. Titik v2 adjacent dengan titik v1 dan v4
3. Titik v1 adjacent dengan titik v2 dan v3
4. Titik v3 adjacent dengan titik v1 dan v4

            Tetapi Titik v1 dengan v4 tidak adjacent karena tidak terhubung

1  
      4. Weight yaitu menyatakan hubungan antara kedua buah vertex maka edge tersebut dikatakan  memiliki bobot. Graph yang memiliki bobot dapat disebut sebagai graph berbobot atau weight graph

2    5.  Path (lintasan) yaitu serangkaian vertex yang berbeda yang adjacent secara berturut – turut dari vertex satu ke vertex berikutnya.

       6. Direct (arah) merupakan arah suatu graph . Pada graph berarah urutan vertex memiliki arti.

    Implementasi Graph

       Implementasi suatu graph dapat dilihat dalam kasus algoritma greedy . Algoritma Greedy merupakan jenis algoritma yang menggunakan pendekatan penyelesaian masalah dengan mencari nilai maksimum (local maximum) sementara pada setiap langkahnya . Algoritma nini merupakan metode yang paling populer untuk memecahkan suatu persoalan optimasi .  

Sebagai contoh masalah sehari – hari yang menggunakan prinsip algoritma greedy salah satunya adalah mencari jalu tercepat/tersingkat dari UNIKOM menuju Trans Studio Mall . 

Algoritma greedy disini membuat solusi langkah per langkah , banyak sekali pilihan yang perlu di eksplorasi pada setiap langkahnya . Oleh karena itu , setiap langkah harus dibuat keputusan yang tepat untuk menentukan pilihannya . Suatu keputusan yang sudah diambil tidak boleh diubah lagi pada langkah selanjutnya .

Perhatikan gambar dibawah ini :

Misalnya kita ingin bergerak dari UNIKOM menuju ke Trans Studio Bandung dan kita telah menemukan beberapa jalur dari peta . Suatu sistem peta (Google Maps) pada gambar secara otomatis mencari jalur tercepat menuju lokasi degan waktu kira-kira 37 menit perjalanan tanpa macet . Pada gambar diatas pada dasarnya menunjukan titik – titik yang saling berhubungan , dengan jarak tertentu dan waktu tertentu pada masing-masing titik tersebut . Misalkan peta diatas kita dipresentasikan dengan titik-titik penghubung seperti berikut :

Dari gambar di atas, kita dapat melihat bagaimana sebuah jalur perjalanan dapat dipresentasikan dengan menggunakan graph misal A = UNIIKOM dan B = TSM (Trans Studio Mall). Maka dari itu, untuk menyelesaikan suatu masalah jarak terpendek kita menggunakan struktur data graph untuk merepresentasikan peta. Berikut graph yang digunakan :

k   Untuk mencari jarak terpendek dari B ke A, langkah – langkah algoritma greedy adalah sebagai berikut:

      1. Kunjungi satu titik pada graph , dan ambil seluruh titik yang dapat dikunjungi dari titik sekarang
      2.Cari local maximum ke titik selanjutnya.
      3. Tandai graph sekarang sebagai graph yang telah dikunjungi, dan pindah ke local maximum yang telah ditentukan .
      4. Kembali ke langkah 1 sampai titik tujuan didapatkan.

Jika pada graph B ke A kita akan mendapatkan pergerakan seperti berikut :
- Mulai dari titik awal (B). Ambil seluruh titik yang dapat dikunjungi.

- Local Maximum adalah C, karena jarak ke C adalah yang paling dekat .
- Tandai A sebagai titik yang telah dikunjungi, dan pindah ke C
- Ambil seluruh titik yang dapat dikunjungi dari C

- Local Maximum adalah ke G, karena yang paling dekat.
- Tandai C sebagai titik yang telah dikunjungi , dan pindah ke G
- Ambil seluruh titik yang dapat dikunjungi dari G

- Local Maximum adalah ke I, karena yang paling dekat.
- Tandai G sebagai titik yang telah dikunjungi , dan pindah ke I
- Ambil seluruh titik yang dapat dikunjungi dari I

- Local Maximum adalah ke A, karena yang paling dekat.
- Tandai I sebagai titik yang telah dikunjungi , dan pindah ke A
- Tandai semua titik yang sudah dikunjungi

Dengan menggunakan algoritma greedy pada graph diatas , maka hasil akhir yang kita dapat sebagai jarak terpendek adalah B-C-G-I-A. Hasil jarak terpendek yang didapatkan ini tidak tepat dengan jarak terpendek yang sebenarnya (B-C-F-A). Algoritma greedy memang tidak selamanya memberikan solusi yang optimal dan akurat , dikarenakan pencarian local maximum pada setiap langkahnya tidak memperhatikan solusi secara keseluruhan .

Referensi :

 https://bertzzie.com/knowledge/analisis-algoritma/Greedy.html

http://t4urusboy08.blogspot.co.id/

https://www.it-jurnal.com/pengertian-algoritma-greedy/