Rabu, 15 Mei 2019

Graf dan Pohon Dalam Algoritma Pemrograman C++

| | 1 komentar

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 V2 dan log V2 = 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

Read more...

Selasa, 16 April 2019

Searching Dalam Algoritma Pemrograman C++

| | 0 komentar

SEARCHING

TI Politala Algoritma Pemrograman 2B

Pengertian Searching

     Algoritma pencarian (Searching algorithm) adalah algoritma yang menerima sebuah argumen kunci dan dengan langkah-langkah tertentu akan mencari argumen kunci tersebut pada data yang telah dimiliki. Setelah proses pencarian dilaksanakan, akan diperoleh salah satu dari dua kemungkinan, yaitu data yang dicari ditemukan (successful) atau tidak ditemukan (unsuccessful).      Ada dua macam teknik pencarian yaitu pencarian sekuensial (sequential search) dan pencarian biner (binary search). Perbedaan dari dua teknik ini terletak pada keadaan data. Pencarian sekuensial digunakan apabila data dalam keadaan acak atau tidak terurut. Sebaliknya, pencarian biner digunakan pada data yang sudah dalam keadaan urut.

Deklarasi Searching

1.   Sequential Search (Linier Search)
    Pencarian Sekuensial (sequential Searching) atau pencarian berurutan sering disebut pencarian linear merupakan metode pencarian yang paling sederhana. Pencarian beruntun adalah proses membandingkan setiap elemen larik satu persatu secara beruntun, mulai dari elemen pertama sampai elemen yang dicari ditemukan atau seluruh elemen sudah diperiksa.
     Teknik pencarian data dari array yang paling mudah adalah dengan cara sequential search, dimana data dalam array dibaca 1 demi satu, diurutkan dari indeks terkecil ke indeks terbesar, maupun sebaliknya. Jika data yang dicari mempunyai nilai yang sama dengan data yang ada dalam kelompok data, berarti data telah ditemukan. Tetapi jika data yang dicari tidak ada yang cocok dengan data-data dalam sekelompok data, berarti data tersebut tidak ada dalam sekelompok data. 
Contoh :
Array :
int A[] = {1,2,3,4,5,6,7,8,9,10} (indeks array pada bahasa C++ dimulai dari indeks ke 0) jika kita ingin mencari bilangan 6 dalam array tersebut, maka proses yang terjadi kita mencari
a)   Dari array indeks ke-0, yaitu 1, dicocokan dengan bilangan yang akan dicari, jika tidak sama, maka mencari ke indeks berikutnya
b)   Pada array indeks ke-1, juga bukan bilangan yang dicari, maka kita mencari lagi pada indeks berikutnya
c)  Pada array indeks ke-2, ternyata bilangan yang kita cari ada ditemukan, maka kita keluar dari looping pencarian.
Contoh program sequential search (Linier Search) :
#include <iostream>
#include <conio.h>
using namespace std;
int main()
{
int A[]={1,2,3,4,5,6,7,8,9,10};
int i, ketemu = 0, n;
int cari;
n = sizeof(A)/sizeof(A[0]);
cout<<"Masukkan data yang dicari : ";cin>>cari;
       for(i=0; i<n;i++)
       {
          if (A[i]==cari)
          {
              ketemu=!ketemu;
              break;
          }
      }
       if(ketemu>0)
       {
            cout<<"Data ditemukan di posisi: "<<i+1;
        }
        else
       {
            cout<<"Data tidak ditemukan";
        }
       getch();
}
Hasil running :
2.  Binary Search
    Binary search merupakan salah satu algoritma untuk melalukan pencarian pada array yang sudah terurut. Jika kita tidak mengetahui informasi bagaimana integer dalam array, maka penggunaan binary search akan menjadi tidak efisien, kita harus melakukan sorting terlebih dahulu atau menggunakan metode lain yaitu linear search. Namun jika kita telah mengetahui integer dalam array terorganisasi baik secara menaik atau menurun, maka bisa dengan cepat menggunakan algoritma binary search. Adapun ide dasar binary search yaitu memulai pencarian dengan membagi dua ruang pencarian. Misalnya kita memiliki array A, dan kita ingin menemukan lokasi dari spesifik target integer K dalam array. Ada 3 kemungkinan kondisi pada binary search yaitu:
