Algoritma Pemrograman : Graph dan Pohon

Graph

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 dari graph 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 memanipulasi 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.

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

b.    Graph berarah (directed graph) :

-          Urutan simpul mempunyai arti. Misal busur AB adalah e1 sedangkan busur BA adalah e8.

c.     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.

Istilah – istilah dalam Graph :

Terdapat istilah – istilah yang berkaitan dengan graph, yaitu : 

a. Vertex

Vertex adalah himpunan node/titik pada sebuah graph.

b.       Edge

Edge adalah garis yang menghubungkan tiap node/vertex.

c.        Adjacent

Adjacent adalah dua buah titik dikatakan berdekatan juka dua buah titik tersebut terhubung dengan sebuah sisi.

d.       Weight

Sebuah graph dikatakan berbobot apabila terdapat sebuah fungsi bobot bernilai real pada himpunan Edge.

e.       Path

Path adalah walk dengan setiap vertex berbeda. Walk didefinisikan sebagai ururtan vertex dan edge. Diawali dengan origin vertex dan diakhiri dengan terminus vertex.

f.         Cycle

Cycle adalah siklus atau sirkuit yang berawal dan berakhir pada simpul yang sama.

Contoh program :

#include <stdfix.h>

#include <stdio.h>

#include <iostream>

#include <stdlib.h>

using namespace std;

int ordo[5][5];

void masukkan(int a, int b, int c)

{

    for (int i = 1; i <= 4; i++)

        {

            for (int j = 1; j <= 4; j++)

            if (i == a && j == b)

            {

                ordo[a][b] = ordo[i][j];

                ordo[a][b] = c;

            }

        }

}

void tampilkan(int a, int b, int c)

{

    for (int i = 1; i <= 4; i++)

        {

            for (int j = 1; j <= 4; j++)

            cout << ordo[i][j] << " ";

            cout << endl;

        }

}

void inisialisasi()

{

    for (int i = 1; i <= 4; i++)

    {

            for (int j = 1; j <= 4; j++)

            ordo[i][j] = 0;

    }

}

void menu()

{

 cout << "-----------------MENU-----------------\n";

 cout << "1. Masukkan Data\n";

 cout << "2. Tampilkan\n";

 cout << "0. Keluar\n";

 cout << "Masukkan Pilihan Anda: ";

}

int main()

{

    inisialisasi();

    int a, b, c;

    int m;

    do

        {

            system("cls");

            menu();cin >> m;

            switch (m)

            {

                case 1:

                    cout << "\nMasukkan Koordinat x : ";    cin >> a;

                    cout << "Masukkan Koordinat y : ";    cin >> b;

                    cout << "Masukkan Isi : ";    cin >> c;

                    if (a <= 4 && b <= 4)

                        {

                            masukkan(a, b, c);

                        }

                    else

                    {

                            cout << "\nIndeks harus kurang dari 4\n";

                    }

                    break;

                    system("pause");

                    case 2:

                        system("cls");

                        tampilkan(a, b, c);

                        break;

                        system("pause");

            }

        system("pause");

    }

    while (m != 0);

}

Hasil Running :

Pohon

     Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya. Tree juga adalah suatu graph yang acyclic, simple, connected yang tidak mengandung loop.

      Sebuah binary search tree (bst) adalah sebuah pohon biner yang boleh kosong, dan setiap nodenya harus memiliki identifier/value. Value pada semua node subpohon sebelah kiiri adalah selalu lebih kecil dari value dari root, sedangkan value subpohon di sebelah kanan adalah sama atau lebih besar dari value pada root, masing-masing subpohon tersebut (kiri dan kanan) itu sendiri adalah juga binary search tree. Struktur data bst sangat penting dalam struktur pencarian, misalkan dalam kasus pencarian dalam sebuah list, jika list sudah dalam keadaan terurut maka proses pencarian akan semakin cepat, jika kita menggunakan  list contigue dan melakukan pencarian biner, akan tetapi  jika kita ingin melakukan perubahan isi list (insert atau delete), menggunakan list contigue akan sangat lambat, karena prose insert dan delete dalam list contigue butuh memindahkan linked-list, yang untuk operasi insert atau delete tinggal mengatur- atur pointer, akan tetapi pada n-linked list, kita tidak bisa melakukan pointer sembarangan setiap saat, kecuali hanya satu kali dengan kata lain hanya secara squential.

            Istilah – istilah di dalam Tree :

Berikut ini merupakan istilah yang berhubungan dengan tree.

1.         Predesesor

Node yang berada diatas node tertentu.  (contoh :  B predesesor dari E dan F) 

2.         Succesor

Node yang berada dibawah node tertentu. (contoh :  E dan F merupakan succesor dari B)

3.         Ancestor

Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.  (contoh :  A dan B merupakan ancestor dari F)

4.         Descendant

Seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.  (contoh :  F dan B merupakan ancestor dari A)

5.         Parent

