TREE DAN GRAPH

A.       Graph

Menurut Foulds (1994) graf 𝐺 adalah pasangan terurut (𝑉,𝐸) dimana 𝑉 adalah himpunan simpul yang berhingga dan tidak kosong. Dan E adalah himpunan sisi yang merupakan pasangan yang tidak terurut dari simpul (𝑖,𝑗) dimana (𝑖,𝑗) ∈𝑉. Elemen 𝑉 dinamakan simpul (node) dan elemen 𝐸 dinamakan sisi (edge), dinotasikan sebagai (𝑖,𝑗), yaitu sisi yang menghubungkan simpul 𝑖 dengan simpul 𝑗, dengan (𝑖,𝑗)∈𝑉(Foulds, 1994).
Berdasarkan orientasi arah pada suatu graf, maka graf digolongkan menjadi dua jenis, yaitu graf tak berarah (undirected graph) dan graf berarah (directed graph) (Munir, 2010). Graf yang sisinya tidak mempunyai orientasi arah disebut dengan graf tak berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Jadi (𝑖,𝑗)=(𝑗,𝑖) adalah sisi yang sama. Sisi pada graf ini dinamakan edge. Sedangkan Graf yang setiap sisinya diberikan orientasi arah dinamakan graf berarah. Sisi berarah pada graf ini dinamakan arc. Pada graf ini belum tentu (𝑖,𝑗)=(𝑗,𝑖) bisa saja (𝑖,𝑗)≠(𝑗,𝑖).

1.         Graf Siklus (Cycle) Atau Sirkuit (Circuit)

Suatu lintasan yang berawal dan berakhir disimpul yang sama dinamakan siklus atau sirkuit (Munir, 2012). Pada gambar berikut siklus atau sirkuit terdapat pada 2,4,3,2.

2.         Graf Berbobot

Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga atau bobot. Bobot pada setiap sisi dapat berbeda-beda bergantung pada masalah yang dimodelkan dengan graf. Bobot dapat menyatakan jarak antara dua buah kota, biaya perjalanan antara dua buah kota, waktu tempuh pesan (message) dari sebuah simpul komunikasi ke simpul komunikasi lain (dalam jaringan komputer), ongkos produksi, dan sebagainya (Latifah, 2014).

B.       Pohon (tree)

Pohon dalam teori graf adalah sebuah graf yang mempunyai 𝑛 buah titik, 𝑛−1 sisi dan tidak mempunyai lintasan (path) serta merupakan graf terhubung. Suatu pohon titik yang berderajat 1 dinamakan daun (leaf) atau titik terminal (terminal vertex), sedangkan titik yang berderajat lebih dari 1 disebut titik cabang (branch vertex) atau titik internal (internal vertex) (Wibisono, 2008: 159).

1.         Pohon Merentang (Spanning Tree)

Pohon perentang suatu graf terhubung 𝐺 adalah suatu subgraf 𝐺 yang merupakan pohon dan memuat semua titik dalam 𝐺 (Siang, 2009: 286). Berikut gambar graf lengkap dengan empat buah pohon perentang.

2.         Pohon Merentang Minimum (Minimum Spanning Tree)

Jika 𝐺 adalah graf berbobot, maka bobot perentang 𝑇 dari 𝐺 didefenisikan dengan jumlah bobot semua sisi di 𝑇. Pohon perentang yang berbeda mempunyai bobot yang berbeda pula. Diantara semua pohon perentang di 𝐺, pohon perentang yang berbobot minimum dinamakan pohon merentang minimum (minimum spanning tree) (Munir, 2005). Pada gambar berikut G adalah graf berbobot, 𝑇1 dan 𝑇2 adalah pohon merentang berbobot dari graf G.
C.       Contoh kasus Pendistribusian Obat ke Apotek-Apotek yang Ada di Kota Pelaihari
Di kota Pelaihari terdapat beberapa apotek yang memiliki jarak beragam antara satu dengan yang lainnya. Dalam pendistribusian obat-obatan, diperlukan jarak yang paling minimum untuk membantu proses pengiriman obat agar cepat dan menghemat waktu serta bahan bakar, sehingga pendistribusian obat menjadi lebih efisien.
Pencarian jarak terpendek untuk melakukan pendistribusian obat ke masing-masing apotik dapat dilakukan dengan menerapkan algoritma Dijkstra dan algoritma Kruskal.

