Graf

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");

}