Terdapat berbagai macam cara untuk menyimpan graf dalam sistim komputer. Data struktur yang digunakan bergantung pada struktur graf dan algoritma yang digunakan untuk memanipulasi graf tersebut. Secara teoritis, dapat terlihat dengan jelas perbedaan antara representasi graf dengan struktur data list dan matriks, namun dalam aplikasi konkret, struktur data terbaik adalah gabungan dari keduanya data list sering digunakan pada sparse graf(graf dengan jumlah simpul yang jarang) karena
struktur data ini membutuhkan memori dalam jumlah yang lebih sedikit. Struktur data matriks di sisi lain menjajikan akses yang lebih cepat dalam aplikasi tertentu namun memakan memori yang jauh lebih besar apabila grafnya sangat besar [4].
Terdapat dua buah cara yang umum diketahui dalam merepresentasikan list, yaitu:
• Incidence list: Sisi-sisi direpresentasikan dengan senarai yang mengandung pasangan
(terurut apabila grafnya berarah) simpul (yang dihubungkan oleh sisi yang
bersangkutan), dan bobot dari sisi jika sisinya memiliki bobot.
• Senarai ketetanggaan: Hampir sama dengan incidence list, tiap simpul memiliki list
dengan simpul tetangganya. Hal ini menimbulkan redudansi pada graf tak berarah,
sebagai contoh:
apabila simpul A dan B bertetangga, maka list ketetanggaan dari A akan mengandung
B,demikian pula sebaiknya, list ketetanggaan dari B akan mengandung A. Struktur
data ini cenderung lebih cepat daripada incidence list, namun dibayar dengan
ukuran memori yang lebih besar.
Berbeda dengan list, varian struktur data graf dengan matriks lebih banyak, yaitu:
• Incidence matriks: Graf direpresentasikan dengan matriks sisi dengan simpul, dimana
[sisi, simpul] mengandung informasi sisi tersebut (kasus termudah: 1 – terhubung, 0 – tak terhubung).
• Matriks ketetanggaan: Struktur data ini merupakan struktur data yang cukup banyak
digunakan dalam merepresentasikan sebuah graf, apabila terdapat sebuah sisi yang
menghubungkan simpul x dan y, maka Mi,j berisi 1, selain itu 0, representasi demikian
memberikan kemudahan untuk mencari subgraf dan membalik (reverse) graf jika dibutuhkan.
• Matriks Laplacian: Didefinisikan sebagai matriks derajat - matriks ketetanggaan,
terkandung didalamnya informasi ketetanggaan dan informasi derajat sebuah simpul.
• Matriks jarak: Berupa matriks n x n, dimana Mi,j
berisi informasi jarak terdekat antara i dan jjika tidak terdapat jalur yang menghubungkan i dan j maka Mi,j = ~.
STRUKTUR DATA GRAF UNTUK HIMPUNAN SALING LEPAS
Struktur data himpunan saling lepas, yang juga dikenal dengan union-find set, adalah struktur data yang terus menyimpan partisi dari himpunan elemen selama selang waktu tertentu ketika pemrosesan masalah dilakukan. Terdapat 3 operasi utama yaitu [10]:
• MakeSet: Membuat sebuah partisi baru yang berisi sebuah elemen.
• Find: Mencari tahu pada partisi manakah sebuah elemen berada.
• Merge/Union: Menggabungkan dua buah partisi menjadi sebuah partisi.
Terdapat beberapa solusi untuk masalah ini,menggunakan struktur data senarai berantai, atau struktur data pohon himpunan saling lepas. Sampai saat ini, solusi yang paling mangkus dan banyak digunakan adalah struktur data pohon himpunan saling lepas dengan path compression dan union rank heuristic, dengan performa O((n)), untuk n)merupakan fungsi yang bertumbuh sangat lambat dan pada aplikasinya hampir tidak pernah melebihi 5
[10].
Senarai Berantai Himpunan Saling Lepas
Mungkin cara termudah dalam membentuk struktur
data himpunan saling lepas adalah dengan membuat
senarai berantai untuk tiap himpunan [1].
Algoritma MakeSet sudah cukup jelas, membuat
senarai dengan satu elemen. Union hanya
menggabungkan dua buah senarai. Sayangnya,
dengan implementasi demikian, Find memiliki
kompleksitas O(n) (linear).
Kita dapat mencoba mengurangi waktu eksekusi
tersebut dengan menggabungkan senarai yang lebih
pendek pada senarai yang lebih panjang, yang biasa
disebut weighted union heuristic. Metoda ini juga
perlu menyimpan panjang tiap senarai ketika sebuah
operasi dilakukan untuk menjaga kemangkusan
algoritmanya. Menggunakan metoda ini, sederetan m
buah operasi MakeSet, Union, dan Find dengan n
buah elemen membutuhkan O(m + nlog n) waktu.
Untuk memperoleh hasil yang lebih baik, kita harus
memulai lagi dengan struktur data yang berbeda [1].
Pohon Himpunan Saling Lepas
Pada struktur data ini, tiap himpunan
direpresentasikan dengan data struktur pohon
dimana tiap simpulnya memiliki referensi ke simpul
orang tuanya (parent node). Pohon himpunan saling
lepas ini semula ditemukan oleh Bernard A. Galler
dan Michael J. Fisher pada tahun 1964, meskipun
analisanya memakan waktu sampai bertahun-tahun
kemudian [10]. Untuk menggambarkan struktur data ini dengan
lebih jelas, akan dibahas penjelasannya dalam
bahasa C.
Di bawah ini adalah representasi dari simpulnya
dalam bahasa C, simpul tidak memiliki pointer ke
simpul anaknya namun memiliki pointer yang
menunjuk ke orang tuanya.
Algoritma 1. Simpul struktur data pohon himpunan
saling lepas
Ketika menggunakan struktur data ini dalam aplikasi
sebenarnya, terdapat pilihan cara lain yaitu
memasukan properti dari simpul pohon langsung
pada struktur yang merepresentasikan tiap elemen
(biasa disebut dengan internal storage) [10].
Operasi find cukup singkat, diberikan simpul yang
terdapat pada sebuah pohon, maka akar pohon dapat
dicari dengan mengikuti pointer orang tuanya, akar
dapat diasumsikan sebagai simpul yang
merepresentasikan seluruh partisi tersebut. Dalam
bahasa C, algoritma find dapat dituliskan sebagai
berikut:
Algoritma 2. Algoritma untuk mencari informasi
pada himpunan mana sebuah elemen
berada
Menggabungkan dua buah pohon menjadi sebuah
pohon juga merupakan hal yang mudah, kita hanya
perlu mencari akar dari salah satu pohon dan
menggabungkan akar tersebut pada akar pohon
berikutnya.
typedef struct
forest_node_simple_t {
void* value;
struct forest_node_simple_t*
parent;
} forest_node_simple;
forest_node_simple*
FindSimple(forest_node_simple* node) {
while (node->parent != NULL) {
node = node->parent;
}
return node;
}
6
#include
forest node simple
simple MakeSet operation
simple find operation
simple union operation
int main() {
int i1=1, i2=2, i3=3;
forest_node_simple* s1 = MakeSetSimple(&i1);
forest_node_simple* s2 = MakeSetSimple(&i2);
forest_node_simple* s3 = MakeSetSimple(&i3);
assert(FindSimple(s1) == s1);
UnionSimple(s1, s2);
assert(FindSimple(s1) == FindSimple(s2));
assert(FindSimple(s1) != FindSimple(s3));
UnionSimple(s2, s3);
assert(FindSimple(s1) == FindSimple(s2) &&
FindSimple(s1) == FindSimple(s3));
return 0;
}
Algoritma 3. Algoritma menggabungkan dua buah
himpunan menjadi sebuah himpunan
Pada akhirnya, MakeSet mengalokasikan tiap simpul
baru tanpa orang tua dan memasukkan nilai yang
diberikan pada simpul tersebut. Perlu diperhatikan
bahwa stdlib.h harus diinclude untuk menggunakan
fungsi malloc().
Algoritma 4. Algoritma membentuk himpunan baru
berisi hanya sebuah elemen
Di bawah ini merupakan contoh penggunaan dari
struktur data himpunan saling lepas seperti yang
telah dijelaskan di atas.
Algoritma 5. Contoh penggunaan (mesin) dari
struktur data himpunan saling lepas
Algoritma 6. Simpul pohon himpunan saling lepas
yang disempurnakan
Algoritma 7. Isi dari prosedur MakeSet yang telah
disempurnakan
5.3 Meningkatkan Efisiensifitas Struktur Data
Pohon Himpunan Saling Lepas
Meskipun sederhana, algoritma yang dijelaskan
sejauh ini memiliki masalah sama seperti masalah
yang dimiliki pohon pada umumnya, setelah
dilakukan banyak operasi penggabungan, ketinggian
pohon menjadi bertambah besar. Karena operasi find
memakan waktu sebanding dengan ketinggian
pohon, maka hal ini dapat mengarah pada
kompleksitas linier. Pada penmasangan akar sebuah
pohon pada akar pohon yang lain, idealnya kita
memasangkan pohon dengan ketinggian lebih
rendah pada pohon yang memiliki
ketinggian lebih tinggi. Sayangnya,
ketinggian merupakan hal yang
membutuhkan banyak kalkulasi
dalam perhitungannya, terlebih
tanpa pointer anak. Oleh karena itu,
kita akan menggunakan
perhitungan kasar melalui tinggi
kira-kira yang disebut dengan rank,
yang disimpan pada akar pohon
(Algoritma 6).
Rank dapat kita definisikan
sebagai berikut [10]:
• Prosedur MakeSet selalu
menghasilkan pohon dengan rank 0
(Algoritma 7).
• Jika rank(s) ¹ rank(t), maka
rank(Union(s, t)) merupakan rank
terbesar antara rank(s) dan rank(t).
Dalam kasus ini, kita memasangkan akar pohon
/* Given the root elements of two
trees, merge the trees into one tree
*/
void UnionSimple
(forest_node_simple* node1,
forest_node_simple* node2) {
node2->parent = node1;
/* or node1->parent = node2; */
}
forest_node_simple*
MakeSetSimple(void* value) {
forest_node_simple* node =
malloc(sizeof(forest_node_simple));
node->value = value;
node->parent = NULL;
return node;
}
typedef struct forest_node_t {
void* value;
struct forest_node_t* parent;
int rank;
} forest_node
<
forest_node* MakeSet(void* value);
<
forest_node* MakeSet(void* value) {
forest_node* node =
malloc(sizeof(forest_node));
node->value = value;
node->parent = NULL;
node->rank = 0;
return node;
}
7
dengan rank yang lebih kecil pada akar pohon
dengan rank yang lebih besar.
• Jika rank(s) = rank(t), maka rank(Union(s, t))
= rank(s) + 1 = rank(t) + 1 (Algoritma 8).
Tehnik seperti yang dijelaskan di atas biasa dikenal
dengan nama union find heuristic, menjamin
ketinggian logaritmik, yang tentu lebih mangkus.
Namun kita bahkan dapat lebih mengefiseienkannya
dengan tehnik yang dikenal dengan nama path
compression. Idenya adalah semua simpul yang
dilewati ketika men-traverse dari sebuah simpul
sampai ke akar berada pada pohon yang sama, oleh
karena itu, simpul-simpul tersebut akan lebih baik
apabila langsung menunjuk (pointing) pada akar
yang terdapat pada pohon yang sama. Kita membuat
kalang kedua dan memperbaharui pointer orang tua
mereka, mempercepat pencarian berikutnya yang
berkaitan dengan simpul yang bersangkutan dengan
dramatis (Algoritma 9) [10].
Algoritma 8. rank(Union(s, t)) = rank(s) + 1 =
rank(t) + 1
Algoritma 9. Pointer tiap simpul diperbaharui ketika
melakukan traversal
Algoritma 10. Struktur data himpunan saling lepas
secara keseluruhan
Masih terdapat beragam algoritma lain yang tidak
memerlukan kalang kedua, namun algoritma itu jauh
lebih rumit dan akan melenceng terlalu jauh dari
bahasan makalah ini.
Secara keseluruhan, struktur data di
atas dapat digambarkan seperti
pada Algoritma 10 di atas.
Di bawah ini diberikan contoh
penggunaan dari struktur data
pohon himpunan saling lepas yang
telah disempurnakan, kurang lebih
tidak jauh berbeda dengan struktur
data pohon himpunan saling lepas
yang belum disempurnakan:
Algoritma 11. Struktur data himpunan saling lepas
secara keseluruhan
<
void Union(forest_node* node1, forest_node* node2);
<
void Union(forest_node* node1, forest_node* node2) {
if (node1->rank > node2->rank) {
node2->parent = node1;
} else if (node2->rank > node1->rank) {
node1->parent = node2;
} else { /* they are equal */
node2->parent = node1;
node1->rank++;
}
}
<
forest_node* Find(forest_node* node);
<
forest_node* Find(forest_node* node) {
/* Find the root */
forest_node* root = node;
while (root->parent != NULL) {
root = root->parent;
}
/* Update the parent pointers */
forest_node* temp;
while (node->parent != NULL) {
temp = node->parent;
node->parent = temp;
node = temp;
}
return root;
}
<
#ifndef _UNION_FIND_H_
#define _UNION_FIND_H_
forest node
declarations
#endif /* #ifndef _UNION_FIND_H_ */
<
header files
#include "union_find.h"
MakeSet operation
union operation
find operation
<
#include
#include "union_find.h"
int main() {
int i1=1, i2=2, i3=3;
forest_node *s1=MakeSet(&i1),
*s2=MakeSet(&i2),
*s3=MakeSet(&i3);
assert(Find(s1) == s1);
Union(s1, s2);
assert(Find(s1) == Find(s2));
assert(Find(s1) != Find(s3));
Union(s2, s3);
assert(Find(s1) == Find(s2) &&
Find(s1) == Find(s3));
return 0;
}
8
6. APLIKASI STRUKTUR DATA
HIMPUNAN SALING LEPAS
6.1 Mengoptimalkan Algoritma Kruskal dalam
mencari Minimum Spanning Tree
Analisis membuktikan bahwa algoritma Kruskal
untuk Minimum Spanning Tree memiliki
kompleksitas O(m log m) dengan m adalah jumlah
sisi-sisinya. Algoritma ini membutuhkan cara yang
lebih cepat untuk mengetes apakah sisi yang
menghubungkan dua buah simpul berada pada
komponen terkoneksi yang sama.
Untuk mencari tahu jawabannya, kita membutuhkan
struktur data untuk memanipulasi himpunanhimpunan
yang dapat mengetes apakah dua buah
elemen berada pada himpunan yang sama dan
menggabungkan dua buah himpunan tersebut.
Masalah ini dapat diimplementasikan dengan operasi
union dan find.
Algoritma 11. Berikut di bawah ini adalah contoh
pseudocode dari implementasi union
find pada kruskal
Implementasi sederhana adalah dengan
merepresentasikan tiap himpunan dengan pohon,
dengan pointer dari simpul ke orang tuanya. Tiap
elemen terkandung dalam simpul, dan nama dari
himpunan adalah elemen dari akar.
Gambar 8. Find dan Union
6.2 Menelusuri Komponen yang Saling
Terkoneksi pada Graf Tak Berarah
Asumsikan kita memiliki graf yang tak berarah dan
ingin secara efisien menjawab pertanyaan yang
berkaitan dengan koneksi antar komponen dari graf
tersebut seperti [1]:
• Apakah dua buah simpul dalam graf yang sama
saling terkoneksi?
• Tampilkan semua simpul dalam graf sesuai
dengan komponennya (keterhubungannya)
• Berapa banyak komponen yang saling
terkoneksi?
Apabila grafnya statis (tidak berubah), maka kita
dapat dengan singkat menggunakan breadth-first
search untuk mengasosiasikan sebuah komponen
dengan tiap simpul. Bagaimanapun, jika kita ingin
menelusuri komponen-komponen dalam graf selama
menambah simpul dan sisi ke dalamnya, struktur
data himpunan saling lepas akan sangat efisien [1].
Asumsikan graf pada mulanya kosong. Setiap kali
kita menambahkan simpul, kita menggunakan
MakeSet untuk membuat himpunan yang
mengandung hanya simpul tersebut. Setiap kali kita
menambahkan sebuah sisi, kita menggunakan Union
untuk menggabungkan himpunan dari dua simpul
yang terhubung pada sisi tersebut. Sekarang, tiap
himpunan akan mengandung simpul dari komponen
yang saling terkoneksi, dan kita dapat menggunakan
Find untuk menentukan pada komponen terkoneksi
manakah sebuah simpul berada, atau apakah dua
buah simpul terdapat pada komponen yang sama [1].
Tehnik ini digunakan oleh Boost Graph Library,
untuk mengimplementasikan fungsi Incremental
Connected Components.
Perlu diperhatikan bahwa metoda ini tidak
memperbolehkan penghapusan sisi-sisi, meskipun
tanpa path compression atau rank heuristic, hal ini
tidaklah mudah, namun, saat ini metoda yang lebih
rumit telah didesain untuk dapat menangani masalah
ini [1].
6.3 Hubungan Ekivalensi dan Kelas Ekivalensi
Hubungan relasi pada himpunan A disebut relasi
ekivalensi apabila refleksif, simetris, dan transitif.
Operasi kongruen modulo n merupakan relasi
ekivalensi. Pernyataan a ~ b mengindikasikan bahwa
elemen a dan b berada pada himpunan yang sama.
Hal ini mengikuti aturan bahwa untuk membentuk
sebuah kelas ekivalensi dari sekelompok relasi
ekivalen kita harus melakukan langkah-langkah
seperti di bawah ini:
" x, MakeSet(x)
" relasi ekivalen (x, y)
if FindSet(x) ¹ FindSet(y)
Union(x, y)
Contoh yang sangat bagus untuk aplikasi ini adalah
relasi ekivalen kongruen modulo 5. Dalam masalah
ini, elemen {0, 5, 10, ...} berada pada kelas
Is si º sj
t = Find (si)
u = Find (sj)
Return (Is t=u?)
Make si º sj
t = d(si)
u = d(sj)
Union (t, u)
9
ekivalensi yang sama. Representasi umum dari kelas
adalah 0. Elemen 7 tidak berada pada himpunan
yang memiliki representasi 0.
Gambar di bawah adalah contoh lain dari relasi
ekivalen yang mengasumsikan pixel sebagai elemen.
Gambar 9. Relasi ekivalensi
Pada gambar di atas, A, B, dan C, adalah tiga kelas
ekivalensi. Sebuah pixel adalah elemen kelas apabila
pixel tersebut berada pada wilayah kelas tersebut.
Selanjutnya, dua buah pixel adalah ekivalen apabila
mereka berdua berada pada himpunan yang sama.
6.4 Pewarnaan Film Tua
Setiap frame pada film hitam putih yang tua terdiri
atas pixel-pixel, untuk mewarnai film ini, kita harus
mewarnai tiap pixel nya dengan aturan tertentu
sehingga tiap pixel yang ekivalen memiliki warna
yang sama. Pixel yang ekivalen adalah pixel yang
secara logika berada pada daerah yang sama, sebagai
contoh ketika seorang aktor mengenakan jaket. Pada
frame, pixel yang bertetangga dengan gray levels
yang sama atau sedikit berbeda dapat diasumsikan
ekivalen. Oleh karena itu, sebuah gray level frame
pixel mendefinisikan sekitar ribuan atau jutaan
hubungan ekivalensi antara pixel tetangganya. Untuk
memisahkan kelas ekivalensi dari hubungan ini,
metoda scan 4-pixel square digunakan untuk
menganalisis tetangga dari sebuah pixel x. Proses
scan ini akan memeriksa hubungan ekivalensi antar
pixel dari kiri atas sampai ke kanan bawah, baris
demi baris.
Gambar 10. Pewarnaan film tua
6.5 Menghitung Garis Pantai Sebuah Daratan
Ketika menghitung kontur permukaan 3-dimensi,
salah satu langkah pertama yang harus dilakukan
adalah menghitung “garis pantai”. Bayangkan kita
sedang men-sweeping sebuah model daratan,
menggunakan bidang yang sejajar dengan
“permukaan air laut”, mulai dari dasar daratan
hingga ke puncaknya. Kita akan mendapatkan
sekumpulan garis kontur seiring bergerak ke puncak
daratan tersebut, dilabelkan dengan solusi lokal yang
dimiliki tiap kontur (ketinggian). Pada akhirnya, kita
akan mendapatkan sebuah kontur yang mengandung
seluruh solusi lokal.
Gambar 11. Contoh kontur ketinggian
Ketika permukaan air laut meningkat sampai di atas
minimum lokal daratan, akan terbentuk sebuah
“danau”, yaitu garis kontur yang mengelilingi
minimum lokal. Masalah ini dapat diselesaikan
dengan operasi MakeSet.
Seiring dengan meningkatnya air laut,
permukaannya akan menyentuh sela gunung (saddle
point). Ketika itu, kita mengikuti tanjakan bukit dari
tiap sisinya sampai pada minimum lokal. Kita
menggunakan Find untuk menentukan kontur mana
yang mengelilingi dua buah solusi lokal ini, lalu
menggunakan Union untuk menggabungkan
keduanya. Pada akhirnya, seluruh kontur akan
tergabung menjadi satu, dan masalah ini selesai.
6.6 Mengklasifikasikan himpunan atom-atom
pada molekul atau fragmen
Dalam perhitungan kimia, tabrakan yang
menyangkut pecahan dari molekul berukuran besar
10
dapat disimulasikan dengan molecular dynamics.
Hasil dari tabrakan ini berupa data atom-atom
beserta posisinya. Pada analisisnya, algoritma unionfind
dapat digunakan untuk mengklasifikasikan
atom-atom ini dalam fragmen-fragmen. Tiap atom
diinisialisasi sebagai bagian dari fragmen dirinya
sendiri. Pada algoritma Find umumnya akan
mengandung pengecekan jarak antara sepasang
atom, meskipun kriteria lain seperti electronic
charge yang terjadi antara atom-atom dapat
digunakan. Union menggabungkan dua buah
fragmen bersama-sama. Pada akhirnya, ukuran dan
karakteristik tiap fragmen dapat dianalisis.
Tidak ada komentar:
Posting Komentar