D.       Algoritma Dijkstra
Algoritma Dijkstra dikstra ditemukan oleh Edsger.Wybe Dijkstra pada tahun 1959. Algoritma ini merupakan algoritma yang dapat memecahkan masalah pencarian jalur terpendek dari suatu graf pada setiap simpul yang bernilai tidak negatif. dijkstra merupakan algoritma yang termasuk dalam algoritma greedy, yaitu algoritma yang sering digunakan untuk memecahkan masalah yang berhubungan dengan suatu optimasi. Dalam pencarian jalur terpendeknya algoritma dijkstra bekerja dengan mencari bobot yang paling minimal dari suatu graf berbobot, jarak terpendek akan diperoleh dari dua atau lebih titik dari suatu graf dan nilai total yang didapat adalah yang bernilai paling kecil.
1.      Graf Algoritma Dijkstra

2.      Matriks Algoritma Dijkstra
0
1
2
3
4
5
6
7
8
9
10
11
0
0
255
0
0
0
0
0
0
1600
0
0
0
1
255
0
441
0
0
0
0
0
0
0
0
0
2
0
441
0
2760
0
0
0
0
1800
0
0
26
3
0
0
2760
0
7070
0
0
0
0
0
0
0
4
0
0
0
7070
0
5590
0
0
0
0
0
0
5
0
0
0
0
5590
0
1310
0
0
0
0
0
6
0
0
0
0
0
1310
0
656
0
1690
0
0
7
0
0
0
0
0
0
656
0
435
0
0
0
8
1600
0
1800
0
0
0
0
435
0
0
0
0
9
0
0
0
0
0
0
1690
0
0
0
20
0
10
0
0
0
0
0
0
0
0
0
20
0
30
11
0
0
26
0
0
0
0
0
0
0
30
0

3.         Program Algoritma Dijkstra
Berikut merupakan source code untuk algoritma Dijkstra, yaitu:
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#define INF 999
using namespace std;
int main()
{
    int n,i,j,start;
    printf("Masukan Jumlah Vertex : ");
    scanf("%d",&n);
    int G[n][n],tempGraf[n][n],jarak[n],visit[n],temp[n],count;
    printf("Masukan Matrix Graf : \n");
    for(i = 0;i < n ;i++)
    {
        for (j=0;j<n;j++)
        {
            cout<<"Matriks ["<<i<<"]["<<j<<"]: ";
            scanf("%d",&G[i][j]);
        }
    }
    printf("Masukan Vertex Asal : ");
    scanf ("%d",&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)
        {
            printf ("\nHasil jarak untuk vertex ke-%d adalah %d\n",i,jarak[i]);
            j=i;
             printf ("%d<-",i);
            while(j!=start)
            {
                j=temp[j];
                printf ("%d",j);
                if(j!=start)
                {
                    printf ("<-");
                }
            }
        }
    }
    printf ("\nTotal Jaraknya adalah %d\n",jarak[n-1]);
    return 0;
}

4.      Hasil Running Algoritma Dijkstra
E.       Algoritma Kruskal
Algoritma Kruskal merupakan salah satu algoritma dalam teori graf untuk menyelesaikan persoalan pohon merentang minimum. Pada Algoritma Kruskal, sisi-sisi didalam graf diurutkan terlebih dahulu berdasarkan bobotnya dari kecil ke besar.
1.           Graf Algoritma Kruskal
2.           Matriks Algoritma Kruskal
1
2
3
4
5
6
7
8
9
10
11
12
1
0
255
0
0
0
0
0
0
1600
0
0
0
2
255
0
441
0
0
0
0
0
0
0
0
0
3
0
441
0
2760
0
0
0
0
1800
0
0
26
4
0
0
2760
0
7070
0
0
0
0
0
0
0
5
0
0
0
7070
0
5590
0
0
0
0
0
0
6
0
0
0
0
5590
0
1310
0
0
0
0
0
7
0
0
0
0
0
1310
0
656
0
1690
0
0
8
0
0
0
0
0
0
656
0
435
0
0
0
9
1600
0
1800
0
0
0
0
435
0
0
0
0
10
0
0
0
0
0
0
1690
0
0
0
20
0
11
0
0
0
0
0
0
0
0
0
20
0
30
12
0
0
26
0
0
0
0
0
0
0
30
0

3.           Program Algoritma Kruskal

Berikut merupakan source code untuk algoritma Dijkstra, yaitu:
#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=0;

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-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;
}

4.           Hasil Running Algoritma Kruskal




Komentar

Posting Komentar