GRAPH

Graph adalah kumpulan dari simpul dan busur yang secara matematis dinyatakan sebagai : G = (V, E)  Dimana     
       G = Graph
       V = Simpul atau Vertex, atau Node, atau Titik
       E = Busur atau Edge, atau arc

Contoh Graph

                        Undirected Graph

V terdiri dari v1, v2, …, v5
E terdiri dari e1, e2, … , e7

Kemungkinan kemungkinan dalam Graph
  1. Sebuah graph mungkin hanya terdiri dari satu simpul
  2. Sebuah graph belum tentu semua simpulnya terhubung dengan busur
  3. Sebuah graph mungkin mempunyai simpul yang tak terhubung dengan yang lain
  4. Sebuah graph mungkin semua simpulnya saling berhubungan

Graph Berarah (Direct Graph) dan tidak berarah (Undirected Graph)

Dapat dilihat dari bentuk busur yang artinya urutan penyebutan pasangan 2 simpul

  1. Graph tak berarah (undirected graph atau non-directed graph) : Urutan simpul dalam sebuah busur tidak dipentingkan. Mis busur e1 dapat disebut busur AB atau BA
  2. Graph berarah (directed graph) : Urutan simpul mempunyai arti. Mis busur AB adalah e1 sedangkan busur BA adalah e8. 
  3. Graph Berbobot (Weighted Graph) Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul, maka busur tersebut dinyatakan memiliki bobot. Bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 buah titik, jumlah rata-rata kendaraan perhari yang melalui sebuah jalan, dll.

Graph Berbobot

Panjang busur (atau bobot) mungkin tidak digambarkan secara panjang yang proposional dengan bobotnya. Misal bobot 5 digambarkan lebih panjang dari 7.

Istilah istilah pada Graph

  1. Incident.
    Jika e merupakan busur dengan simpul-simpulnya adalah v dan w yang ditulis e=(v,w), maka v dan w disebut “terletak” pada e, dan e disebut incident dengan v dan w
  2. Degree (derajat), indegree dan outdegree
    •  Degree sebuah simpul adalah jumlah busur yang incident dengan simpul tersebut.  
    •  Indegree sebuah simpul pada graph berarah adalah jumlah busur yang kepalanya incident dengan  simpul tersebut, atau jumlah busur yang “masuk” atau menuju simpul tersebut.
    • Outdegree sebuah simpul pada graph berarah     adalah jumlah busur     yang ekornya incident dengan simpul tersebut, atau jumlah busur yang “keluar” atau berasal dari simpul tersebut.  
  3. Adjacent
    Pada graph tidah berarah, 2 buah simpul disebut adjacent bila ada busur yang menghubungkan kedua simpul tersebut. Simpul v dan w disebut adjacent.Successor dan Predecessor

    Pada graph berarah, simpul v disebut adjacent dengan simpul w bila ada busur dari w ke v.
  4. Pada graph berarah, bila simpul v adjacent dengan simpul w, maka simpul v adalah successor simpul w, dan simpul w adalah predecessor dari simpul v.  
  5. Path Sebuah path adalah serangkaian simpul-simpul yang berbeda, yang adjacent secara berturut-turut dari simpul satu ke simpul berikutnya.

Representasi Graph dalam bentuk matrix

  1. Adcency Matrix Graph tidak berarah


  2.  Adjacency Matrix Graph Berarah
Representasi Graph dalam bentuk Linked List
  1. Adjency List graph tak berarah
  2. Digambarkan sebagai sebuah simpul yang memiliki 2 pointer.
    Simpul vertex :        Simpul edge :

  3. Define struct untuk sebuah simpul yang dapat digunakan sebagai vertex maupun edge.
    typedef struct tipeS {
        tipeS *Left;
        int INFO;
        tipeS *Right;
        };
    tipeS *FIRST, *PVertex, *PEdge;

Contoh : untuk vertex A, memiliki 2 edge yang terhubung yaitu e1 dan e2.


 Gambar disana dapat di susun dengan lebih sederhana, sebagai berikut :


 Adjency List Graph Berarah 

