Graf dan Pohon Dalam Algoritma Pemrograman C++

POLITEKNIK NEGERI TANAH LAUT
GRAF DAN POHON

TI Politala Algoritma Pemrograman 2B

Pengertian Graf
G membentuk suatu graf jika terdapat pasangan himpunan (V(G), E(G)), dimana V(G) (simpul pada graf G) tidak kosong dan E(G) (rusuk pada graf G). Jika v dan w adalah sepasang simpul yang berbeda di G, melambangkan rusuk di G dan jika e=vw adalah rusuk di maka:

a. v dan w berikatan (adjacent) di G

b. Rusuk e hadir (joining) simpul v dan w di G

c. v dan w adalah simpul ujung rusuk di e

d. Rusuk e hadir (incident) di simpul v dan w atau sebaliknya dikatakan simpul v dan w hadir pada rusuk e.

Menutut Rosen berdasarkan ada tidaknya bobot, graf dikelompokkan menjadi dua jenis yaitu graf berbobot dan graf tak-berbobot.

Jenis-Jenis Graf

a. Berdasarkan ada tidaknya loop atau rusuk ganda pada suatu graf, maka graf digolongkan menjadi dua jenis, yaitu:
1) Graf sederhana (simple graph) yaitu graf yang tidak mengandung loop maupun rusuk ganda. Gambar G1 di bawah ini adalah contoh graf sederhana.

(Gambar 1 Graf Sederhana G1)

2) Graf tak-sederhana (unsimple graph) yaitu graf yang mengandung loop atau rusuk ganda. Gambar Graf G2 di bawah ini adalah contoh graf tidak sederhana yang mengandung rusuk ganda dan Graf G3 adalah contoh graf tidak sederhana yang mengandung loop.

(Gambar 2 Graf Tak Sederhana G2)

(Gambar 2 Graf Tak Sederhana G3)

b. Berdasarkan jumlah titik pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:
1) Graf berhingga (limited graph) adalah graf yang jumlah titiknya n berhingga.
2) Graf tak berhingga (unlimited graph) adalah graf yang jumlah titiknya n tidak berhingga banyaknya.
c. Berdasarkan orientasi arah pada rusuk, maka secara umum graf dibedakan atas dua jenis:
Graf tak berarah (undirect graph) adalah graf yang rusuknya tidak mempunyai orientasi arah. Urutan pasangan titik yang terhubung oleh rusuk tidak diperhatikan. Sehingga (𝑣1, 𝑣2) = (𝑣2, 𝑣1) adalah rusuk yang sama. Graf tak berarah sering dipakai pada jaringan saluran telepon karena rusuk pada graf tak berarah menyatakan bahwa saluran telepon dapat beroperasi pada dua arah. Graf G4 di bawah ini merupakan contoh graf tak berarah.

(Gambar 4 Graf Tak Berarah G4)

Keterhubungan
Sebuah graf disebut terhubung jika untuk setiap dua titik terdapat rusuk yang menghubungkan kedua titik tersebut.

a. Jalan (walk), Walk dengan panjang k pada sebuah graf G adalah rangkaian terurut dari k rusuk pada graf G dengan bentuk : 𝑢𝑣, 𝑣𝑤, 𝑤𝑥, … , 𝑦𝑧 ;

Walk tersebut dinyatakan dengan 𝑢𝑣, 𝑣𝑤, 𝑤𝑥, … , 𝑦𝑧 atau dengan kata lain walk antara u sampai z (Robin J. Wilson & John J. Watkin, 1990 : 34).

b. Jejak (Trail) adalah walk dengan semua rusuk dalam barisan adalah berbeda (Munir, 2009 :370).

c. Lintasan (Path) adalah sebuah trail tanpa titik berulang (Robin J. Wilson & John J. Watkin, 1990: 35).

d. Sikel (Cycle) adalah sebuah trail tertutup yang titik awal dan akhir merupakan titik yang sama.

e. Graf Hamilton, Sirkuit Hamilton adalah lintasan yang melalui tiap titik dalam graf tepat satu kali. Graf Hamilton adalah graf yang memiliki sirkuit Hamilton. Contoh sirkuit Hamilton adalah (𝑣1, 𝑣2, 𝑣3, 𝑣4) pada G1. Contoh Graf Hamilton adalah G1.

