GRAF DAN POHON DALAM PEMROGRAMAN C++

GRAF

Pengertian Graf

Sebuah graf (G) didefinisikan sebagai pasangan himpunan (V,E) dengan V sebagai himpunan tak kosong dari simpul pada G. E adalah himpunan rusuk(edge) pada G yang menghubungkan sepasang simpul. Jadi, dapat disimpulkan dalam graf(G), himpunan simpul dinotasikan dengan V dan himpunan rusuk dinotasikan dengan E.

Berikut beberapa istilah yang sering digunakan dalam graf yaitu:

1. Gelang (loop)

Dikatakan gelang apabila ujung rusuknya berawalan dan berakhiran simpul yang sama.

2. Rusuk ganda (multiple edges)

Dikatakan rusuk ganda apabila terdapat lebih dari satu rusuk yang bersisian dengan sepasang simpul.

3. Bertetanggaan (adjacent)

Dikatakan bertetangga apabila dua buah simpul terhubung langsung dengan sebuah rusuk.

4. Bersisian (incident)

Dikatakan bersisian apabila satu rusuk bersisian dengan simpul a dan b.

5. Graf kosong (null graph)

Graf kosong apabila himpunan rusuknya adalah himpunan kosong.

6. Perjalanan (walk)

Adalah barisan antar simpul dan rusuk pada G

7. Lintasan (path)

8. Sirkuit (circuit)

Sirkuit adalah lintasan yang berawalan dan berakhhiran pada simpul yang sama.

9. Terhubung (connected)

Dikatakan terhubung apabila terdapat lintasan dari u ke v. Jika dua buah simpul terhubung maka pasti simpul yang pertama dapat dicapai oleh simpul kedua.

10. Graf berbobot (weighted graph)

Adalah graf yang setiap rusuknya diberi sebuah harga(bobot).

Jenis-jenis graf secara umum yaitu:

1. Graf sederhana adalah graf yang tidak mempunyai rusuk ganda dan gelang. Beberapa graf sederhana yaitu:

    a. Graf lengkap adalah graf sederhana yang setiap simpulnya bertetangga.

    b. Graf lingkaran adalah graf sederhana yang setiap simpulnya berderajat dua.

    c. Graf teratur adalah graf yang simulnya mempunyai derajat yang sama.

    d. Graf bipartit adalah graf yang himpunan simpulnya dikelompokkan menjadi dua himpunabagian v1 dan v2.

2. Graf tak sederhana adalah graf yang mengandung rusuk ganda atau gelang.

Jenis-jenis graf berdasarkan orientasi arah yaitu:

1. Graf tak berarah adalah graf yang rusuknya tidak mempunyai orientasi arah.

2. Graf berarah adalah graf yang setiap rusuknya memiliki orientasi arah.

Algoritma Graf

1. Algoritma Djikstra

Agoritma ini dipakai dalam memecahkan permasalahan jarak terpendek untuk sebuah graf berarah. algoritma djikstra bekerja dengan membuat jalur ke satu simpul pada setiap langkah. Langkah-langkah algoritma djikstra yaitu dengan langkah-langkah berikut:

   a. Menentukan titik awal, lalu memberi bobot untuk masing-masing node. Algoritma ini akan melakukan pencarian dari satu titik ke titik yang lainnya.

     b. Set semua node yang belum dilalui dan set node awal sebagai node keberangkatan.

    c. Dari node keberangkatan, hitung jarak node yang belum dilalui dan hitung jaraknya dari titik keberangkatan.

     d. Setelah selesai, tandai node yang telah dilalui sebagai node dilewati.

   e. Set node yang belum dilewati dengan jarak terkecil dari node keberangkatan sebagai node keberangkatan selanjutnya.

2. Algoritma Kruskal

Algoritma ini dipakai dalam graf yang diurutkan terlebih dahulu berdasarkan bonpynya dari kecil ke besar. Langkah-langkah algoritma ini adalah sebagai berikut:

      a. Lakukan pengurutan terhadap setiap sisi di graf mulai dari terkecil sampai terbesar.

      b. Pilih sisi yang mempunyai bobot minimum dan tidak membentuk sirkuit.

     c. Ulangi langkah kedua sampai pohon rentang minimum terbentuk dan berjumlah n-1(n adalah jumlah simpul graf)

POHON

Pengertian Pohon

Dalam ilmu komputer, tree adalah struktur data yang secara bentuk menyerupai sebuah pohon yang terdiri dari serangkaian node(simpul) yang saling berhubungan. Node-node tersebut dihubungkan oleh sebuah vektor. Pohon (tree) merupakan salah satu bentuk khusus dari struktur suatu graf. 

