GRAF DAN POHON DALAM PEMROGRAMAN C++

ALGORITMA DAN PEMROGRAMAN 2 "GRAF DAN POHON"

[ Tugas Kuliah ] Algoritma dan Pemrograman 2 | Graf dan Pohon

Tugas TI POLITALA Alpro 2C

Nama               : Prima Angelia Rehulina Barus

Kelas               : 2C

Jurusan            : Teknik Informatika

NIM                : 1801301109

Matkul             : Alpro 2 Tugas 4

Semester          : II  

GRAF DAN POHON

Pada pembahasan kali ini, saya akan menjelaskan tentang materi graf dan pohon khususnya materi graf dan pohon dengan algoritma djikstra dan kruskal. Materi ini berdasarkan hasil diskusi kelompok dengan kasus rumah makan terdekat di Pelaihari dengan algoritma djikstra dan kruskal.

A.    Pengertian Graf

Sebuah graf G didefinisikan sebagai pasangan himpunan (V,E) , dengan V adalah himpunan tak kosong yang terdiri dari simpul-simpul (vertices) atau titik pada G. Sedangkan E adalah himpunan rusuk (edge) atau sisi pada G yang menghubungkan sepasang simpul atau titik. Himpunan simpul atau titik pada G dinotasikan sebagai V, dan himpunan rusuk atau sisi pada G dinotasikan sebagai E. Jadi G=(V, E)

Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graph, maka graph digolongkan menjadi dua jenis:

1.      Graph sederhana (simple graph).

Graf yang tidak mempunyai gelang atau loop maupun sisi ganda.

2.      Graph tak-sederhana (unsimple-graph).

Graf yang mempunyai gelang atau loop maupun sisi ganda.

Berdasarkan jumlah simpul pada suatu graph, maka secara umum graph dapat digolongkan menjadi dua jenis:

    1. Graph berhingga (limited graph)

    2. Graph tak-berhingga (unlimited graph)

Berdasarkan orientasi arah pada sisi, maka secara umum graph  dibedakan atas 2 jenis:

1.  Graph tak-berarah (undirected graph)

Graph yang sisinya tidak mempunyai orientasi arah atau panah disebut graph tak-berarah.

2.  Graph berarah (directed graph atau digraph)

Graph yang setiap sisinya diberikan orientasi arah atau panah disebut sebagai graph berarah.

Algoritma Graf

Algoritma Graf yang dibahas dalam laporan ini ada 2 yaitu :

a)      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 kalkulasiatau total  terhadap semua kemungkinan bobot terkecil dari setiap titik yang dilalui.

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.

2. Algoritma Kruskal

Algoritma Kruskal adalah sebuah algoritma dalam teori graf yang mencari sebuah minimum tree untuk sebuah graf berbobot yang terhubung. Jika grafik tidak terhubung, maka menemukan hutan rentang minimum (pohon rentan minimum untuk setiap komponen terhubung). 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 kedalam 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

Karakteristik dari Algoritma Kruskal :

a.Sifat dari 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.

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 lebih ditambahkan kepohon.

B.     Pengertian Pohon

Pohon (tree) adalah merupakan graf yang tak berarah terhubung yang tidak memuat sirkuit sederhana. pohon adalah suatu graph yang banyak vertexnya sama dengan n (n>1), jika :

~ Graph tersebut tidak mempunyai lingkar (cycle free) dan banyaknya rusuk (n-1).

~ Graph tersebut terhubung .

Hutan ( forest ) merupakan kumpulan pohon yang saling lepas. Dengan kata lain, hutan merupakan graf tidak terhubung yang tidak mengandung sirkuit.

Berikut adalah beberapa sifat pohon :

1. Misalkan G merupakan suatu graf dengan n buah simpul dan tepat n – 1 buah sisi.

2. Jika G tidak mempunyai sirkuit maka G merupakan pohon.

3. Suatu pohon dengan n buah simpul mempunyai n – 1 buah sisi.

4. Setiap pasang simpul di dalam suatu pohon terhubung dengan lintasan tunggal.

5. Misalkan G adalah graf sederhana dengan jumlah simpul n,jika G tidak mengandung sirkuit maka penambahan satu sisi pada graf hanya akan membuat satu sirkuit.

C.     Permasalahan

Permasalahan yang terdapat pada laporan ini adalah sebagai berikut:

1.                   Membuat sebuah pembahasan tentang graf dan pohon serta algoritma djikstra dan kruskal.

