A.
PENGERTIAN GRAPH
Graph adalah himpunan noktah (simpul) di dalam
bidang dua dimensi yang dihubungkan dengan himpunan garis (sisi / edge). Graph
dapat digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara
objek-objek tersebut. Representasi visual dari graph adalah dengan menyatakan
objek sebagai noktah, bulatan atau titik (Vertex), sedangkan hubungan antara
objek dinyatakan dengan garis (Edge).
Suatu graph didefinisikan oleh himpunan verteks
dan himpunan sisi (edge). keterhubungan antara verteks. Biasanya untuk suatu
graph G digunakan notasi matematis. Verteks menyatakan entitas-entitas data dan
sisi menyatakan G = (V, E)
Dimana :
G = Graph
V = Simpul atau Vertex, atau Node, atau Titik
E = Busur atau Edge, atau arc
G = Graph
V = Simpul atau Vertex, atau Node, atau Titik
E = Busur atau Edge, atau arc
Graph
merupakan suatu cabang ilmu yang memiliki banyak terapan. Banyak sekali
struktur yang bisa direpresentasikan dengan graph, dan banyak masalah yang bisa
diselesaikan dengan bantuan graph. Seringkali graph digunakan untuk
merepresentasikan suaru jaringan. Misalkan jaringan jalan raya dimodelkan graph
dengan kota sebagai simpul (vertex/node) dan jalan yang menghubungkan setiap
kotanya sebagai sisi (edge) yang bobotnya (weight) adalah panjang dari jalan
tersebut.
Ada beberapa cara untuk menyimpan graph di
dalam sitem komputer. Struktur data bergantung pada struktur graph dan
algoritma yang digunakan untuk memmanipulasi graph. Secara teori salah satu
dari keduanya dapat dibedakan antara struktur list dan matriks, tetapi dalam
penggunaannya struktur terbaik yang sering digunakan adalah kombinasi keduanya.
1. Graph
tak berarah (undirected graph atau non-directed graph) :
Urutan simpul dalam sebuah busur tidak dipentingkan.
Misal busur e1 dapat disebut busur AB atau BA.
2. Graph
berarah (directed graph)
Urutan simpul mempunyai arti. Misal 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.
Gambar yang
menunjukkan suatu graph dengan 6 simpul dan 7 sisi.
Berdasarkan gambar di atas mungkin ada yang mengira bahwa
gambar tersebut mirip seperti struktur dari Tree. Ya memang benar gambar di
atas mirip seperti Tree tetapi tentu saja itu bukan Tree, itu adalah gambar
dari struktur Graph. Untuk lebih jelasnya akan sedikit dijelaskan mengenai
Tree.
Tree dalam pemrograman merupakan struktur data yang tidak
linear / non linear yang digunakan terutama untuk merepresentasikan hubungan
data yang bersifat hierarkis antara elemen-elemennya. Kumpulan elemen yang
salah satu elemennya disebut dengan root (akar) dan sisa elemen yang lain
disebut sebagai simpul (node/vertex) yang terpecah menjadi sejumlah himpunan
yang tidak saling berhubungan satu sama lain, yang disebut subtree / cabang.
Adapun Perbedaan Graph
dengan Tree sebagai berikut:
a. Pada Tree tidak terdapat Cycle
b. Pada Graph tidak memiliki root
B.
ISTILAH-ISTILAH DALAM GRAPH
Di sini akan dijelaskan
mengenai istilah-istilah yang ada kaitanya dengan graph, yaitu:
a. Vertex :
Himpunan node / titik pada sebuah graph.
b. Edge :
Himpunan garis yang menghubungkan tiap node / Vertex.
c. Adjacent : Dua
buah titik dikatakan berdekatan (adjacent) jika dua buah titik tersebut terhubung dengan sebuah sisi. Adalah Sisi e3 = v2v3 insident dengan titik v2
dan titik v3, tetapi sisi e3 = v2v3 tidak insident dengan titik v1 dan titik v4.
Titik v1 Adjacent dengan titik v2 dan v3, tetapi titi v1
tidak adjacent dengan titik v4.
d. Weight : Sebuah
graf G = (V, E) disebut sebuah graf berbobot (weight graph), apabila terdapat
sebuah fungsi bobot bernilai real W pada himpunan E, W : E € R, nilai W(e)
disebut bobot untuk sisi e, " e Î E. Graf berbobot tersebut dinyatakan
pula sebagai G=(V, E, W).
Graf berbobot G = (V,
E, W) dapat menyatakan :
·
Suatu sistem
penghubung udara, di mana
ü V = Himpunan kota-kota
ü E = Himpunan penerbangan langsung dari satu kota ke kota
lain.
ü W = Fungsi bernilai real pada E yang menyatakan jarak
atau ongkos atau waktu.
·
Suatu sitem jaringan
computer, di mana
ü V = Himpunan computer.
ü E = Himpunan jalur komunikasi langsung antar dua komputer.
ü W = Fungsi bernilai real pada E yang menyatakan jarak
atau ongkos atau waktu.
e. Path :
Walk dengan setiap vertex berbeda. Contoh, P = D5B4C2A Sebuah Walk (W)
didefinisikan sebagai urutan (tidak nol) Vertex & Edge. Diawali origin Vertex
dan diakhiri terminus Vertex. Dan setiap 2 Edge berurutan adalah series.
Contoh, W=A1B3C4B1A2.
f. Cycle :
Siklus ( Cycle ) atau Sirkuit ( Circuit ) Lintasan yang berawal dan berakhir pada simpul yang sama.
C.
REPRESENTASI GRAPH
Dalam pemrograman, agar data yang ada dalam graph dapat
diolah, maka graph harus dinyatakan dalam suatu struktur data yang dapat
mewakili graph tersebut. Dalam hal ini graph perlu direpresentasikan kedalam
bentuk array dan dimensi yang sering disebut matrix atau direpresentasikan
dalam bentuk linked list. Bentuk mana yang dipilih biasanya tergantung kepada
efisiensi dan kemudahan dalam membuat program. Berikut ini beberapa bentuk
representasi graph:
1.
Representasi Graph Dalam Bentuk Matrix
a. Adjacency Matrik Graph Tak Berarah
Matrik
yang digambarkan pada gambar 1b merupakan representasi dalam bentuk Adjacency
Matrik dari graf yang digambarkan pada gambar 1a. Beberapa hal yang dapat
dilihat atau dapat diterangkan pada Adjacency Matrik tersebut adalah sebagai
berikut :
o Matrik yang terbentuk adalah matrik bujur sangkar n x n,
dimana n = jumlah simpul yang ada dalam graf tersebut. Matrik ini menyatakan
hubungan antara simpul satu dengan simpul lainnya.
o Matrik yang terbentuk adalah matrik simetris dengan sumbu
simetris adalah diagonal dari titik kiri atas ke titik kanan bawah.
o Data yang tedapat baik dalam baris maupun kolom, dapat
menyatakan degree sebuah simpul. Contoh : baik pada baris D maupun kolom D
jumlah angka 1 nya adalah 3 buah, dimana jumlah ini menyatakan degree simpul D.
b. Adjacency Matrik Graf Berarah
Matrik
yang digambarkan pada gambar 2b merupakan representasi dalam bentuk Adjacency
Matrik dari graf yang digambarkan pada gambar 2a. Beberapa hal yang dapat
dilihat atau dapat diterangkan pada Adjacency Matrik tersebut adalah sebagai
berikut :
o Matrik yang terbentuk adalah matrik bujur sangkar n x n,
dimana n = jumlah simpul yang ada dalam graf tersebut. Matrik ini menyatakan
hubungan antara simpul satu dengan simpul lainnya.
o Matrik yang terbentuk mungkin simetris mungkin juga tidak
simetris. Menjadi simetris bila hubungan antara dua buah simpul (v1 dan v2)
terdapat busur dari v1 ke v2 dan juga sebaliknya.
o Hal pokok yang dinyatakan oleh matrik ini adalah : busur
yang ’keluar’ dari suatu simpul. Dengan demikian, data yang terdapat dalam
suatu baris, dapat menyatakan outdegree simpul yang bersangkutan.
Contoh : Jumlah elemen yang
nilainya = 1 pada baris B ada 3 elemen,ini menyatakan jumlah outdegree simpul B
adalah 3 buah.
o Data yang terdapat dalam suatu kolom, dapat menyatakan
indegree simpul bersangkutan.
Contoh : Jumlah elemen yang
nilainya 1 pada kolom B ada 2 elemen, ini menyatakan indegree simpul B adalah 2
buah.
c. Adjacency Matrik Graf Berbobot Tak Berarah
Nilai
yang ada dalam tiap elemen matrik, menyatakan bobot busur yang menghubungkan
dua buah simpul yang bersangkutan. Untuk dua buah simpul yang tidak berhubungan
langsung oleh sebuah busur, maka dianggap dihubungkan oleh sebuah busur yang
nilai bobotnya tidak terhingga. Dalam pemograman, karena keperluan algoritma,
maka dari total bobot seluruh busur yang ada atau yang mungkin ada.
Contoh:
pada gambar 3a simpul A dan C tidak berhubungan langsung melalui sebuah busur,
maka untuk elemen matrik yang bersangkutan diisi dengan nilai 999 karena nilai
999 dalam kasus ini cukup mewakili nilai tidak terhingga.
2.
Representasi Graph Dalam Bentuk Linked List
a. Adjacency List
Bila ingin
direpresentasikan dalambentuk linked list, dapat diilustrasikan secara
sederhana seperti gamabar 4b. Dari ilustrasi sederhana tersebut terlihat ada 5
buah simpul A,B,C,D,dan E yang dibariskan dari atas kebawah seperti pada gambar
4a. Kemudian dari masing-masing simpul ’keluar’ pointer kearah kanan yang
menunjuk simpul-simpul lain. Salah satu contoh, yang dapat dilihat pada gambar
4b dimana A menunjuk simpul B dan simpul D.
Dalam Adjacency List,
kita perlu membedakan antara simpul-vertex dan simpul-edge. Simpul-vertex untuk
menyatakan simpul atau vertex, dan simpul-edge untuk menyatakan hubungan antar
simpul yang biasa disebut busur. Struktur keduanya bisa sama, bisa juga tidak
sama,tergantung kebutuhan.Untuk memudahkan pembuatan program, struktur kedua
macam simpul dibuat sama seperti yang digambarkan pada gambar 5c. Yang
membedakan antara simpul-vertex dan simpul-edge, adalah anggapan terhadap
simpul tersebut. Dalam contoh ini, terlihat struktur simpul dibuat terdiri dari
3 elemen. Satu elemen untuk INFO, dua elemen untuk pointer.pointer kiri (left)
dan pointer kanan (right).
Struct
tipes
|
{
|
Struct tipes
*Left;
|
int INFO;
|
Struct tipes
*Right;
|
} ;
|
Struct tipes
*First,*Pvertex,*Pedge;
|
- · Bila simpul dianggap sebagai simpul-vertex, maka :
Pointer
left digunakan untuk menunjuk simpul berikutnya dalam untaian simpul-simpul
yang ada,atau diisi NULL bila sudah tidak ada simpul yang pelu
ditunjuk.Sedangkan pointer Right digunakan untuk menunjuk simpul edge yang
pertama.
- · Bila Simpul dianggap sebagai simpul-edge, maka :
Pointer
left digunakan untuk menunjuk simpul-vertex ‘tujuan’ yang berhubungan dengan
simpul-vertex ‘asal’ dan pointer right digunakan untuk menunjuk simpul-edge
berkiutnya bila masih ada, atau diisi NULL bila tak ada lagi simpul-busur yang
ditunjuk.
D.
CONTOH REPRESENTASI GRAPH DALAM BAHASA C
typedef struct vertex
|
{
|
char
nama[100];
|
float
x, y;
|
float
status;
|
float
jarak;
|
struct
vertex *next,*connector;
|
};
|
typedef
struct vertex *pvertex;
|
typedef
struct edge
|
{
|
float
jarak;
|
char
titik1[100];
|
char
titik2[100];
|
edge
* next;
|
};
|
typedef
struct edge * garis;
|
garis
awalga = NULL, akhirga= NULL;
|
pvertex
makeptree (float x, float y, char nama[])
|
{
|
pvertex
baru;
|
baru=(pvertex)malloc(sizeof(struct
vertex));
|
baru->x=x;
|
baru->y=y;
|
baru->status=0;
|
baru->next=NULL;
|
baru->connector=NULL;
|
strcpy(baru->nama,nama);
|
}
|
void
makevertex (pvertex *vertex,float x,float y,char nama[])
|
{
|
pvertex
p , q ;
|
p
= makeptree(x,y,nama);
|
q
= *vertex;
|
if(q
== NULL)
|
*vertex
= p ;
|
else
|
{
|
for(;q->next;q=q->next)
|
{
|
}
|
q->next
= p;
|
}
|
}
|
void
makeedge(garis * awalga, garis * akhirga, char titik1[], char titik2[], float
jarak)
|
{
|
garis
baru;
|
baru=(garis)malloc(sizeof(edge));
|
baru->jarak=jarak;
|
strcpy(baru->titik1,titik1);
|
strcpy(baru->titik2,
titik2);
|
if(*awalga==NULL)
|
{
|
*awalga=baru;
|
*akhirga=baru;
|
}
|
else
|
{
|
(*akhirga)->next=baru;
|
(*akhirga)=baru;
|
}
|
}
|
void
cek(pvertex vertex, int jumlah)
|
{
|
pvertex
awal,p,q;
|
float
jarak;
|
float
min ;
|
float
temp;
|
awal
= vertex;
|
p
= awal;
|
for(int
i=0;i
|
{
|
min
= 999;
|
p->status
=1;
|
for(q=awal->next;q!=NULL;q=q->next)
|
{
|
if(q->status!=1)
|
{
|
jarak=(((p->x)-(q->x))*((p->x)-(q->x)))+(((p->y)-(q->y))*((p->y)-(q->y)));
|
jarak=sqrt(jarak);
|
if
(min>jarak)
|
{
|
min
= jarak;
|
p->jarak
= min;
|
p->connector
= q;
|
}
|
makeedge(&awalga,&akhirga,p->nama,q->nama,p->jarak);
|
}
|
}
|
p
= p->connector;
|
}
|
temp=(((p->x)-(awal->x))*((p->x)-(awal->x)))+(((p->y)-(awal->y))*((p->y)-(awal->y)));
|
p->jarak
= sqrt(temp);
|
p->connector
= awal;
|
}
|
void
displayedge(pvertex vertex,int jumlah)
|
{
|
pvertex
list = vertex;
|
float
tot;
|
tot
+= vertex->jarak;
|
printf("\n\t%s
ke %s\n", list->nama,list->connector->nama);
|
list
= list->connector;
|
for(int
a=0; a
|
{
|
printf("\n\t%s
ke %s\n", list->nama,list->connector->nama);
|
tot
+= list->jarak;
|
list
= list->connector;
|
}
|
printf("\n");
|
}
|
E.
KAITAN SHORHEST PATH PROBLEM DALAM GRAPH
Lintasan terpendek
merupakan salah satu dari masalah yang dapat diselesaikan dengan graf. Jika
diberikan sebuah graf berbobot, masalah lintasan terpendek adalah bagaimana
kita mencari sebuah jalur pada graf yang meminimalkan jumlah bobot sisi
pembentuk jalur tersebut.
Terdapat beberapa macam
persoalan lintasan terpendek antara lain:
- Lintasan terpendek antara dua buah simpul tertentu (a pair shortets path).
- Lintasan terpendek antara semua pasangan simpul (all pairs shortest path).
- Lintasan terpendek dari simpul tertentu ke semua simpul yang lain (single-source shoertest path).
- Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu (intermediate shortest path).
Jalur terpendek adalah suatu jaringan pengarahan
perjalanan dimana sesorang pengarah jalan ingin menentukan jalur terpendek
antara dua kota, berdasarkan beberapa jalur alternatif yang tersedia, dimana titik
tujuan hanya satu. Gambar 2.6 menunjukkan suatu graf ABCDEFG yang berarah dan
tidak berbobot.
1.
Pathing Algorhitm
Pathing
Algorithm adalah sebuah algoritma yang digunakan untuk mencari suatu solusi
dalam menentukan lintasan terpendek dari suatu graf. Saat ini terdapat banyak
sekali algoritma yang digunakan untuk menyelesaikan persoalan lintasan
terpendek diantaranya Algoritma Djikstra ( djikstra algorithm ) dan Algoritma
Bellman-Ford ( bellman-ford algorithm ).
2.
Algoritma Djikstra
Algoritma
Dijkstra, dinamai menurut penemunya, Edsger Dijkstra, adalah algoritma dengan
prinsip greedy yang memecahkan masalah lintasan terpendek untuk sebuah graf
berarah dengan bobot sisi yang tidak negatif.
Algoritma Dijkstra merupakan
salah satu varian bentuk algoritma populer dalam pemecahan persoalan yang
terkait dengan masalah optimasi. Sifatnya sederhana dan lempang
(straightforward). Sesuai dengan arti greedy yang secara harafiah berarti tamak
atau rakus - namun tidak dalam konteks negatif -, algoritma greedy ini hanya
memikirkan solusi terbaik yang akan diambil pada setiap langkah tanpa
memikirkan konsekuensi ke depan.
Input
algoritma ini adalah sebuah graf berarah yang berbobot (weighted directed graph)
G dan sebuah sumber vertex s dalam G dan V adalah himpunan semua vertices dalam
graph G.
Setiap
sisi dari graf ini adalah pasangan vertices (u,v) yang melambangkan hubungan
dari vertex u ke vertex v. Himpunan semua tepi disebut E. Bobot (weights) dari
semua sisi dihitung dengan fungsi : w: E → [0, ∞), jadi w(u,v) adalah jarak
tak-negatif dari vertex u ke vertex v. Ongkos (cost) dari sebuah sisi dapat
dianggap sebagai jarak antara dua vertex, yaitu jumlah jarak semua sisi dalam
jalur tersebut. Untuk sepasang vertex s dan t dalam V, algoritma ini menghitung
jarak terpendek dari s ke t.
3.
Algoritma Bellman-Ford
Algoritma
Bellman-Ford menghitung jarak terpendek (dari satu sumber) pada sebuah digraf
berbobot. Maksudnya dari satu sumber ialah bahwa ia menghitung semua jarak
terpendek yang berawal dari satu titik node. Algoritma Dijkstra dapat lebih
cepat mencari hal yang sama dengan syarat tidak ada sisi (edge) yang berbobot
negatif. Maka Algoritma Bellman-Ford hanya digunakan jika ada sisi berbobot negatif.
Algoritma Bellman-Ford
menggunakan waktu sebesar O(V.E), di mana V dan E adalah menyatakan banyaknya
sisi dan titik. Dalam konteks ini, bobot ekivalen dengan jarak dalam sebuah
sisi.
Tidak ada komentar:
Posting Komentar