Hutan(forest) adalah kumpulan pohon yang saling lepas atau graf yang tak terhubung.

Sifat-sifat pohon:

Misal  G = (V,E) adalah garf tak berarah sederhana dan jumlah simpulnya n. Maka pernyataan di bawah ini adalah ekivalen.

1. G adalah pohon

2. Setiap pasang simpul dalam  terhubung oleh lintasan tunggal.

3. G terhubung dan memiliki m=n-1 buah sisi

4. G tidak mengandung sirkuit dan memiliki m=n-1 buah sisi

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

6. G terhubung dan semua sisinya adalah jembatan.

Contoh Kasus

Kasus yang diambil adalah mencari rumah sakit terdekat di wilayah Banjarmasin. Rumah sakit yang diambil dalam kasus ini berjumlah 10 rumah sakit. Bobot atau jarak antar rumah sakit diukur melalui google maps.

1. Map

2. Graf

3. Matriks

4. Program 

Djikstra
#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]=2300; G[0][2]=1040;  G[0][3]=0;   G[0][4]=0;    G[0][5]=0;    G[0][6]=0;   G[0][7]=0;   G[0][8]=0;   G[0][9]=0;
    G[1][0]=2300; G[1][1]=0;    G[1][2]=2620;  G[1][3]=0;   G[1][4]=2907; G[1][5]=3320; G[1][6]=0;   G[1][7]=0;   G[1][8]=0;   G[1][9]=0;
    G[2][0]=1040; G[2][1]=2620; G[2][2]=0;     G[2][3]=2070;G[2][4]=1080; G[2][5]=0;    G[2][6]=0;   G[2][7]=0;   G[2][8]=0;   G[2][9]=0;
    G[3][0]=0;    G[3][1]=0;    G[3][2]=2070;  G[3][3]=0;   G[3][4]=0;    G[3][5]=0;    G[3][6]=0;   G[3][7]=3620;G[3][8]=0;   G[3][9]=0;
    G[4][0]=0;    G[4][1]=2970; G[4][2]=1080;  G[4][3]=0;   G[4][4]=0;    G[4][5]=2900; G[4][6]=2170;G[4][7]=0;   G[4][8]=0;   G[4][9]=0;
    G[5][0]=0;    G[5][1]=3320; G[5][2]=0;     G[5][3]=0;   G[5][4]=2900; G[5][5]=0;    G[5][6]=1660;G[5][7]=0;   G[5][8]=0;   G[5][9]=4460;
    G[6][0]=0;    G[6][1]=0;    G[6][2]=0;     G[6][3]=0;   G[6][4]=2170; G[6][5]=1660; G[6][6]=0;   G[6][7]=1760;G[6][8]=0;   G[6][9]=1120;
    G[7][0]=0;    G[7][1]=0;    G[7][2]=0;     G[7][3]=3620;G[7][4]=0;    G[7][5]=0;    G[7][6]=1760;G[7][7]=0;   G[7][8]=1390;G[7][9]=0;
    G[8][0]=0;    G[8][1]=0;    G[8][2]=0;     G[8][3]=0;   G[8][4]=0;    G[8][5]=0;    G[8][6]=0;   G[8][7]=1390;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]=4460; G[9][6]=1120;G[9][7]=0;   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;
}

Hasil Running

Kruskal
#include <cstdlib>
#include <iostream>
#include <fstream>

using namespace std;
class kruskal
{
    private:
    int n; //no of nodes
    int noe; //no edges in the graph
    int graph_edge[100][4];

    int tree[10][10];

    int sets[100][10];
    int top[100];
    public:
    int read_graph();
    void initialize_span_t();
    void sort_edges();
    void algorithm();
    int find_node(int );
    void print_min_span_t();
};

int kruskal::read_graph()
{
//cout<<"Program ini Mengimplementasikan Algoritma Kruskal\n";
cout<<"Banyak titik graph : ";
cin>>n;
noe=1;

cout<<"\nJarak antar tiap titik:\n";

for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
        cout<<"("<<i<<" , "<<j<<") = ";
        int w;
        cin>>w;
            if(w!=0)
            {
            noe++;

            graph_edge[noe][1]=i;
            graph_edge[noe][2]=j;
            graph_edge[noe][3]=w;
            }
        }
    }

}