Vehicle Routing Problem (VRP)

Vehicle Routing Problem (VRP) dapat didefinisikan sebagai permasalahan mencari rute dengan biaya minimum dari suatu depot ke pelanggan yang letaknya tersebar dengan jumlah permintaan yang berbeda-beda. Rute dibuat sedemikian rupa sehingga setiap pelanggan dikunjungi hanya satu kali oleh satu kendaraan. Seluruh rute berawal di depot, dan jumlah permintaan dalam satu rute tidak boleh melebihi kapasitas kendaraan.

VRP diperkenalkan pertama kali oleh Dantzig dan Ramzer pada tahun 1959 memegang peranan penting dalam pengaturan distribusi dan menjadi salah satu masalah yang dipelajari secara luas.VRP merupakan perhitungan formulasi dengan mempertimbangkan masalah jumlah kendaraan dan rute yang akan dilalui. Tujuan yang ingin dicapai dalam VRP di antaranya (Toth & Vigo, 2002):

1. Meminimalkan ongkos perjalanan secara keseluruhan yang dipengaruhi oleh keseluruhan jarak yang ditempuh dan jumlah kendaraan yang digunakan.

2. Meminimalkan jumlah kendaraan yang digunakan untuk melayani semua pelanggan.

3. Menyeimbangkan rute.

4. Meminimalkan keluhan pelanggan.

Pengertian Pohon

Graf T merupakan sebuah pohon jika dan hanya jika ada satu jalur sederhana pada setiap pasang simpul (i, j). Jika N = |V|, maka ada N 1 sisi (busur) dan semuanya terhubung, tanpa ada kalang (loop). Setiap simpul dapat menjadi akar pada pohon tersebut. Sebuah pohon dapat direpresentasikan dengann menyusun simpulsimpul dalam suatu urutan tertentu yang dimulai dari akar. Beberapa definisi pada pohon adalah sebagai berikut:

1. Setiap simpul (kecuali akar) hanya memiliki satu simpul orang tua.

2. Setiap simpul memiliki 0 atau lebih anak.

3. Sebuah sisi dengan 0 anak adalah merupakan daun.

Pohon adalah graf tak-berarah terhubung yang tidak mengandung sirkuit.

Hutan (forest) adalah kumpulan pohon yang saling lepas, atau graf tidak terhubung yang tidak mengandung sirkuit. Setiap komponen di dalam graf terhubung tersebut adalah pohon. Pohon mempunyai bilangan kromatis = 2.

Sifat-sifat Pohon:

1. Teorema. Misalkan G = (V, E) adalah graf tak-berarah sederhana dan jumlah simpulnya n. Maka, semua pernyataan di bawah ini adalah ekivalen:

a. G adalah pohon.

b. Setiap pasang simpul di dalam G terhubung dengan lintasan tunggal.

c. G terhubung dan memiliki m = n – 1 buah sisi.

d. G tidak mengandung sirkuit dan memiliki m = n – 1 buah sisi.

e. G tidak mengandung sirkuit dan penambahan satu sisi pada graf akan membuat hanya satu sirkuit.

f. G terhubung dan semua sisinya adalah jembatan.

2. Teorema di atas dapat dikatakan sebagai definisi lain dari pohon.

Pohon Merentang (Spanning Tree)

1. Pohon merentang dari graf terhubung adalah upagraf merentang yang berupa pohon.

2. Pohon merentang diperoleh dengan memutus sirkuit di dalam graf.

3. Setiap graf terhubung mempunyai paling sedikit satu buah pohon merentang.

4. Graf tak-terhubung dengan k komponen mempunyai k buah hutan merentang yang disebut hutan merentang (spanning forest).

Aplikasi Pohon Merentang

1. Jalan-jalan seminimum mungkin yang menghubungkan semua kota sehingga setiap kota tetap terhubung satu sama lain.

2. Perutean (routing) pesan pada jaringan komputer.

Pohon Rentang Minimum

1. Graf terhubung-berbobot mungkin mempunyai lebih dari 1 pohon merentang.