2.                   Membuat sebuah program mencari jalur terpendek antar rumah makan terdekat di Pelaihari menggunakan algoritma djikstra dan kruskal.

D.    Penjelasan Kasus

Kasus yang diambil dalam laporan ini adalah kasus rumah makan terdekat di pelaihari. Disini diambil beberapa rumah makan ada sekitar 10 rumah makan. Dari 10 rumah makan tersebut diukur jaraknya di google map untuk memuat grafnya. Setelah itu dibuat jarak satu persatu rumah makan untuk membuat matriks berbobotnya.

a)      Map

b)      Graf Djikstra dan Kruskal

c)      Matriks Djikstra

d)      Matriks Kruskal

e)      Codingan Algoritma Djikstra

Hasil Running Djikstra

f)       Codingan Algoritma Kruskal

Hasil Running Kruskal

Sekian penjelasan dari saya tentang materi graf dan pohon khususnya materi graf dan pohon dengan algoritma djikstra dan kruskal. Semoga bermanfaat.

Daftar pustaka

Rifanti, Marina Utti. 2017. “PEMILIHAN RUTE TERBAIK MENGGUNAKAN ALGORITMA DIJKSTRA UNTUK MENGURANGI KEMACETAN LALU LINTAS DI PURWOKERTO (BEST ROUTE SELECTION USE DIJKSTRA ALGORITHM TO REDUCE TRAFFIC CONGESTION IN PURWOKERTO)”. Diakses pada tanggal 25 Mei 2019 pukul 09.30 WITA dari https://www.researchgate.net/publication/325059321_Pemilihan_Rute_Terbaik_Menggunakan_Algoritma_Dijkstra_Untuk_Mengurangi_Kemacetan_Lalu_Lintas_di_Purwokerto/download

Amrullah. 2018. “APLIKASI GRAF POHON PADA ALGORITMA HUFFMAN”. Diakses pada tanggal 25 Mei 2019 pukul 10.45 WITA dari https://www.researchgate.net/publication/322423546

Read More →

SORTING DALAM PEMROGRAMAN C++

ALGORITMA DAN PEMROGRAMAN 2 "SORTING"

[ Tugas Kuliah ] Algoritma dan Pemrograman 2 | Sorting – Bubble Sort

Tugas TI POLITALA Alpro 2C

Nama               : Prima Angelia Rehulina Barus

Kelas               : 2C

Jurusan            : Teknik Informatika

NIM                : 1801301109

Matkul             : Alpro 2 Tugas 3

Semester          : II  

SORTING

Pada pembahasan kali ini, saya akan menjelaskan tentang materi sorting khususnya materi sorting dengan algoritma bubble sort dan quick sort.

Pengertian Sorting (pengurutan)

            Sorting yaitu suatu aktivitas untuk mengurutkan suatu data yang belum terurut misalnya mengurutkan data-data dari nilai yang terkecil ke terbesar ataupun sebaliknya.

Ada 6 jenis metode sorting, yaitu;

1.      Bubble sort

2.      Insertion sort

3.      Merge sort

4.      Quick sort

5.      Selection sort

6.      Shell sort 

Tetapi pada kali ini saya akan membahas tentang salah satu materi yaitu sorting dengan algoritma bubble sort dan quick sort.

a.       Metode Pengurutan dengan Bubble Sort

Metode pengurutan bubble sort merupakan algoritma pengurutan yang paling tua dan sederhana dan mudah untuk diimplementasikan. Metode gelembung (bubble sort) disebut juga dengan metode pertukaran (exchange sort) yaitu metode yang mengurutkan data dengan cara membandingkan masing-masing elemen, kemudian melakukan penukaran bila perlu. Metode ini mudah untuk dipahami dan diprogram, tetapi bila dibandingkan dengan metode lain yang lebih kompleks, metode ini merupakan metode yang paling tidak efisien untuk mengurutkan data.

b.      Metode Pengurutan dengan Quick Sort

Metode pengurutan quick sort merupakan algoritma pengurutan data yang sangat cepat dengan tipe penyelesaian divide and conquer. sehingga cocok untuk mengurutkan data dalam jumlah yang besar.

c.       Algoritma dari Bubble Sort  

Adapun Proses Algoritma Bubble Sort  adalah sebagai berikut:

1.      Pengurutan dimulai dengan membandingkan elemen pertama untuk mendapatkan angka terbesar. Lalu angka tersebut ditempatkan pada elemen terakhir.