Predesesor satu level diatas satu node. (contoh : B merupakan parent dari F)

6.         Child

Succesor satu level dibawah satu node. (contoh : F merupakan child dari B)

7.         Sibling 

Node yang memiliki parent yang sama dengan satu node (contoh : E dan F adalah sibling)

8.         Subtree

Bagian dari tree yang berupa suatu node beserta descendant-nya (contoh : Subtree B, E, F dan Subtree  D, G, H)

9.         Size

Banyaknya node dalam suatu tree (contoh : gambar tree diatas memiliki size = 8)

10.     Height

Banyaknya tingkat/level dalam suatu tree (contoh : gambar tree diatas memiliki height = 3)

11.     Root (Akar)

Node khusus dalam tree yang tidak memiliki predesesor (Contoh : A)

12.     Leaf (Daun)

Node-node dalam tree yang tidak memiliki daun (contoh : Node E,F,C,G,H)

13.     Degree (Derajat)

Banyaknya child yang dimiliki oleh suatu node (contoh : Node A memiliki derajat 3, node B memiliki derajat 2)

Contoh Program

#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][100];

    int tree[100][100];

    int sets[100][100];

    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 bandara : ";

cin>>n;

noe=0;

cout<<"\nJarak antar tiap bandara:\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;

            }

        }

        cout << endl;

    }

}

void kruskal::sort_edges()