2. Pohon rentang yang berbobot minimum – dinamakan pohon merentang minimum (minimum spanning tree).

Graf Pohon
Graf pohon (tree) adalah suatu graf terhubung yang tidak memuat siklus. Suatu graf yang setiap titiknya mempunyai derajat satu disebut daun (pendant vertex)

Selanjutnya, akan diberikan definisi beberapa kelas graf pohon. Suatu graf bintang K, n (star) adalah suatu graf terhubung yang mempunyai satu titik berderajat n yang disebut pusat dan titik lainnya berderajat satu (Chartrand dkk., 1998).

Graf pohon disebut graf bintang ganda (double star) jika graf pohon tersebut mempunyai tepat dua titik x dan y berderajat lebih dari satu. Jika x dan y berturutturut berderajat a+1 dan b+1, dinotasikan dengan Sa,b , (Chartrand dkk., 1998)

Graf ulat (caterpillar graf) adalah graf pohon yang memiliki sifat apabila dihapus semua daunnya akan menghasilkan lintasan (Chartrand dkk., 1998).

Graf dan Algoritma Routing

Pada jaringan komputer, aliran setiap paket dapat dimodelkan dengan menggunakan graf yang memiliki bobot. Simpul pada graf merepresentasikan router, sedangkan busur pada graf merepresentasikan subnet. Routing adalah proses untuk meneruskan paket dari suatu simpul ke simpul yang lainnya dengan berdasarkan asas jalur terpendek. Tujuannya adalah agar pengiriman paket tersebut dapat dilakukan secara efektif dan efisien. Algoritma routing untuk mendapatkan jalur terpendek diantaranya adalah algoritma Dijkstra dan algoritma Kruskal.

Algoritma Routing

1. Algoritma Dijkstra (Pencarian Jalur Terpendek)

Algoritma ini bertujuan untuk menemukan jalur terpendek berdasarkan bobot terkecil dari satu titik ke titik lainnya. Misalkan titik mengambarkan gedung dan garis menggambarkan jalan, maka algoritma Dijkstra melakukan kalkulasi terhadap semua kemungkinan bobot terkecil dari setiap titik.

Pertama-tama tentukan titik mana yang akan menjadi node awal, lalu beri bobot jarak pada node pertama ke node terdekat satu per satu, Dijkstra akan melakukan pengembangan pencarian dari satu titik ke titik lain dan ke titik selanjutnya tahap demi tahap. Inilah urutan logika dari algoritma Dijkstra:

1. Beri nilai bobot (jarak) untuk setiap titik ke titik lainnya, lalu set nilai 0 pada node awal dan nilai tak hingga terhadap node lain (belum terisi).

2. Set semua node “Belum terjamah” dan set node awal sebagai “Node keberangkatan”.

3.Dari node keberangkatan, pertimbangkan node tetangga yang belum terjamah dan hitung jaraknya dari titik keberangkatan. Sebagai contoh, jika titik keberangkatan A ke B memiliki bobot jarak 6 dan dari B ke node C berjarak 2, maka jarak ke C melewati B menjadi 6+2=8. Jika jarak ini lebih kecil dari jarak sebelumnya (yang telah terekam sebelumnya) hapus data lama, simpan ulang data jarak dengan jarak yang baru.

4. Saat kita selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah terjamah sebagai “Node terjamah”. Node terjamah tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal bobotnya.

5. Set “Node belum terjamah” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selanjutnya dan lanjutkan dengan kembali ke step 3.

Dibawah ini penjelasan langkah per langkah pencarian jalur terpendek secara rinci dimulai dari node awal sampai node tujuan dengan nilai jarak terkecil.

1. Node awal 1, Node tujuan 5. Setiap edge yang terhubung antar node telah diberi nilai

2. Dijkstra melakukan kalkulasi terhadap node tetangga yang terhubung langsung dengan node keberangkatan (node 1), dan hasil yang didapat adalah node 2 karena bobot nilai node 2 paling kecil dibandingkan nilai pada node lain, nilai = 7 (0+7).