2.      Pada akhir proses pertama ini, bilangan yang terbesar menempati tempat yang sesuai.

3.      Pada akhir proses kedua ini, bilangan terbesar kedua menempatkan tempat yang sesuai.

4.      Bila proses ini dilanjutkan, tidak ada pertukaran tempat lagi bagi bilangan – bilangan tersebut, sebab bilangan tersebut telah selesai disusun.

Algoritma pengurutan dengan bubble sort dapat dituliskan sebagai berikut :

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

    {

     for (j=n-1; j>=i+1; j--)

     {

         if (data[j]<data[j-1])

         {

             buble=data[j];

             data[j]=data[j-1];

             data[j-1]=buble;

         }

     }

    }

d.      Algoritma dari Quick  Sort

Adapun proses Algoritma Quick Sort adalah Sebagai berikut:

1.      Pilih satu elemen secara acak sebagai pivot

2.      Pindahkan semua elemen yang lebih kecil ke sebelah kiri pivot dan semua elemen yang lebih besar ke sebelah kanan pivot. Elemen yang nilainya sama bisa disimpan di salah satunya.

3.      Lakukan sort secara rekursif terhadap sub-array sebelah kiri dan kanan pivot

Algoritma pengurutan dengan quick sort dapat dituliskan sebagai berikut :

int partisi (int data[], int awal, int akhir)

{

int x,i,j,simpan;

 i=awal;

 j=akhir;

while(1)

{

while(data[i]<data[awal])

 i=i+1;

while(data[j]>data[awal])

j=j-1;

 if (i<j)

{

 //tukarkan data

simpan=data[i];

data[i]=data[j];

data[j]=simpan;

}

else

return j;

}

}

void quick_sort(int data[], int awal, int akhir)

{

int q;

if(awal<akhir)

{

q=partisi(data,awal,akhir);

quick_sort(data,awal,q);

quick_sort(data, q+1,akhir);

}

}

e.       Contoh Program

Berikut ini adalah contoh program bubble sort :

#include <iostream>

using namespace std;

int main()

{

    int i,j,n, bubble,pil, data[10];

    cout<<"========================================="<<endl;

    cout<<"| Program Sorting Data                  |"<<endl;

    cout<<"| Pilih Metode Sorting Bubble  :        |"<<endl;

    cout<<"|      1. Ascending                     |"<<endl;

    cout<<"|      2. Descending                    |"<<endl;

    cout<<"========================================="<<endl;

    cout<<"Masukkan Banyak Nomor Undian: ";cin>>n;

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

    {

        cout<<"Data ke - "<<i+1<<" : ";cin>>data[i];

    }

    cout<<"Masukkan Metode Yang Dipilih : ";cin>>pil;

    if (pil==1)

    {

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

    {

     for (j=n-1; j>=i+1; j--)

     {

         if (data[j]<data[j-1])

         {

             bubble=data[j];

             data[j]=data[j-1];

             data[j-1]=bubble;

         }

     }

    }

                 cout<<"Data yang telah disorting secara ascending "<<endl;

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

             {

                 cout<<"Data ke- "<<i+1<<" : "<<data[i]<<endl;

             }

    }

    else if (pil==2)

    {

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

    {

     for (j=n-1; j>=i+1; j--)

     {

         if (data[j]>data[j-1])

         {

             bubble=data[j];

             data[j]=data[j-1];

             data[j-1]=bubble;

         }

     }

    }

    cout<<"Data yang telah disorting secara descending "<<endl;

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

             {

                 cout<<"Data ke- "<<i+1<<" : "<<data[i]<<endl;

             }

    }

}

Sekian penjelasan dari saya tentang materi sorting yaitu sorting dengan algoritma bubble sort dan quick sort. Semoga bermanfaat.

Daftar pustaka

http://yuliana.lecturer.pens.ac.id/Struktur%20Data/PRAKTIKUM%202015/Praktikum%2011-%20Sorting%20Bubble%20Sort.pdf

http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2006-2007/Makalah/Makalah0607-77.pdf

http://aren.cs.ui.ac.id/sda/resources/sda2010/06_sorting.pdf

http://eprints.undip.ac.id/19736/1/sorting.pdf

http://ruzi.staff.gunadarma.ac.id/Downloads/files/32027/PENGURUTAN+BILANGAN+DENGAN+METODE+BUBBLE+SORT.doc

Read More →