void kruskal::sort_edges()
{
/**** Sort the edges using bubble sort in increasing order**************/

for(int i=1;i<=noe;i++)
{
    for(int j=1;j<=noe-i;j++)
    {
        if(graph_edge[j][3]>graph_edge[j+1][3])
        {
        int t=graph_edge[j][1];
        graph_edge[j][1]=graph_edge[j+1][1];
        graph_edge[j+1][1]=t;

        t=graph_edge[j][2];
        graph_edge[j][2]=graph_edge[j+1][2];
        graph_edge[j+1][2]=t;

        t=graph_edge[j][3];
        graph_edge[j][3]=graph_edge[j+1][3];
        graph_edge[j+1][3]=t;
        }
    }
}



cout<<"\n\nSetelah Jarak diurutkan adalah ::\n";
for(int i=1;i<=noe;i++)
cout<<"("<< graph_edge[i][1]
<<" , "<<graph_edge[i][2]
<<" ) = "<<graph_edge[i][3]<<endl;
}

void kruskal::algorithm()
{

    for(int i=1;i<=n;i++)
    {
    sets[i][1]=i;
    top[i]=1;
    }

cout<<"\nRentang Yang di Pakai\n\n";

    for(int i=1;i<=noe;i++)
    {
    int p1=find_node(graph_edge[i][1]);
    int p2=find_node(graph_edge[i][2]);

        if(p1!=p2)
        {
            cout<<"Rentang yg masuk ke pohon ::"
            <<" < "<<graph_edge[i][1]<<" , "
            <<graph_edge[i][2]<<" > "<<endl<<endl;

            tree[graph_edge[i][1]][graph_edge[i][2]]=graph_edge[i][3];
            tree[graph_edge[i][2]][graph_edge[i][1]]=graph_edge[i][3];

            // Mix the two sets

            for(int j=1;j<=top[p2];j++)
            {
                top[p1]++;
                sets[p1][top[p1]]=sets[p2][j];
            }

            top[p2]=0;
        }
        else
        {
            cout<<"Jika "
            <<" < "<<graph_edge[i][1]<<" , "
            <<graph_edge[i][2]<<" > "<<"di masukkan, maka terbentuk siklus. jadi di hapus\n\n";
        }
    }
}

int kruskal::find_node(int n)
{
    for(int i=1;i<=noe;i++)
    {
        for(int j=1;j<=top[i];j++)
        {
        if(n==sets[i][j])
            return i;
        }
    }

    return -1;
}


int main(int argc, char *argv[])
{
    kruskal obj;
    obj.read_graph();
    obj.sort_edges();
    obj.algorithm();

    system("PAUSE");
    return EXIT_SUCCESS;
}

Hasil Running

Referensi

http://eprints.uny.ac.id/28787/2/c.BAB%20II.pdf

https://www.academia.edu/5508323/Makalah_graph

http://dinus.ac.id/repository/docs/ajar/TREE_-_Struktur_Data.pdf

dina_indarti.staff.gunadarma.ac.id/Downloads/files/46268/Pohon.pdf

Read More →

Algoritma Bubble Sort dan Quick Sort pada C++

Bubble Sorting

Algoritma Bubble Sorting

Bubble sort atau yang disebut dengan metode gelombang adalah metode mengurutkan data dengan cara membandingkan masing-masing elemen kemudian menukarkannya jika perlu. Penukaran data ini dilakukan terus-menerus sampai data terurut dan tidak ada perubahan. 

Metode ini terinspirasi dari gelembung sabun yang berada di permukaan air. Pada dasarnya berat jenis gelembung sabun lebih ringan dari berat jenis air, maka gelembung sabun akan mengapung di atas permukaan air. 

Kelebihan metode bubbe sort yaitu metode ini sederhana dan mudah dipahami, namun metode ini adalah metode yang tidak efisen pada saat mengurutkan data yang sangat besar maka akan mengalami kelambatan dan kinerja memburuk yang cukup signifikan.

Algoritma ini termasuk dalam algoritma comparison sort karena menggunakan perbandingan antar elemen. 

Algoritma bubble sort yaitu:

a. Menbandingkan data ke-1 dengan data ke-(i+1). Apabila tidak sesuai (data ke-i > data ke(i+1) atau data ke-i < data ke(i+1)) maka akan terjadi pertukaran data (data ke-1 = data ke-(i+1) dan data ke-(i+1) = data ke-1). 

b. Membandingkan data ke (i+1) dengan data ke-(i+2) dan seterusnya.

c. Selesai membandingkan satu iterasi antara (n-1) dengan n maka program akan melanjutkan ke iterasi berikutnya yaitu (n-1) sampai dengan seterusnya.

d. Proses akan berhenti apabila tidak ada pertukaran dalam satu iterasi.

Berikut adalah contoh algotitma bubble sort yaitu:

Proses yang akan terjadi apabila mengurutkan data " 4  2  5  3  9 " menggunakan algoritma bubble sort adalah sebagai berikut.

Pass pertama

4  2  5  3  9  menjadi  2  4  5  3  9

2  4  5  3  9  menjadi  2  4  5  3  9