3. Node 2 diset menjadi node keberangkatan dan ditandai sebagi node yang telah terjamah. Dijkstra melakukan kalkulasi kembali terhadap node-node tetangga yang terhubung langsung dengan node yang telah terjamah. Dan kalkulasi dijkstra menunjukan bahwa node 3 yang menjadi node keberangkatan selanjutnya karena bobotnya yang paling kecil dari hasil kalkulasi terakhir, nilai 9 (0+9).

4. Perhitungan berlanjut dengan node 3 ditandai menjadi node yang telah terjamah. Dari semua node tetangga belum terjamah yang terhubung langsung dengan node terjamah, node selanjutnya yang ditandai menjadi node terjamah adalah node 6 karena nilai bobot yang terkecil, nilai 11(9+2).

5. Node 6 menjadi node terjamah, dijkstra melakukan kalkulasi kembali, dan menemukan bahwa node 5 (node tujuan) telah tercapai lewat node 6. Jalur terpendeknya adalah 1-36-5, dan niilai bobot yang didapat adalah 20 (11+9). Bila node tujuan telah tercapai maka kalkulasi dijkstra dinyatakan selesai

2. Algoritma Kruskal

Algoritma Kruskal adalah sebuah algoritma dalam teori graf yang mencari sebuah minimum tree untuk sebuah graf berbobot yang terhubung. Ini berarti menemukan subset dari tepi yang membentuk sebuah pohon yang mencakup setiap titik, dimana dimana berat total dari semua tepi diatas pohon diminimalkan. Jika grafik tidak terhubung, maka mmenemukan hutan rentang minimum (pohon rentan minimum untuk setiap komponen terhubung). Algoritma Kruskal juga tergolong algoritma Greedy dalam teori graf yang digunakan untuk mencari minimum spanning tree. Algoritma ini pertama kali muncul pada tahun 1956 dalam sebuah tulisan oleh Joseph Kruskal. Dasar pembentukan algoritma Kruskal berasal dari analogi glowing forest. Glowing forest maksudnya adalah untuk membentuk pohon merentang minimum T dari graf G adalah dengan cara mengambil satu persatu sisi dari graf G dan memasukkannya ke dalam pohon yang telah terbentuk sebelumnya. Seiring dengan berjalannya iterasi untuk setiap sisi, maka forest akan memiliki pohon yang semakain sedikit. Algoritma Kruskal akan terus menambah sisi-sisi kedalamm hutan yang sesuai hingga akhirnya tidak akan ada lagi forest, melainkan hanyalah sebuah pohon yang merentang minimum. Secara umum Algoritma Kruskal ditulis:

1. T masih kosong
2. Pilih sisi (i, j) dengan bobot minimum
3. Pilih sisi (i, j) dengan bobot minimum yang berikutnya yang tidak membentuk cycle di T, tambahkan (i,j) ke T
4. Ulangi langkah 3 sebanyak (n-2) kali
5. Total langkah (n-1) kali
6. Karakteristik Algoritma Kruskal

a. Sifat Algoritma Kruskal
1. Bekerja tidak hanya dengan grafik diarahkan.
2. Bekerja dengan bobot dan tidak grafik tertimbang. Tapi yang lebih menarik, apabila tepi yang berbobot.
3. Kruskal adalah jenis algoritma yang menghasilkan solusi optimal MST.
4. Langkah-Langkah Algoritma Kruskal
Langkah-langkah algoritma Kruskal adalah sebagai berikut:
1. Atur tepi berat: pling berat pertama dan terberat terakhir.
2. Pilih yang ringan tidak diperiksa tapi dari diagram.
3. Tambahkan tepi memilih ini ke pohon, hanya jika hal itu tidak membuat siklus.
4. Menghentikan proses kapanpun n-1 tapi lebihditambahkan kepohon.

Contoh algoritma Kruskal sebagai berikut:
Berikut adalah graf berbobot yang akan dicari pohon merentang minimum nya,dengan bobot sebesar 90.

AD dan CE adalah sisi dengan bobot terkecil, pilih sembarang antara AD dan CE, pilih AD.
Karena CE sisi terkecil berikutnya, pilih CE

Selanjutnya, pilih sisi DF dengan bobot 6.

AB dan BE adalah sisi dengan bobot terkecil yang belum dipilih, pilih sembarang antara AB dan BE, pilih AB.

