Graf adalah kumpulan noktah (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 tersebut. Representasi visual dari graph adalah dengan
menyatakan objek sebagai noktah, bulatan atau titik (Vertex), sedangkan
hubungan antara objek dinyatakan dengan garis (Edge).
G = (V, E)
Dimana
G = Graph
V = Simpul atau Vertex, atau Node,
atau Titik
E = Busur atau Edge, atau arc
Graf merupakan suatu cabang ilmu yang
memiliki banyak terapan. Banyak sekali struktur yang bisa direpresentasikan
dengan graf, dan banyak masalah yang bisa diselesaikan dengan bantuan graf.
Seringkali graf digunakan untuk merepresentasikan suaru jaringan. Misalkan
jaringan jalan raya dimodelkan graf 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.
• 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
• Graph berarah (directed graph) :
• Urutan simpul mempunyai arti. Misal
busur AB adalah e1 sedangkan busur BA adalah e8.
• 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.
2. Istilah-istilah
dalam graf
Kemudian terdapat istilah-istilah yang
berkaitan dengan graph yaitu:
a. Vertex
Adalah himpunan node
/ titik pada sebuah graph.
b. Edge
Adalah himpunan garis
yang menghubungkan tiap node / vertex.
c. Adjacent
Adalah 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 titik v3,
tetapi titik v1 tidak adjacent dengan
titik v4.
d. Weight
Adalah 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 perhubungan 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 sistem jaringan komputer, di mana
· V = himpunan komputer
· E = himpunan jalur komunikasi langsung
antar dua komputer
· W = fungsi bernilai real pada E yang
menyatakan jarak atau ongkos atau waktu
e. Path
Adalah Walk dengan setiap vertex
berbeda. Contoh, P = D5B4C2A Sebuah walk
(W) didefinisikan sebagai urutan (tdk nol) vertex & edge. Diawali origin
vertex dan diakhiri terminus vertex. Dan setiap 2 edge berurutan adalah
series. Contoh, W = A1B3C4B1A2.
f. Cycle
Adalah Siklus ( Cycle ) atau Sirkuit ( Circuit
) Lintasan yang berawal dan berakhir pada simpul yang sama
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");
}