1.   Jika data target K langsung di temukan, maka proses pembagian ruangan berhenti. Kemudian print out indeks data elemen pada array.
2.    Jika data target K < A[middle], maka pencarian dapat dibatasi hanya dengan melakukan pencarian pada sisi kiri array dari A[middle]. Seluruh elemen yang berada di sebelah kanan dapat di abaikan.
3.    Jika data target K > A[middle], maka akan lebih cepat jika pencarian di batasi hanya pada bagian sebelah kanan saja.
4.    Jika seluruh data telah di cari namun tidak ada, maka diberi nilai seperti -1.
Dibawah ini merupakan salah satu versi program binary search :
#include <iostream>
#include <conio.h>
using namespace std;
int main()
{
      const int Ar[10] = {1,2,3,4,5,6,7,8,9,10}; // untuk proses ascending
      int tar;
      cout<<"masukan data yang dicari : "; cin>>tar;
      int awal=0, akhir=10, tengah;
      while (awal <= akhir)
     {
             tengah = (awal + akhir)/2;
             if (tar > Ar[tengah] )   // descending ubah tanda > menjadi <
            {
                   awal = tengah + 1;
 }
             else if (tar < Ar[tengah]) // descending ubah tanda < menjadi >
            {
       akhir= tengah - 1;
}
            else
{
       awal = akhir +1;
            }
      }
      if (tar == Ar[tengah])
     {
cout<<" Data "<<tar<<" ditemukan, pada posisi ke- "<<tengah+1<<endl;
      }
      else
     {
cout<<"Data "<<tar<<" tidak ditemukan "<<endl;
  }
  getch();
}
Hasil running :

Contoh Program Binary Search Lainnya


 Hasil running :

Jika ingin contoh program searching yang lainnya, silahkan download pada link :

DAFTAR PUSTAKA


Muhidin, Asep. 2010. Modul Kuliah Pemrograman Bahasa C++, Bekasi; Penerbit Zeyrank Offset.
Arhami, Muhammad. 2010. “MODUL PRAKTIKUM ALGORITMA DAN STRUKTUR DATA”. Pendidikan Teknik Informatika. Politeknik Universitas Negeri Malang.
Rahmaddeni. 2012. “ANALISA PERBANDINGAN ALGORITMA PENCARIAN (SEARCHING ALGORITM)”. Jurnal. Jurnal Sains dan Teknologi Informasi, Vol. 1, No. 1.


Read more...

Kamis, 11 April 2019

Sorting Dalam Algoritma Pemrograman C++

| | 0 komentar

SORTING

TI Politala Algoritma Pemrograman 2B

Pengertian Sorting

Sorting adalah proses mengatur sekumpulan objek menurut aturan atau susunan tertentu. Urutan objek tersebut dapat menaik atau disebut juga ascending (dari data kecil ke data lebih besar) ataupun menurun/descending(dari data besar ke data kecil).
Metode Sorting :

  1. Bubble Sort (Metode Gelembung)
  2. Quick Sort atau Exchange Sort
  3. Merge Sort (Metode Penggabungan)
  4. Shell Sort 
  5. Insertion Sort (Metode Penyisipan)
  6. Selection Sort (Metode Seleksi)
Disini saya hanya akan membahas 3 metode yaitu Bubble Sort (Metode Gelembung),  Guick Sort atau Exchange Sort, dan Marge Sort (Metode Penggabungan).

Jenis-Jenis Metode Sorting

