Handout No: 20 [Handout berikutnya, sebelumnya, atau kembali ke halaman utama]

      Struktur Data graf: representasi & algoritma-algoritma

      14 April 1999

      Goal: Rrepresentasi, DFS, BFS, Shortest path Dijkstra
      Disclaimer: pada tanggal 5 Mei 1999 page ini baru selesai 90% ....

      Representasi Graph

      Representasi Matriks Keterhubungan Langsung (Adjacency Matrix)

      Suatu matriks digunakan untuk menyatakan adjacency set setiap verteks dalam baris-barisnya. Nomor baris menyatakan nomor verteks adjacency berasal dan nomor kolom menunjukkan nomor verteks kemana arah adjacency. Elemen matriks [x, y] berharga 1 bila terdapat sisi dari x ke y dan berharga 0 bila tidak ada.

      Harga biner ini memungkinkan penggunaan 1 bit untuk setiap sel matriks. Misalnya pada suatu graph dengan jumlah verteks 48 dapat digunakan 6 byte perbaris (semua 38 baris, jadi diperlukan 48 x 6 byte). Untuk mengetahui harga elemen matrilks maka diperlukan operasi shift-right serts operasi boolean and. Misalnya adjacency dari verteks 15 ke verteks 27 pada contoh 48 verteks di atas maka byte ke ë 27/8û dari baris ke 15 di-shift-right sebanyak (27 mod 8) posisi lalu di-and-kan dengan bilangan 1. Bila hasilnya 1 maka 15 adjacent ke 27, bila 0 maka tidak.
      Direpresentasikan dalam matriks sbb.
      Dari\Ke A B C D E F G H I J K L M
      A - 1 1 1 0 1 0 0 0 0 0 0 0
      B 1 - 1 0 0 0 0 1 0 0 0 0 0
      C 1 1 - 0 1 0 1 1 1 0 0 0 0
      D 1 0 0 - 1 1 1 0 0 0 1 1 0
      E 0 0 1 1 - 1 0 0 0 0 0 0 0
      F 1 0 0 1 1 - 0 0 0 0 0 0 0
      G 0 0 1 1 0 0 - 0 1 0 1 0 0
      H 0 1 1 0 0 0 0 - 1 0 0 0 0
      I 0 0 1 0 0 0 1 1 - 1 0 0 1
      J 0 0 0 0 0 0 0 0 1 - 1 0 1
      K 0 0 0 1 0 0 1 0 0 1 - 1 0
      L 0 0 0 1 0 0 0 0 0 0 1 - 1
      M 0 0 0 0 0 0 0 0 1 1 0 1 -

      Sudah tentu, representasi bit ini hanya dapat digunakan untuk graph yang tidak berbobot. Untuk graph berbobot maka diperlukan suatu matriks di mana setiap elemennya menyatakan harga (atau harga-harga) bobot tersebut. Adjacency secara implisit terepresentasikan dengan bobot-bobot ini. Bila harga bobot ¥ (tak hingga) maka berarti tidak terdapat sisi adjacent ybs.

      Matriks ini digunakan baik untuk undigraph maupub digraph. Untuk undigraph maka matriks merupakan matriks simetris.
      Dari\Ke A B C D E F G H I J K L M
      A - 24 43 33 ¥ 31 ¥ ¥ ¥ ¥ ¥ ¥ ¥
      B 24 - 18 ¥ ¥ ¥ ¥ 45 ¥ ¥ ¥ ¥ ¥
      C 43 18 - ¥ 16 ¥ 22 35 15 ¥ ¥ ¥ ¥
      D 33 ¥ ¥ - 19 22 39 ¥ ¥ ¥ 13 27 ¥
      E ¥ ¥ 16 19 - 15 ¥ ¥ ¥ ¥ ¥ ¥ ¥
      F 31 ¥ ¥ 22 15 - ¥ ¥ ¥ ¥ ¥ ¥ ¥
      G ¥ ¥ 22 39 ¥ ¥ - ¥ 21 ¥ 13 ¥ ¥
      H ¥ 45 35 ¥ ¥ ¥ ¥ - 25 ¥ ¥ ¥ ¥
      I ¥ ¥ 15 ¥ ¥ ¥ 21 25 - 19 ¥ ¥ 35
      J ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ 19 - 10 ¥ 15
      K ¥ ¥ ¥ 13 ¥ ¥ 13 ¥ ¥ 10 - 19 ¥
      L ¥ ¥ ¥ 27 ¥ ¥ ¥ ¥ ¥ ¥ 19 - 25
      M ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ 35 15 ¥ 25 -

      Representasi List Keterhubungan Langsung (Adjacency List)

      Mengingat bahwa rasio degree (atau outdegree pada digraph) rata-rata verteks terhadap jumlah verteks dalam sejumlah masalah adalah bisa sangat kecil maka representasi matriks tersebut akan berupa matriks sparse yaitu sebagian besarnya berisikan bilangan nol (atau bilangan ¥ pada weighted graph). Untuk kepentingan efisiensi ruang maka tiap baris matriks tersebut digantikan list yang hanya berisikan verteks-verteks dalam adjacency set Vx dari setiap verteks x.

      Keseluruhan graph adalah array dari verteks yang pada masing-masing verteksnya digunakan suatu struktur list untuk menyimpan indeks-indeks dari verteks yang adjacent dari verteks yang bersangkutan. Jika list menggunakan fixed array maka perlu disimpan pula degree (atau out degree) yang menyatakan panjang dari list. Jika menggunakan list berkait maka informasi degree ini tidak diperlukan.

      Pada masalah yang sangat dinamis di mana selama proses berlangsung bisa muncul verteks baru atau dihapusnya suatu verteks yang ada dari graph maka struktur array untuk verteks ini dapat menggunakan suatu list berkait pula. Pada struktur demikian maka list dari adjacent verteks berisikan pointer dari verteks-verteks. Secara keseluruhan apabila adjacent list menggunakan list berkait pula, graph direpresentasikan dengan multilevel linked-list.

      Algoritma-algoritma Pencarian

      Pencarian atau yang mirip dengan pencarian adalah proses-proses yang paling umum dalam masalah graph. Terdapat 2 metoda pencarian:
      • Depth First Search (DFS): pada setiap pencabangan, penelusuran verteks-verteks yang belum dikunjungi dilakukan selengkapnya pada pencabangan pertama, kemudian selengkapnya pada pencabangan kedua, dan seterusnya secara rekursif.
      • Breadth First Search (BFS): pada setiap pencabangan penelusuran verteks-verteks yang belum dikunjungi dilakukan pada verteks-verteks adjacent, kemudian berturut-turut selengkapnya pada masing-masing pencabangan dari setiap verteks adjacent tersebut secara rekursif.

      Implementasi algoritma DFS rekursif

      Rekursivitas dilakukan dalam fungsi Traverse() class Graph { ....
      void DFS() { for (each vertex v in G) v.Status = false; for (each vertex v in G) if (v.Status == false) Traverse(v); }
      void Traverse(Vertex v) { Vertex w;
      w.Visit();
      v.Status = true;
      for (each adjac. vertex w from v) { if (w.Status == false) Traverse(w); } }       }       }

      Implementasi algoritma DFS nonrekursif

      Memanfaatkan stack sebagai struktur data pendukung class Graph { ....
      void DFS() { Stack s = new Stack();
      Vertex v, w, t;
      for (each vertex v in G) v.Status = false; for (each vertex v in G) { s.push(v);
      while (s.emptyStack() == false){ w=s.pop();
      if (v.Status == false) { visit(w);
      v.Status = true;
      for (each adjac. vertex t from w) s.push(t);       }       }       }       }       }

      Implementasi algoritma BFS

      Algoritma BFS menjadi kurang straightforward jika dinyatakan secara rekursif. Jadi sebaiknya diimplementasikan secara nonrekursif dengan memanfaatkan queue sebagai struktur data pendukung class Graph { ....
      void BFS() { Queue q = new Queue();
      Vertex v, w, t;
      for (each vertex v in G) v.Status = false;
      for (each vertex v in G) {       if (v.Status == false) { v.Status = true;
      q.add(v);
      while (EmptyQueue(Q) == false){ w = q.remove();
      visit(w);
      for (each adjac. vertex T from w){ if (t.Status == false) { t.Status = true;
      q.add(t);       }       }       }       }       }       }       }

      Masalah Pencarian Lintasan Terpendek

      Pencarian shortest path (lintasan terpendek) dalam adalah termasuk masalah yang paling umum dalam suatu weighted, connected graph. Lebih lanjut lagi dalam kelas masalah ini terdapat subkelas-subkelas masalah yang lebih spesifik. Misalnya pada jaringan jalan raya yang menghubungkan kota-kota disuatu wilayah, hendak dicari
      • lintasan terpendek yag menghubungkan antara dua kota berlainan tertentu (Single-source Single-destination Shortest Path Problems)
      • semua lintasan terpendek masing-masing dari suatu kota ke setiap kota lainnya (Single-source Shortest Path problems)
      • semua lintasan terpendek masing-masing antara tiap kemungkinan pasang kota yang berbeda (All-pairs Shortest Path Problems)
      Untuk memecahkan masing-masing dari masalah-masalah tersebut terdapat sejumlah solusi.
      • Algoritma Dijkstra untuk Single-source Shortest Path
      • Algoritma Floyd-Warshall untuk masalah All-pairs Shortest Path
      • Algoritma Johnson untuk masalah All-pairs Shortest Path pada sparse graph

      Dalam beberapa masalah graph lain, suatu graph dapat memiliki bobot negatif dan kasus ini dipecahkan oleh algoritma Bellman-Ford.

      Yang akan dibahas di sini adalah algoritma Dijkstra yaitu mencari lintasan terpendek dari suatu verteks asal tertentu vs ke setiap verteks lainnya (digunakan juga dengan sangat optimal pada masalah single-destination). Kelas-kelas masalah lain dibahas dengan cukup rinci di Cormen et. al, Introduction to Algorithms, McGraw-Hill, 1990.

      Algoritma Dijkstra

      Algoritma ini mirip dengan algoritma Prim untuk mencari MST, yaitu pada tiap iterasi memeriksa sisi-sisi yang menghubungkan subset verteks W dan subset verteks (V-W) dan memindahkan verteks w dari (V-W) ke W yang memenuhi kriteria tertentu. Perbedaannya terletak pada kriteria itu sendiri.
      • Jika yang dicari algoritma Kruskal adalah sisi dengan bobot terkecil dari sisi-sisi di atas dalam setiap iterasinya,
      • dalam algoritma Dijkstra, yang dicari adalah sisi yang menghubungkan ke suatu verteks di (V-W) sehingga jarak dari verteks asal Vs ke verteks tersebut adalah minimal.

      Dalam implementasinya penghitungan jarak dari verteks asal vs disederhanakan dengan menambahkan field minpath pada setiap verteks; field-field minpath ini diinisialisasi sesuai dengan adjacencynya dengan vs, kemudian dalam setiap iterasi di-update bersamaan masuknya w dalam W. Field minpath ini menunjukkan jarak dari vs ke verteks yang bersangkutan terpendek yang diketahui hingga saat itu. Jadi pada verteks dalam W, minpath sudah menunjukkan jarak terpendek dari Vs untuk mencapai verteks yang bersangkutan, sementara pada (V-W) masih perlu diupdate pada setiap iterasi dalam mendapatkan verteks w seperti diterangkan di atas. Yaitu, setiap mendapatkan w maka update minpath setiap adjacent verteks x dari w di (V-W) sisa dengan:

      • minimum (minpath dari x , total minpath w + panjang sisi yang bersangkutan), agar dapat berlaku umum maka di awal algoritma seluruh minpath diinisialisasi dengan +¥ .

      Demikian halnya pencarian w itu sendiri disederhanakan menjadi pencarian node di (V-W) dengan minpath terkecil.

      Selengkapnya algoritma Dijkstra adalah sebagai berikut.

      • Inisialisasi
        • W berisi mula-mula hanya vs
        • field minpath tiap verteks v dengan
        • Weight[vs, v], jika ada sisi tersebut, atau,
        • +¥ , jika tidak ada.
      • Lalu, dalam iterasi lakukan hingga (V-W) tak tersisa (atau dalam versi lain: jika ve ditemukan):
        • dari field minpath tiap verteks cari verteks w dalam (V-W) yang memiliki minpath terkecil yang bukan tak hingga.
        • jika ada w maka
          • masukkan w dalam W
          • update minpath pada tiap verteks t adjacent dari w dan berada dalam (V-W) dengan: minimum (minpath[t] , minpath[w] + Weight[w, t])

      Verteks-verteks dalam W dapat dibedakan dari verteks dalam (V-W) dengan suatu field yang berfungsi sebagai flag atau dengan struktur liked-list. Informasi lintasan dapat diketahui dengan pencatatan predesesor dari setiap verteks yang dilakukan pada saat update harga minpath tersebut (fungsi minimum): jika minpath[t] diupdate dengan (minpath[w]+Weight[w, t]) maka predesesor dari t adalah w. pada tahap inisialisasi predesesor setiap verteks diisi oleh vs.

      Contoh masalah:
      Pada weighted graph di atas akan dicari shortest path dari A ke G. Algoritma ini akan bekerja sbb. (Notasi penulisan: X:mvia, dibaca, vertex X dicapai dari A melalui via dengan panjang path m, warna verteks A menunjukkan status visit dari X = true, (update): menunjukkan terjadinya update harga minpath dan via dari verteks ybs.).

      • Pada tahap inisialisasi: tabel MinPath diisi:
        {A:0, B: 24A, C: 43A, D: 33A, F: 31A, yang lain ¥ }
      • Iterasi ke 1: dari tabel minpath didapat B (via A) dan update tabel MinPath menjadi:
        A:0, B: 24A, C: 42B(update), D: 33A, F: 31A, H: 69B(update), yang lain ¥}
      • Iterasi ke 2: dari tabel minpath didapat F (via A) dan update tabel MinPath menjadi:
        A:0, B: 24A, C: 42B, D: 33A, E: 46B(update), F: 31A, H: 69B, yang lain ¥}
      • Iterasi ke 3: dari tabel minpath didapat D (via A) dan update tabel MinPath menjadi:
        A:0, B: 24A, C: 42B, D: 33A, E: 46B, F: 31A, G: 72D(update), H: 69B, K: 46D(update), L: 60D(update), yang lain ¥}
      • Iterasi ke 4: dari tabel minpath didapat C (via B) dan update tabel MinPath menjadi:
        A:0, B: 24A, C: 42B, D: 33A, E: 46B, F: 31A, G: 64D, H: 69B, I: 57C(update), K: 46D, L: 60D, yang lain ¥}
      • Iterasi ke 5: dari tabel minpath didapat E (via B) dan update tabel MinPath menjadi:
        A:0, B: 24A, C: 42B, D: 33A, E: 46B, F: 31A, G: 64D, H: 69B, I: 57C, K: 46D, L: 60D, yang lain ¥}
      • Iterasi ke 6: dari tabel minpath didapat K (via D) dan update tabel MinPath menjadi:
        A:0, B: 24A, C: 42B, D: 33A, E: 46B, F: 31A, G: 59K(update), H: 69B, I: 57C, J: 56K(update), K: 46D, L: 60D, yang lain ¥}
      • Iterasi ke 7: dari tabel minpath didapat J (via K) dan update tabel MinPath menjadi:
        A:0, B: 24A, C: 42B, D: 33A, E: 46B, F: 31A, G: 59K, H: 69B, I: 57C, J: 56K, K: 46D, L: 60D, M: 71J(update), yang lain ¥}
      • Iterasi ke 8: dari tabel minpath didapat I (via C) dan update tabel MinPath menjadi:
        A:0, B: 24A, C: 42B, D: 33A, E: 46B, F: 31A, G: 59K, H: 69B, I: 57C, J: 56K, K: 46D, L: 60D, M: 71J}
      • Iterasi ke 9: dari tabel minpath didapat G (via K) dan update tabel MinPath menjadi:
        A:0, B: 24A, C: 42B, D: 33A, E: 46B, F: 31A, G: 59K, H: 69B, I: 57C, J: 56K, K: 46D, L: 60D, M: 71J}
      • Karena G adalah verteks tujuan maka algoritma berhenti dan shortest path dari A ke G diperoleh dengan panjang 59. Route ybs: A-D-K-G.

      Berikut ini adalah applet demo Shortest path. Isikan asal dan tujuan dengan id dari verteks yang dicari atau melakukan click-and-drag pada verteks-verteks asal-tujuan. Tujuan bisa diisi tanda bintang (*) untuk mencari shortest path ke semua verteks (Lihat juga contoh dengan graph yang lebih besar!!!).

      Handout berikutnya, sebelumnya, atau kembali ke halaman utama