Karena BE sisi terkecil berikutnya, pilih BE

Simpul G adalah simpul terakhir yang belum dipilih, oleh karena itu pilih sisi yang terhubung dengan simpul G, yaitu GE dan GF, karena GE memiliki bobot lebih kecil, pilih GE.

Karena semua simpul telah dipilih, maka pohon merentang minimum ditunjukkan dengan warna hijau. Dengan bobot sebesar 39. Dengan menggunakan struktur data sederhana kompleksitas waktu algoritma ini adalah O (E log E) yang ekuivalen dengan O (E log V).

Keduanya ekuivalen karena:

- E bernilai maksimal V²dan log V²= 2 x logV = O (log V)
- Jika kita tidak menghiraukan simpulsimpul yang terisolasi, V <= 2E, jadi log V adalah O (log E)

Hasil tersebut diperoleh dengan melalui beberapa tahap, pertama, urutkan sisi-sisi dengan menggunakan comparison sort dengan waktu O (E log E). Kemudian, gunakan himpunan struktur data yang disjoint untuk menjaga tempat simpul yang mana ada di komponen mana. Kemudian, tunjukkan O(E) operasi, untuk menemukan operasi- operasi dan kemungkinan satu union untuk setiap sisi. Sehingga, waktu total adalah O (E log E) = O (E log V). Misalkan sisi-sisi yang ada telah diurutkan atau bisa diurut dalam waktu yang linear (dengan counting sort atau radix sort), algoritma ini dapat menggunakan himpunan struktur data yang disjoint dengan lebih rumit, sehingga memiliki kompleksitas waktu O (E α(V)), dimana α adalah inverse dari fungsi Ackermann yang bernilai single, dan tumbuh dengan sangat lambat.
Berikut adalah contoh dari algoritma Dijikstra :

#include <iostream>

#define INF 99999

using namespace std;

main()