1.   Bubble Sort
      Merupakan metode sorting termudah, diberi nama “Bubble” karena proses pengurutan secara berangsur-angsur bergerak/berpindah ke posisinya yang tepat, seperti gelembung yang keluar dari sebuah gelas bersoda. Bubble Sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya. Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar, jika pengurutan ascending. Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar, jika pengurutan descending. Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya. Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya. Kapan berhentinya? Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.
Pada gambar di atas, pengecekan dimulai dari data yang paling akhir, kemudian dibandingkan dengan data di depannya, jika data di depannya lebih besar maka akan ditukar.
Pada proses ke-2, pengecekan dilakukan sampai dengan data ke-2 karena data pertama pasting sudah paling kecil.
Untuk contoh program ini adalah
#include <iostream>
#include <conio.h>
using namespace std;
main()
{
     int nilai['n'];
     int temp;
     int n;
     cout<<"Banyak Data: "; cin>>n;
     cout<<endl;
     for (int a=1; a<=n; a++)
    {
         cout<<"nilai[“<<a<<“]: "; cin>>nilai[a];
    }
    cout<<"\n\n";
    cout<<"Data Sebelum diurutkan"<<endl;
    for(int a=1; a<=n; a++)
    {
         cout<<nilai[a]<<" ";
    }
    for(int a=n-1; a>=1; a--)
   {
        for(int b=1; b<=a; b++)
        {
              if(nilai[b]>nilai[b+1])
              {
                   temp=nilai[b+1];
                   nilai[b+1]=nilai[b];
                   nilai[b]=temp;
               }
          }
    }
    cout<<"\n\nData Setelah Diurutkan (Ascending)"<<endl;
    for (int a=1; a<=n; a++)
   {
        cout<<nilai[a]<<" ";
   }
   cout<<"\n\n";
   cout<<"\n\nData Setelah Diurutkan (Descending)"<<endl;
   for (int a=n; a>=1; a--)
   {
         cout<<nilai[a]<<" ";
   }
   getch();
}
Hasil Running :
2.   Quick Sort atau Exchange Sort
     Quick Sort merupakan suatu algoritma pengurutan data yang menggunakan teknik pemecahan data menjadi partisi-partisi, sehingga metode ini disebut juga dengan nama partition exchange sort. Untuk memulai irterasi pengurutan, pertama-tama sebuah elemen dipilih dari data,  kemudian elemen-elemen data akan diurutkan diatur sedemikian rupa. Metode Quick sering disebut juga metode partisi (partition exchange sort). Metode ini mempunyai efektifitas yang tinggi dengan teknik menukarkan dua elemen dengan jarak yang cukup besar. Metode pengurutan quick sort dapat diimplementasikan dalam bentuk non rekursif dan rekursif. Berbagai varian dari quicksort pada intinya berupaya untuk mengembangkan teknik-teknik pembuatan partisi yang efektif untuk berbagai macam masukan.Hal ini merupakan bahan yang terus dipelajari hingga kini.Ditambah pula dengan perbaikan dari segi pemrograman sehingga lebih efisien (seperti mengurangi operasi pembandingan, pertukaran maupun perulangan).
     Sangat mirip dengan Bubble Sort, dan banyak yang mengatakan Bubble Sort sama dengan Exchange Sort. Perbedaan ada dalam hal bagaimana membandingkan antar elemen-elemennya. Exchange sort membandingkan suatu elemen dengan elemen-elemen lainnya dalam array tersebut, dan melakukan pertukaran elemen jika perlu. Jadi ada elemen yang selalu menjadi elemen pusat (pivot). Sedangkan Bubble Sort akan membandingkan elemen pertama/terakhir dengan elemen sebelumnya/sesudahnya, kemudian elemen sebelum/sesudahnya itu akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi, begitu seterusnya.