2  4  5  3  9  menjadi  2  4  3  5  9

2  4  3  5  9  menjadi  2  4  3  5  9

Pass kedua

2  4  3  5  9  menjadi  2  4  3  5  9

2  4  3  5  9  menjadi  2  3  4  5  9

2  3  4  5  9  menjadi  2  3  4  5  9

2  3  4  5  9  menjadi  2  3  4  5  9 

Pass kedua

2  3  4  5  9  menjadi  2  3  4  5  9

2  3  4  5  9  menjadi  2  3  4  5  9

2  3  4  5  9  menjadi  2  3  4  5  9

2  3  4  5  9  menjadi  2  3  4  5  9

Contoh Program

#include <iostream>
#include <conio.h>

using namespace std;

int main()
{
   int i,j,n,data[10],simpan,k;
   cout<<"\tBUBBLE SORT MENGGUNAKAN  C++"<<endl;
   cout<<"\t============================"<<endl;
   cout<<"\nmasukkan banyak data= ";cin>>n;
   for(i=1;i<=n;i++)
{
    cout<<"data "<<i<<" = ";cin>>data[i];
}
   cout<<"awal = ";
   for(i=1;i<=n;i++)
   cout<<data[i]<<" ";
   cout<<endl;
   for(i=1;i<n;i++)
{
    for(j=1;j<n;j++)
{
            if(data[j]>data[j+1])
{
            simpan=data[j];
            data[j]=data[j+1];
            data[j+1]=simpan;
       }
    }
}
   cout<<"hasil= ";
   for(i=1;i<=n;i++)
    cout<<data[i]<<" ";
getch();
}

Hasil Running:

Quick Sort

Algoritma Quick Sort

Quick sort adalah metode pengurutan cepat yang memiliki efektifitas tinggi dengan menukarkan dua elemen dengan jarak yang cukup besar. Pengurutan cepat ini membandingkan suatu elemen (pivot) dengan elemen lain sehingga elemen lin yang lebih kecil dari pivot  maka akan terjadi pertukaran antara elemen sebelah kiri pivot fan elemen lain yang besar dari pivot terletak disebelah kanan. 

Pada algoritma quick sort, pemilihan sort ialah hal yang paling menentukan. Apakah akan memberikan performa yang baik atau buruk.

Berikut cara pemilihan pivot:

1. Pivot merupakan elemen tengah dalam array. Cara ini bagus pada tabel acak namun tidak bagus pada tabel yang sudah terurut.

2. Pivot dipilih acak dari salah satu elemen array. 

3. Pivot adalah elemen median tabel. Cara ini yaitu cara yang paling bagus, sebab hasil pembagian partisi pada tabel seimbang. Juga cara ini memberikan kompleksitas waktu yang minimum.

Contoh Program

#include <stdio.h>

#include <stdlib.h>

#define MAX 10

int Data[MAX];

// Prosedur menukar data

void Tukar (int *a, int *b)

{

 int temp;

 temp = *a;

 *a = *b;

 *b = temp;

} // Prosedur pengurutan metode Quick Sort

void QuickSortRekursif(int L, int R)

{

 int i, j, x;

 x = Data[(L+R)/2];

 i = L;

 j = R;

 while (i <= j){

 while(Data[i] < x)

 i++;

 while(Data[j] > x)

 j--;

 if(i <= j){

 Tukar(&Data[i], &Data[j]);

 i++;

 j--;

 }

 }

 if(L < j)

 QuickSortRekursif(L, j);

 if(i < R)

 QuickSortRekursif(i, R);

}

int main()

{

 int i;

 srand(0);

// Membangkitkan bilangan acak

 printf("DATA SEBELUM TERURUT");

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

 {

 Data[i] = (int) rand()/1000+1;

 printf("\nData ke %d : %d ", i, Data[i]);

 }

 QuickSortRekursif(0, MAX-1);

 // Data setelah terurut

 printf("\nDATA SETELAH TERURUT");

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

 {

 printf("\nData ke %d : %d ", i, Data[i]);

 }

}

Hasil Running:

Referensi

http://yuliana.lecturer.pens.ac.id/Struktur%20Data%20C/Prak%20SD%20-%20pdf/Praktikum%208.pdf

https://docplayer.info/50754841-Analisis-algoritma-bubble-sort.html

https://www.academia.edu/17143309/Struktur_Data_-_SORTING_PENGURUTAN_

http://yuliana.lecturer.pens.ac.id/Struktur%20Data%20C/Prak%20SD%20-%20pdf/Praktikum%209.pdf

https://www.academia.edu/10450333/Laporan_Quick_Sort

https://www.academia.edu/10072435/metode_Quick_Sort_C_

Read More →