{

int n=10,i,j,start;

int G[n][n],tempGraf[n][n],jarak[n]={0,0,0,0,0,0,0,0,0,0},visit[n],temp[n],count;

G[0][0]=0; G[0][1]=3000; G[0][2]=4780; G[0][3]=0; G[0][4]=0; G[0][5]=5600; G[0][6]=0; G[0][7]=0; G[0][8]=0; G[0][9]=0;

G[1][0]=3000; G[1][1]=1800; G[1][2]=400; G[1][3]=0; G[1][4]=0; G[1][5]=0; G[1][6]=0; G[1][7]=0; G[1][8]=0; G[1][9]=0;

G[2][0]=4780; G[2][1]=1800; G[2][2]=0; G[2][3]=0; G[2][4]=0; G[2][5]=0; G[2][6]=1350;G[2][7]=0; G[2][8]=900; G[2][9]=0;

G[3][0]=0; G[3][1]=400; G[3][2]=0; G[3][3]=0; G[3][4]=600; G[3][5]=0; G[3][6]=1340;G[3][7]=0; G[3][8]=0; G[3][9]=0;

G[4][0]=0; G[4][1]=0; G[4][2]=0; G[4][3]=600; G[4][4]=0; G[4][5]=1370; G[4][6]=0; G[4][7]=0; G[4][8]=0; G[4][9]=0;

G[5][0]=5600; G[5][1]=0; G[5][2]=0; G[5][3]=0; G[5][4]=1370; G[5][5]=0; G[5][6]=1450;G[5][7]=0; G[5][8]=0; G[5][9]=3320;

G[6][0]=0; G[6][1]=0; G[6][2]=1350; G[6][3]=1340;G[6][4]=0; G[6][5]=1450; G[6][6]=0; G[6][7]=150; G[6][8]=0; G[6][9]=2530;

G[7][0]=0; G[7][1]=0; G[7][2]=0; G[7][3]=0; G[7][4]=0; G[7][5]=0; G[7][6]=150; G[7][7]=0; G[7][8]=400; G[7][9]=1330;

G[8][0]=0; G[8][1]=0; G[8][2]=900; G[8][3]=0; G[8][4]=0; G[8][5]=0; G[8][6]=0; G[8][7]=400; G[8][8]=0; G[8][9]=0;

G[9][0]=0; G[9][1]=0; G[9][2]=0; G[9][3]=0; G[9][4]=0; G[9][5]=3320; G[9][6]=2530;G[9][7]=1330;G[9][8]=0; G[9][9]=0;

for(i = 0;i < n ;i++)

{

for (j=0;j<n;j++)

{

cout<<"Matriks "<<"["<<i<<"]"<<"["<<j<<"]"<<" : ";

cout<<G[i][j]<<endl;

}

cout<<"Masukan Vertex Asal : ";

cin>>start;

for(i=0;i<n;i++)

{

for (j=0;j<n;j++)

{

if (G[i][j] == 0)

{

tempGraf[i][j] = INF;

}

else{

tempGraf[i][j] = G[i][j];

}

for (i = 0;i<n;i++)

{

jarak[i] = tempGraf[start][i];

temp[i] = start;

visit[i] = 0;

}

jarak[start] = 0;

visit[start] = 1;

count =1; ///dimulai dari 1 karena kita tidak akan menghitung vertex asal lagi

///proses untuk menghitung vertex yang dikunjungi

int jarakmin,nextvertex;

while (count < n-1)

{

jarakmin = INF;

for (i=0;i<n;i++)

{

///jika jarak lebih kecil dari jarak minimum dan vertex belum dikunjungi

/// maka jarak minimum adalah jarak yang sudah dibandingkan sebelumnya dengan jarakmin

if(jarak[i] < jarakmin && visit[i]!=1)

{

jarakmin = jarak[i];

nextvertex = i; ///untuk memberikan vertex pada jarak minimum

}

/// untuk mengecek vertex selanjutnya yang terhubung dengan vertex lain yang memiliki jarak minimum

visit[nextvertex] = 1;

for(i = 0;i<n;i++)

{

if(visit[i]!=1)

{

if(jarakmin+tempGraf[nextvertex][i]<jarak[i])

{

jarak[i] = jarakmin+tempGraf[nextvertex][i];

temp[i] = nextvertex;

}

count++;

}

///nenampilkan jalur dan jarak untuk setiap vertex

int a[n+1],k;

for (i = 0; i < n ;i++)

{

if(i!=start)

{

cout<<"\nHasil jarak untuk vertex ke-"<<i<<" adalah "<<jarak[i]<<endl;

j=i;

cout<<"<-"<<i<<" ";

while(j!=start)

{

j=temp[j];

cout<<j;

if(j!=start)

{

cout<<"<-";

}

jarak[i]+=jarak[i];

}

cout<<"\nTotal Jaraknya adalah "<<jarak[n-1];

return 0;

}

Jika ingin contoh program yang lainnya, silahkan download pada link :
Algoritma pohon :
https://drive.google.com/file/d/1CBT0Sw5U2J3hIn6dT-9t_YDxK6JZ45BT/view?usp=sharing
Algoritma Graf :
https://drive.google.com/file/d/1T0GCpQ5stzW2Xh_NVzl54sNe-3wTUJZH/view?usp=sharing
Algoritma Djikstra :
https://drive.google.com/file/d/1VlTE9zMMRZo0RJlN03QX9gdpLgR0pNr3/view?usp=sharing
Algoritma Kruskal :
https://drive.google.com/file/d/1n7jGdNuK5pzuKEuUnJ-WwUtgRp_-5juY/view?usp=sharing

DAFTAR PUSTAKA

Muhidin, Asep. 2010. Modul Kuliah Pemrograman Bahasa C++, Bekasi; Penerbit Zeyrank Offset.

Hasmawati. 2015. “BAHAN AJAR TEORI GRAF”. Fakultas Matematika Dan Ilmu Pengetahuan Alam Universitas Hasanuddin.

Siregar, Indra. 2009. “Penerapan Graf Pada Algoritma Routing”. Jurnal. Program Studi Teknik Teknik Informatika, Sekolah Teknik Elektro dan Informatika Institut Teknologi Bandung.

https://kaazima.blogspot.com/2013/12/contoh-program-c-program-tree-c-sederhana.html
https://galehfatmaea.blogspot.com/2014/05/graph-c.html

KURNIA'S TYPING

Rabu, 15 Mei 2019