{

/** Sort the edges using bubble sort in increasing order******/

for(int i=1;i<=noe-1;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

Algoritma Pemrograman : Sorting (Bubble & Quick Method)

Quick Sorting

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.

Algoritma ini mengambil salah satu elemen secara acak (biasanya dari tengah) yang disebut dengan pivot lalu menyimpan semua elemen yang lebih kecil di sebelah kiri pivot dan semua elemen yang lebih besar di sebelah kanan pivot. Hal ini dilakukan secara rekursif terhadap elemen di sebelah kiri dan kanannya sampai semua elemen sudah terurut.

Algoritma Quick Sort.

Pilih satu elemen secara acak sebagai pivot

Pindahka 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.

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

Proses pengurutan Quick Sort adalah sebagai berikut :

Proses pengurutan berhenti bila pointer kiri overlap dengan pointer kanan (langkah 8 di gambar atas), sekaligus membagi (divide) 2 bagian yang akan diurutkan selanjutnya; yaitu partisi kiri dan kanan.

Proses pengurutan dilakukan sama dengan langkah sebelumnya (rekursif) dan dilakukan pada partisi kiri dan kanan. Pembagian partisi berhenti bila tiap partisi hanya menyisakan satu elemen data saja (lihat warna hijau pada langkah 4 di atas).

Ketika proses pengurutan dilakukan secara rekursif (berulang), maka menghasilkan partisi hanya satu elemen saja dan kemudian digabung kembali sehingga terlihat bahwa data telah berurutan. Untuk lebih jelasnya, anda bisa memahami proses sorting dengan membaca Algoritma Quick Sort di bawah ini :

Contoh program dalam wujud berbeda :

#include <iostream>

using namespace std;

void quick_sort(int[],int,int);
int partition(int[],int,int);

int main()
{
    int n,i;
    n =7;
   int a[]={9,4,2,7,10,1,5};
    cout<<"\nData sebelum pengurutan:\n";
 
    for(i=0;i<n;i++)
        cout<<a[i]<<" , ";
     
    quick_sort(a,0,n-1);
    cout<<"\nData setelah dilakukan quick sort:\n";
 
    for(i=0;i<n;i++)
        cout<<a[i]<<" , ";
 
    return 0;     
}

void quick_sort(int a[],int l,int u)
{
    int j;
    if(l<u)
    {
        j=partition(a,l,u);
        quick_sort(a,l,j-1);
        quick_sort(a,j+1,u);
    }
}

int partition(int a[],int l,int u)
{
    int v,i,j,temp;
    v=a[l];
    i=l;
    j=u+1;
 
    do
    {
        do
            i++;
         
        while(a[i]<v&&i<=u);
     
        do
            j--;
        while(v<a[j]);
     
        if(i<j)
        {
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
    }while(i<j);
 
    a[l]=a[j];
    a[j]=v;
 
    return(j);
}

Hasil running :

Bubble Sorting

Algoritma Bubble Sort merupakan proses pengurutan yang secara berangsur-angsur memindahkan data ke posisi yang tepat. Karena itulah, algoritma ini dinamakan “bubble” atau yang jika diterjemahkan ke dalam Bahasa Indonesia, artinya yaitu gelembung. Fungsi algoritma ini adalah untuk mengurutkan data dari yang terkecil ke yang terbesar (ascending) atau sebaliknya (descending).

Metode pengurutan gelembung (Bubble Sort) ini terinspirasi oleh gelembung sabun yang berada di permukaan air. Karena berat jenis gelembung sabun yang lebih ringan ketimbang berat jenis air, maka gelembung sabun akan selalu terapung ke atas permukaan. Prinsip inilah yang dipakai pada algoritma pengurutan gelembung.

Secara sederhana, bisa didefinisikan bahwa algoritma Bubble Sort adalah pengurutan dengan cara pertukaran data dengan data di sebelahnya secara terus menerus sampai pada satu iterasi tertentu dimana tidak ada lagi perubahan yang signifikan.

Sebelum kita masuk untuk membuat program, berikut ini adalah syarat dan langkah-langkah yang harus diperhatikan pada metode Bubble Sort:

Jumlah iterasi sama dengan banyaknya bilangan dikurang 1.

Di setiap iterasi, jumlah pertukaran bilangannya sama dengan jumlah banyaknya bilangan.

Dalam algoritma Bubble Sort, meskipun deretan bilangan tersebut sudah terurut, proses sorting akan tetap dilakukan.

Tidak ada perbedaan cara yang berarti untuk teknik algoritma Bubble Sort Ascending dan Descending.

Untuk mempelajari algoritma Bubble Sort ini, Anda hanya perlu memahami cara yang digunakan untuk mengurutkan data. Logika sederhananya, algoritma ini menggunakan perbandingan dalam operasi antar elemennya. Kita simak salah satu contoh di bawah ini, yang merupakan gambaran dari penerapan algoritma Bubble Sort dengan array “3 1 4 2 8”.

Proses pertama:

(3 1 4 2 8) menjadi (1 3 4 2 8)

(1 3 4 2 8) menjadi (1 3 4 2 8)

(1 3 4 2 8) menjadi (1 3 2 4 8)

(1 3 2 4 8) menjadi (1 3 2 4 8)

Proses kedua:

(1 3 2 4 8) menjadi (1 3 2 4 8)

(1 3 2 4 8) menjadi (1 2 3 4 8)

(1 2 3 4 8) menjadi (1 2 3 4 8)

(1 2 3 4 8) menjadi (1 2 3 4 8)

Proses ketiga:

(1 2 3 4 8) menjadi (1 2 3 4 8)

(1 2 3 4 8) menjadi (1 2 3 4 8)

(1 2 3 4 8) menjadi (1 2 3 4 8)

(1 2 3 4 8) menjadi (1 2 3 4 8)

    Jika diperhatikan proses yang terjadi di atas, ketika proses kedua data di dalam array sudah terurut dengan benar. Tetapi, algoritma Bubble Sort akan terus berjalan hingga proses kedua berakhir. Proses ketiga ini akan terus berjalan, karena pada algoritma Bubble Sort, yang dimaksud “data sudah terurut” adalah tidak ada satupun pertukaran data pada suatu proses. Proses ketiga ini dimaksudkan untuk verifikasi data.

    Algoritma Bubble Sort ini mempunyai kelebihan dan kekurangan. Dua hal inilah yang menjadi pertimbangan programmer ketika membuat program. Berikut ini beberapa kelebihan yang dimiliki oleh algoritma ini :

1. Algoritma ini adalah metode paling sederhana untuk mengurutkan data.

2. Selain sederhana, algoritma ini juga mudah dipahami.

3. Sedangkan, kekurangan dari algortima ini adalah sebagai berikut:

    Tingkat efisiensinya yang kurang. Bubble Sort ini merupakan metode pengurutan yang tidak efisien, khususnya ketika menangani data yang berjumlah besar. Hal tersbeut karena ketika mengurutkan data yang sangat besar akan sangat lambat prosesnya.

Jumlah pengulangan yang dilakukan oleh algortima ini akan tetap sama jumlahnya, meskipun data yang diurutkan sudah cukup terurut.

    Bubble sort (metode gelembung) adalah metode/algoritma pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat. Artinya Algoritma ini akan menggeser  nilai yang terkecil atau terbesar (sesuai dengan jenis pengurutan, ascending atau descending) ke posisi ujung dari daftar. Demikian seterusnya hingga semua daftar dalam keadaan terurut. Proses dasar yang terjadi dalam algoritma ini adalah proses pertukaran nilai (swapping). 

Contoh syntax program :

#include<iostream>

using namespace std;

main()
{
    int i,j,n,data[100],save,k;
    cout<<" Masukkan banyak data : ";cin>>n;
    for(i=1;i<=n;i++)
    {
        cout<<" Data "<<i<<" : ";cin>>data[i];
    }
    cout<<" Awal : "<<endl;
    for(i=1;i<=n;i++)
        cout<<data[i]<<" "<<endl;
    for(i=1;i<n;i++)
    {
        for(j=1;j<n;j++)
        {
            if(data[j]>data[j+1])
            {
                save=data[j];
                data[j]=data[j+1];
                data[j+1]=save;
            }
        }
    }
    cout<<" Hasilnya : "<<endl;
    for(i=1;i<=n;i++)
        cout<<data[i]<<" ";
}

Hasil running program :