Graph Berarah dan berbobot

 Penyelesaian kasus graph gambar diatas
  1. Define simpul untuk vertex dan edge Mengidentifikasi Simpul pertama sebagai  vertex yang pertama 
  2. Tambahkan vertex sisanya 
  3. Tambahkan edge pada masing-masing vertex yang telah terbentuk 
  4. Tampilkan representasi graph berikut bobotnya
 
 
Graph VS Tree  
  1. Sebuah Graph memiliki ciri berbeda dengan Tree Dalam Graph, edge bebas menghubungkan node-node mana pun. Dalam Tree, satu node hanya boleh terhubung ke satu parent dan beberapa child, tidak boleh ke beberapa parent
  2. Dalam sebuah Graph bisa dirunut jalur edge yang membentuk jalur putaran dari 1 node kembali ke node semula; ini tidak boleh terjadi dalam Tree
Spanning Tree
Spanning Tree adalah sebuah Tree yang dibuat dari sebuah Graph dengan menghilangkan beberapa edge-nya. Tree ini harus mengandung semua node yang dimiliki Graph.
Minimum Spaning Tree
  1. Jika Weighted Graph diubah menjadi Spanning Tree, tiap kombinasi Tree yang dapat dibuat memiliki total weight yang berbeda-beda.
  2. Problem Minimum Spanning Tree (MST) berusaha mencari Tree seperti apa yang bisa dibuat dari sebuah Weighted Graph dengan total weight seminimal mungkin
Mst dengan Metode Greedy
  1. Algoritma Prim-Dijkstra Ditemukan oleh Robert C. Prim di tahun 1957 dan oleh Edsger Dijkstra di tahun 1959.
  2. Algoritma Kruskal Ditemukan oleh Joseph Kruskal di tahun 1956.
Algoritma Prim-Dijkstra
Langkah-langkah algoritma Prim-Dijkstra :
  1. Tentukan node awal, asumsikan semua edge berwarna hitam
  2. Dari semua edge yang terhubung ke node awal tersebut, pilih edge dengan bobot terkecil
  3. Tandai edge yang dipilih dengan warna hijau
  4. Apabila ada edge yang kedua node-nya sudah terkena jalur hijau, tandai edge tersebut dengan
  5. warna merah (karena jika dipilih akan membentuk jalur putaran à melanggar syarat tree)
  6. Tentukan node-node yang berada di jalur hijau sebagai node aktif
  7. Bandingkan semua edge yang terhubung ke node aktif (hanya edge hitam), pilih yang bobotnya terkecil
  8. Tandai edge yang dipilih dengan warna hijau
  9. Ulangi dari langkah ke-4 hingga semua node terlewati jalur hijau
  10. Ketika semua node telah dilewati jalur hijau, maka jalur hijau yang terbentuk adalah MST yang dicari
Algoritma Kruskal
Langkah langkah algoritma Kruskal :
  1. Asumsikan semua edge berwarna hitam
  2. Bandingkan bobot semua edge hitam, pilih edge dengan bobot terkecil
  3. Tandai edge yang dipilih dengan warna hijau
  4. Apabila ada edge yang kedua node-nya sudah terkena jalur hijau, tandai edge tersebut dengan
  5. warna merah (karena jika dipilih akan membentuk jalur putaran à melanggar syarat tree)
  6. Ulangi dari langkah ke-2 hingga semua node terlewati jalur hijau
  7. Ketika semua node telah dilewati jalur hijau, maka jalur hijau yang terbentuk adalah MST yang dicari
Contoh Problem MST
 

Shortest Path

Dalam sebuah Graph yang setiap edge yang memiliki weight (bobot), jarak terpendek (shortest path) antara 2 node dapat dicari dengan Metode Greedy 
 
Misal kita hendak mencari jalur terpendek (shortest path) dari node A ke node F, bagaimana cara menghitungnya dengan Metode Greedy?

Metode Greedy Shortest Path
Langkah-langkah Metode Greedy
  1. Berangkat dari node awal 
  2. Pilih edge yang memiliki bobot terkecil dari node tersebut 
  3. Maju ke node yang dituju 
  4. Ulangi dari langkah ke-2 hingga mencapai node tujuan
Contoh Problem Shortest Path