Materi Struktur Organisasi Data Graph dan Tree
Halo guyss,, balik lagi nih sama aku, aku mau share materi seperti biasa. Materi yang mau aku share adalah tentang Graph dan Tree, disimak baik-baik yaa teman-teman semua...
GRAPH dan TREE
Pengertian Graf dan Tree serta Perbedaannya
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 darigraph 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.
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
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 = v2v3tidak insident dengan titik v1 dan titik v4.
Titik v1 adjacent dengan titik v2 dan titik v3, tetapi titik v1 tidakadjacent 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 diakhiriterminus 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
Representasi Graf
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
Adjacency Matrik Graf 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 :
1. 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.
2. Matrik yang terbentuk adalah matrik simetris dengan sumbu simetris adalah diagonal dari titik kiri atas ke titik kanan bawah.
3. 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.
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 :
1. 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.
2. 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.
3. 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.
4. 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.
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 999karena nilai 999 dalam kasus ini cukup mewakili nilai tidak terhingga.
2. Representasi graf dalam bentuk Linked List
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 menunjuksimpul-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 disebutbusur. 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 peluditunjuk.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.
3. 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");
}
4. Kaitan Shorhest Path Problem dalam Graf
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.
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 ).
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 sdalam G dan V adalah himpunan semua vertices dalam graphG.
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.
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.
5. Algoritma tentang TSP,CPP,Coloring Graph dan MST
a. Travelling Salesman Problem
Traveling Salesman Problem (TSP) pertama kali diperkenalkan oleh Rand pada tahun 1948, reputasi Rand membuat TSP dikenal dengan baik dan menjadi masalah yang populer. TSP merupakan persoalan yang mempunyai konsep sederhana dan mudah dipahami. Permasalahan TSP (Traveling Salesman Problem ) adalah permasalahan dimana seorang salesman harus mengunjungi semua kota dimana tiap kota hanya dikunjungi sekali, dan dia harus mulai dari dan kembali ke kota asal. Pada TSP, optimasi yang diinginkan agar ditemukan rute perjalanan terpendekuntuk melewati sejumlah kota dengan jalur tertentu sehingga setiap kota hanya terlewati satu kali dan perjalanan diakhiri dengan kembali ke kota semula. Pendekatan dengan menggunakan Jaringan SarafKohonen Self Organizing memberikan solusi atau penyelesaian dalam perhitungan waktu yang lebih singkat dibandingkan dengan sejumlah algoritma lain yang diterapkan pada komputer dalam bentuk program. The Travelling Salesman Problem adalah sebuah bentuk permasalahan riil yang mempunyai bentuk permodelan weight hamiltonian cycle. Dalam permodelan ini, seorang salesman dalam pekerjaannya diharuskan untuk mengunjungi pelanggannya yang berada pada beberapa kota yang tiap-tiap kotaknya mempunyai jarak berbeda-beda. Untuk mengefisiensikan beban kerjanya, salesman tersebut, dia harus merancang sebuah rute perjalanan dengan waktu minimal. Selain itu, demi efisiensi biaya dan waktu, salesman tersebut berusaha agar dia tidak melewati satu kota yang sama dua kali. Berikut ini adalah gambar permodelan dari problem travelling salesman problem.
Berikut adalah Algoritma untuk mencari TSP:
· Mula-mula dimulai dari U cari nilai Edge yang terkecil dan masih belum dilewati dalam rute. Maka dipilih Edge U-Y yang mempunyai nilai 2. Kemudian tandai titik U dan Y agar tidak dilewati lagi.
· Kemudian dari titik Y pilih nilai edge terkecil dimana vertex tujuannya belum ditandai/tidak menimbulkan cycle. Dalam hal ini dipilih edge Y-Z, kemudian tandai vertex Z.
· Sama dengan step 1 dan step 2. Dalam hal ini, dipilih edge Z-W sebagai rute.
· Pada vertex W, Nilai edge yang terkecil ada pada edge U-W, tetapi karena edge ini menimbulkan cycle, maka edge ini tidak dapat digunakan, demikian halnya dengan edge W-Y, sehingga yang dipilih sebagai rute adalah Edge W-X
· Karena semua vertex sudah terhubung dan tidak ada cycle, maka path pada gambar 5 adalah solusi dari problem untuk titik U
· Jadi, yang akan dilalui adalah Path : U – Y – Z – W – X – VPanjang path : 142
b. Chinese Postman Problem
· Masalah Chinese Postman Problem pertama kali diformulasikan dalam bentuk masalah untuk menentukan sisi terpendek bagi seorang tukang pos untuk melewati semua jalan yang ada dan kembali ke tempat semula. Masalah ini dikemukakan oleh Kwan Mei-Ko di awal 1960-an dalam jurnal Chinese Mathematics. Dalam istilah graf definisi CPP adalah mencari lintasan pada suatu graf berbobot yang terhubung yang melewati semua sisi (minimal sekali) dengan jumlah bobot minimum dari suatu simpul kembali ke simpul awal. Postman yang mengantarkan surat di suatu daerah tertentu berkeinginan untuk mengetahui circuit yang menjelahi setiap jalan (dalam hal ini mengikuti arah, jika hanya ada 1 jalur), berawal dan berakhir di kantor. Permasalahan ini adalah permasalahan teori graf, yaitu :
- jalan adalah directed edge atau busur berarah
- persimpangan jalan adalah vertex atau simpul
· Postman membutuhkan Chinese Postman Tour (CPT) yang paling pendek, dengan pengulangan kunjungan jalan seminimal mungkin. Biaya CPT didefinisikan sebagai jumlah total berat/weight edge atau total jarak yang dibutuhkan. CPT dikatakan optimal jika CPT tersebut memiliki biaya minimal. Jika ada beberapa berat/weight edge yang negatif, maka CPT yang optimal tidak dapat didefinisikan. Hal ini disebabkan karena postman akan mengulang sampai tidak terhingga untuk mengunjungi jalan tersebut untuk mendapatkan biaya lebih rendah.
· Sebelum memulai perjalanannya tukang pos harus pergi ke kantor pos untuk mengambil surat. Barulah dia pergi mengantarkan surat dengan menelusuri setiap jalan pada daerahnya dan akhirnya ia harus kembali ke kantor pos untuk memgembalikan semua suarat yang tidak terkirim. Untuk menghemat energi Tukang pos ingin menelusuri daerahnya dengan dengan sesedikit mungkin jarak yang ditempuh.
Pada intinya masalah tukang pos adalah bagaimana menelusuri semua jalan yang ada pada rutenya dan kembali ke asal dengan jarak tempuh yang paling sedikit. Pada kenyataannya tidak hanya tukang pos saja yang menghadapi masalah ini, banyak profesi lain yang menghadapi masalah serupa seperti polisi ingin menempuh jalur yang paling efisien dalam berpatroli, tukang jualan bakso ingin melewati setiap rumah dengan efisien , petani ingin menngetahui jalur terbaik dalam menebarkan benih, dan lain-lain. Masalah ini muncul pada sebuah jurnal di cina yang di sebut sebagai “postman problem” dan sering kali disebut “Chinese postman problem”.
· Postman problem dapat digambarkan sebagai graf, dimana tiap sisi adalah jalan dan tiap simpul adalah persimpangan dari jalan-jalan. Postman problem adalah permasalahan (problem) untuk menemukan jalur terpendek untuk melalui tiap sisi graf setidaknya sekali dan kembali lagi ke simpul awal.Berikut ini adalah gambar permodelan dari problemChinese Postman Problem.
Untuk menyelesaikan Chinese Postman Problem yang ada di gambar atas menggunakan Algoritma Fleury maka kita harus membentuk Eulerian Pathnya dahulu.:
· Graf berikut tidak memiliki sirkuit Euler, karena ada dua simpul berderajat ganjil (U dan V). Kita perlu mencari jalur terpendek antara U dan V, beberapa jalur yang ada antara lain: U>X>V : 7
· Graf berikut tidak memiliki sirkuit Euler, karena ada dua simpul berderajat ganjil (U dan V). Kita perlu mencari jalur terpendek antara U dan V, beberapa jalur yang ada antara lain: U>X>V : 7, U>Y>X>Z>V : 12
· Graf berikut tidak memiliki sirkuit Euler, karena ada dua simpul berderajat ganjil (U dan V). Kita perlu mencari jalur terpendek antara U dan V, beberapa jalur yang ada antara lain: U>X>V : 7, U>Y>X>Z>V : 12, U>Y>Z>V : 9
· Graf berikut tidak memiliki sirkuit Euler, karena ada dua simpul berderajat ganjil (U dan V). Kita perlu mencari jalur terpendek antara U dan V, beberapa jalur yang ada antara lain: U>X>V : 7, U>Y>X>Z>V : 12, U>Y>Z>V : 9, U>Y>W>Z>V : 10
· Graf berikut tidak memiliki sirkuit Euler, karena ada dua simpul berderajat ganjil (U dan V). Kita perlu mencari jalur terpendek antara U dan V, beberapa jalur yang ada antara lain: U>X>V : 7, U>Y>X>Z>V : 12, U>Y>Z>V : 9, U>Y>W>Z>V : 10, U>W>V : 7dan U>X>Y>W>V : 6
· Dan seterusnya, yang terpendek adalah 6(U>X>Y>W>V), Jalur terpendek di-gandakan agar menjadi graph genap.
Setelah di jalankan hasil reduce nya adalah seperti di gambar dan U>X>Y>W>V tetap ada garis nya karena tadi telah di gandakan yang dikarenakan U dan V berderajat ganjil serta mencari jarak terpendek untuk kembali titik awal.
Jadi ada dua jalur yang akan dilewati dan untuk kembali ke titik awal yaitu :
Pertama
U>Y>X>Z>W>Y>Z>V>W>Y>X>U
Kedua
U>Y>W>Z>X>Y>Z>V>W>Y>X>U
Panjang optimum adalah 37
c. Coloring Graph
Coloring adalah pewarnaan suatu graf. Ada dua macam cara mewarnai suatu graf yaitu coloring vertex (pewarnaan titik) dancoloring edge (pewarnaan garis). Coloring vertex adalah cara pemberian warna untuk setiap titik pada suatu graf sedemikian rupa sehingga setiap titik yang adjacent ( dihubungkan oleh garis/edge yang sama) diwarnai dengan warna yang berbeda. Sedangkan coloring edge adalah cara pemberian warna pada garis sedemikian rupa sehingga setiap garis yang bertumpuan pada titik yang sama diberi warna yang berbeda. cara pemberian warna tidak memiliki aturan tertentu, hanya harus seminimal mungkin.
Untuk pembuatan jadwal ini akan digunakan coloring vertex. Dari suatu jadwal yang diinputkan, mula-mula akan dipetakan menjadi suatu graf terlebih dahulu. Proses coloring dilakukan pada graf yang terbentuk. Pemetaan dilakukan dengan mengasumsikan bahwa setiap jadwal adalah sebuah vertex dan urutan jadwal atau dua jadwal yang tidak bisa diadakan bersamaan dipetakan dengan membuat edge antara dua titik tersebut. Untuk kapasitas ruang yang ada akan dimodelkan dengan batasan jumlah warna sama yang bisa digunakan untuk mewarnai vertex.
Setelah selesai melakukan proses coloring, setiap vertex pada graf hasil akan memiliki warna yang berbeda-beda. Dari warna-warna tersebut akan diketahui bahwa titik dengan warna yang sama bisa dijadwalkan bersamaan sedangkan untuk titik dengan warna yang berlainan, harus dijadwalkan berbeda. Jumlah yang digunakan menunjukkan banyaknya jadwal yang harus dibuat untuk bisa melakukan penjadwalan.
Intinya adalah bahwa antara dua buah vertex yang dihubungkan dengan sebuah edge, warnanya harus berbeda agar jadwal tidak bertabrakan.
6. Implementasi Graph dalam bahasa C
a. Contoh Implementasi Graph untuk membangun jaringan kereta api yang efisien
Untuk membangun jaringan kereta api yang efisien ini dapat kita implementasi ke dalam bahasa C dengan menggunakan algoritma prims. Algoritma nya sebagai berikut:
· Awal nya tentukan berapa kota yang ingin untuk membangun jaringan kereta api agar ditiap kota terdapat jalur kereta api tersebut.
· Setelah itu hitung jarak terpendek dari satu kota ke kota berikutnya dengan menggunakan rumus jarak=((X1-X2)2+(Y1-Y2)2)
· Setelah menghitung maka dapat kita tentukan jarak-jarak yang terpendek dan dapat kita hubungan dengan catatan semua kota harus terhubung dan memiliki jalur kereta api tersebut.
Source Code :
typedef struct vertex
{
bool flag;
char nama[1000];
float x;
float y;
struct vertex *next;
struct edge *list;
};
typedef struct vertex *pvertex;
typedef struct edge
{
bool flag;
bool flag2;
float length;
struct edge *next;
struct vertex *link;
};
typedef struct edge *pedge;
pvertex make_vertex(char nama[],float x,float y)
{
pvertex p;
p = (pvertex) malloc(sizeof(struct vertex));
p->next = NULL;
p->list = NULL;
p->flag = 0;
p->x = x;
p->y = y;
strcpy(p->nama,nama);
return p;
}
pedge meke_edge(float length)
{
pedge p;
p = (pedge) malloc(sizeof(struct edge));
p->next = NULL;
p->link = NULL;
p->flag = 0;
p->flag2 = 0;
p->length=length;
return p;
}
void insert_vertex(pvertex *graph,float x,float y,pvertex *temp,char nama[])
{
pvertex news;
news = make_vertex(nama,x,y);
if(*graph==NULL)
{
*graph = news;
*temp = *graph;
}
else
{
(*temp)->next = news;
(*temp) = (*temp)->next;
}
}
void insert_edge(pvertex *temp,pvertex *temp2,pedge *edge,float length)
{
pedge news2;
news2 = meke_edge(length);
news2->link = *temp2;
if((*temp)->list==NULL)
{
(*temp)->list = news2;
*edge = news2;
}
else
{
(*edge)->next = news2;
(*edge) = (*edge)->next;
}
}
void cek(pvertex graph,int jumlah,char nama[])
{
pvertex temp,temp2;
pedge edge;
float length;
temp = graph;
for(int i = 0; i
{
strcpy(nama, temp->nama);
temp2 = graph;
for(int j = 0; j
{
length = ((temp->x - temp2->x)*(temp->x - temp2->x)+(temp->y - temp2->y)*(temp->y - temp2->y));
length = sqrt(length);
if(strcmp(temp2->nama,nama)!= 0)
{
insert_edge(&temp,&temp2,&edge,length);
}
temp2 = temp2->next;
}
temp = temp->next;
}
}
void proses(pvertex graph,int jumlah)
{
pvertex temp,temp_vertex,con_vex;
pedge edge,minedge;
float min;
graph->flag = 1;
for (int i = 1;i <>
{
min = 999;
for(temp = graph; temp != NULL; temp = temp->next)
{
if(temp->flag == 1)
{
for(edge=temp->list; edge != NULL; edge = edge->next)
{
if(edge->length <>
{
if(edge->flag==0)
{
if(edge->link->flag==0)
{
minedge = edge;
min = edge->length;
con_vex = edge->link;
temp_vertex = temp;
}
}
}
}
}
}
minedge->flag = 1;
con_vex->flag = 1;
for(edge = con_vex->list; edge->link != temp_vertex; edge = edge->next)
{
}
edge->flag = 1;
}
}
void view(pvertex graph)
{
pvertex temp;
pedge edge,news2;
float total;
total = 0;
printf("\n");
for(temp = graph; temp != NULL; temp = temp->next)
{
for(edge = temp->list; edge != NULL; edge = edge->next)
{
if(edge->flag == 1)
{
if(edge->flag2 == 0)
{
edge->flag2 = 1;
for(news2 = edge->link->list; news2->link != temp; news2 = news2->next)
{
}
news2->flag2 = 1;
total +=edge->length;
printf("%s ke %s Panjangnya: %.3f\n",temp->nama,edge->link->nama,edge->length);
}
}
}
}
printf("\nTotal Jaraknya adalah : %.3f\n",total);
}
b. Contoh Implementasi Graph untuk mencari rute terpendek yang dapat mengunjungi semua kota
Jadi untuk mencari rute terpendek yang dapat mengunjungi semua kota seperti gambar diatas dapat kita menggunakan algoritma TSP.
Source Code
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 panjangnya : %.2f\n", list->nama,list->connector->nama,list->jarak);
list = list->connector;
for(int a=0; a
{
printf("\n\t%s ke %s panjangnya : %.2f\n", list->nama,list->connector->nama,list->jarak);
tot += list->jarak;
list = list->connector;
}
printf("\n");
}
void view(pvertex vertex)
{
pvertex p;
float total=0 ;
p = vertex;
printf("\nYang akan dilewati adalah>> ");
printf("%2s ", p->nama);
total=total+vertex->jarak;
for(p=p->connector;strcmp(p->nama,vertex->nama);p = p->connector)
{
printf("%2s ", p->nama);
total=total+p->jarak;
}
printf("%2s ",p->nama);
printf("\nTotal jarak nya>> %.2f",total);
}
0 komentar :
Posting Komentar