untuk contoh program ini adalah
#include <iostream>
#include <conio.h>
using namespace std;
void tampilkan_data(int data[], int n)
{
     int i;
     for (i=1;i<=n;i++)
     cout<<data[i]<<" ";
     cout<<"\n";
}
int partisi (int data[], int awal, int akhir)
{
      int x,i,j,simpan;
      //www.nutekno.com
      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);
    }
}
int main()
{
    int i,j,n,data[100];
    cout<<"masukkan banyak data= ";cin>>n;
    for(i=1;i<=n;i++)
   {
         cout<<"data ke-"<<i<<" = ";cin>>data[i];
   }
   cout<<"Data sebelum diurut: "<<endl;
   for(j=1;j<=n;j++)
  {
       cout<<data[j]<<" ";
   }
   quick_sort(data,1,n);
    //hasil pengurutan
    cout<<endl<<endl;
    cout<<"hasil pengurutan:\n";
    tampilkan_data(data,n);
 getch();
}
Hasil Running :
3.   Merge Sort
Merge sort adalah algoritme divide-and-conquer berdasar kepada proses memecah list menjadi beberapa sublist hingga pada akhirnya tiap sublist hanya berisi satu elemen lalu sublist tersebut akan digabungkan dengan cara tertentu hingga list tersortir.
Konsep Dasar:
  • Membagi list acak menjadi NN sublist, masing-masing memiliki 11elemen.
  • Ambil sepasang list singleton dan gabungkan mereka menjadi list dengan 2 elemen. NN akan dikonversi menjadi N/2N/2 list dengan ukuran 2.
  • Ulangi proses ini hingga tersisa satu list yang sudah teratur.
Saat membandingkan dua sublist untuk digabungkan, elemen pertama pada kedua list akan dijadikan dasar pertimbangan. Saat melakukan penyortiran dengan urutan ascending, elemen dengan nilai yang lebih kecil akan menjadi elemen baru dari list tersortir. Prosedur ini diulangi hingga sublist yang lebih kecil kosong dan sublist hasil penggabungan baru memiliki semua elemen kedua sublist.
Sebagaimana yang dapat dipahami dari gambar di atas, pada setiap langkah, list dengan ukuran MM dibagi menjadi 22 sublist berukuran M/2M/2, hingga pembagian tidak dapat lagi dilakukan. Lebih mudahnya, diketahui terdapat array AA yang lebih kecil dengan elemen (9,7,8)(9,7,8).
Pada langkah pertama, list berukuran 33 dibagi menjadi 22 sublist dengan sublist pertama terdiri dari (9,7)(9,7) dan sublist kedua terdiri dari (8)(8). Sekarang, list pertama yang terdiri dari elemen (9,7)(9,7)dibagi lagi menjadi 22 sublist terdiri dari elemen (9)(9) dan (7)(7) secara berurutan.
Sublist tersebut tidak dapat dibagi lagi karena setiap sublist hanya memiliki 11 elemen, kini kita akan mulai menggabungkan list tersebut. 22 sublist yang terbentuk pada langkah terakhir akan digabungkan sesuai urutan menggunakan prosedur yang disebutkan di atas dan membentuk list baru (7,9)(7,9). Dengan melakukan backtracking, kita akan menggabungkan list yang berisi elemen (8)(8)dengan list ini, sehingga list baru yang tersortir terbentuk (7,8,9)(7,8,9).
Implementasi cara tersebut tersedia di bawah ini:
void merge(int A[ ] , int start, int mid, int end) 
{
    //menyimpan posisi awal kedua posisi awal kedua bagian dalam variabel temporer
    int p = start ,q = mid+1;
    int Arr[end-start+1] , k=0;
for(int i = start ;i &lt;= end ;i++)
{
     if(p &gt; mid)      //memeriksa apabila bagian pertama berakhir atau belum
     Arr[ k++ ] = A[ q++] ;
     else if ( q &gt; end)   //memeriksa apabila bagian kedua berakhir atau belum
     Arr[ k++ ] = A[ p++ ];
     else if( A[ p ] &lt; A[ q ])     //memeriksa bagian mana yang memiliki elemen yang lebih kecil
     Arr[ k++ ] = A[ p++ ];
     else
     Arr[ k++ ] = A[ q++];
 }
for (int p=0 ; p&lt; k ;p ++) 
{
    /* Sekarang array yang sebenarnya memiliki elemen yang tersortir untuk kedua bagian. */
    A[ start++ ] = Arr[ p ] ;                         
}
}
Di sini, pada fungsi merge, kita akan melakukan merge pada dua bagian array di mana satu bagian memiliki posisi dari awal hingga pertengahan dan bagian lain memiliki posisi mid+1 hingga akhir.
Awalan diambil dari bagian depan array, yaitu p dan q. Lalu elemen pada kedua bagian akan dibandingkan dan elemen dengan nilai yang lebih kecil akan disimpan di auxiliary array (Arr[ ]). Jika pada kondisi tertentu, salah satu bagian berakhir, maka semua elemen dari elemen yang satunya akan ditambahkan ke auxiliary array dengan urutan yang sama.
Amati 2 fungsi recursion bercabang berikut ini:
void merge_sort (int A[ ] , int start , int end )
{
     if( start &lt; end ) 
     {
           int mid = (start + end ) / 2 ;    // membagi array menjadi dua bagian
           merge_sort (A, start , mid ) ;  // menyortir bagian pertama array
           merge_sort (A,mid+1 , end ) ;// menyortir bagian kedua array
           // menyatukan kedua bagian dengan membandingkan elemen pada kedua bagian
          merge(A,start , mid , end );  
      }                   
}
untuk contoh program ini adalah
#include <iostream>
#include <conio.h>
using namespace std;
int a[50];
void merge(int,int,int);
void merge_sort(int low,int high)
{
     int mid;
     if(low<high)
     {
          mid=(low+high)/2;
          merge_sort(low,mid);
          merge_sort(mid+1,high);
          merge(low,mid,high);
     }
}
void merge(int low,int mid,int high)
{
     int h,i,j,b[50],k;
     h=low;
     i=low;
     j=mid+1;
    while((h<=mid)&&(j<=high))
    {
         if(a[h]<=a[j])
         {
              b[i]=a[h]; h++;
          }
         else
         {
              b[i]=a[j]; j++;
          } i++;
     }
 if(h>mid)
 {
       for(k=j;k<=high;k++)
       {
            b[i]=a[k]; i++;
        }
  }
        else
       {
             for(k=h;k<=mid;k++)
             {
                  b[i]=a[k]; i++;
              }
        }
              for(k=low;k<=high;k++)
              a[k]=b[k];
        }
main()
{
 int num,i;
 cout<<"*******************************************************************"<<endl;
 cout<<"                         MERGE SORT PROGRAM "<<endl;
 cout<<"*******************************************************************"<<endl;
 cout<<endl<<endl;
 cout<<"Masukkan Banyak Bilangan : ";cin>>num;
   cout<<endl;
 cout<<"Sekarang masukkan "<< num <<" Bilangan yang ingin Diurutkan :"<<endl;
 for(i=1;i<=num;i++)
 {
  cout<<"Bilangan ke-"<<i<<" : ";cin>>a[i] ;
 }
 merge_sort(1,num);
 cout<<endl;
 cout<<"Hasil akhir pengurutan : "<<endl;
 cout<<endl;
 for(i=1;i<=num;i++)
  cout<<a[i]<<" ";
 cout<<endl<<endl<<endl<<endl;
   getch();

}
Hasil Running :

DAFTAR PUSTAKA


Read more...
animasi  bergerak gif

Popular Posts

Blogger templates

Blogroll

About

Diberdayakan oleh Blogger.

Cari Blog Ini

Postingan lain

Translate

Blogger templates

Pages

Pages

Popular Posts

 

Designed by: CompartidΓ­simo
Images by: DeliciousScraps©