Struktur Data Graph

Struktur Data Graph

Graf adalah salah satu jenis struktur data yang terdiri dari titik(vertex) dan garis(edge), dimana dalam graf tersebut, vertex - vertex yang ada dihubungkan oleh edge, hingga menjadi suatu kesatuan yang disebut graf. Sebagai contoh dari pemodelan graf adalah peta kota kota, dimana kota disini sebagai vertex dan jalur yang menghubungkannya berlaku sebagai edge. Agar lebih jelas perhatikan gambar dibawah ini :

Dalam gambar tersebut, terdapat beberapa kota yang berada dipulau jawa dimana kota kota tersebut dihubungkan oleh beberapa jalur - jalur yang ada. Untuk contoh diatas kita bisa menganggap bawah kota kota yang ada merupakan vertex, dan jalur jalur yang menghubungkan kota kota tersebut sebagai edge. Sehingga secara keseluruhan peta diatas dapat dibuat pemodelannya sebagai sebuah graf.

Ada terdapat beberapa jenis graf yang bisa kita gunakan, yaitu beberapa diantaranya adalah sebagai berikut :

1.     Graf Berarah

 adalah graf yang edge-nya memiliki arah, sebagai contoh edge AB menghubungkan vertex A ke B, dimana hubungan vertex B ke A, harus diperoleh dari edge lain, yaitu edge BA, dan jika edge BA tidak ada, maka vertex B ke A tidak memiliki hubungan, meski vertex A ke B memiliki hubungan.

2.     Graf Tak Berarah

adalah graf yang edge-nya tidak memiliki arah, sehigga jika edge AB menghubungkan vertex A ke B, maka secara otomatis juga menghubungkan vertex B ke A.

3.     Graf Berbobot

adalah suatu graf dimana edge dari graf tersebut memiliki bobot atau nilai tertentu.

4.     Graf Berbobot

adalah suatu graf dimana edge dari graf tersebut tidak memiliki bobot atau nilai.

Untuk merepresentasikannya dalam pemrograman komputer, graf dapat disusun dari LinkedList yang berada dalam LinkedList. Perhatikan contoh graf berarah dibawah ini :

Graf tersebut dapat direpresentasikan dalam sebuah matrik 5x5 , dimana baris dan kolom di matriks tersebut menunjukan vertex yang ada.

Operasi pada Graph

---> G1 U G2

----> G1 n G2

-----> G1 - G2











---> G2 - G1

Stack (Tumpukan)

Apa itu STACK ??

Stack merupakan bentuk khusus dari suatu struktur data, dimana node yang ditambahkan ke dalam list dan diambil dari list hanya pada 'kepala'nya, atau dengan kata lain prinsip pengolahannya adalah last-in first-out (LIFO).

data yang terakhir kali dimasukkanakan pertama kali keluar dari stack tersebut. Stack dapat diimplementasikan sebagai representasi berkait atau kontigu (dengan tabel fix). Ciri Stack :

1. Elemen TOP (puncak) diketahui

2. penisipan dan penghapusan elemen selalu dilakukan di TOP

3. LIFO (Last In First Out)

 LIFO

 Jika ingin mengambil 90, maka harus melakukan

pop untuk 37 dan 12 terlebih dahulu ke mudian

pop untuk 90.

Lalu jika ingin 90 tetap ada, maka harus

melakukan push untuk 90, kemudian push untuk

12 dan 37.

Data hanya bisa diambil secara berurutan, tidak

bias diambil secara langsung

pekerjaan pada komputer diolah berdasarkan pengalamatan-pengalamatan yang diatur sedemikian rupa. Begitu juga saat terjadi suatu interrupt. Saat komputer menyelesaikan suatu interrupt yang ditemukannya, maka komputer kembali melacak pekerjaan sebelumnya. Informasi pengalamatan tentang pekerjaan sebelumnya tadi disimpan dalam suatu register khusus yang dikenal sebagai sebuah stack.

Ilustrasi STACK (tumpukan)

kita mempunyai dua buah kotak yang kita tumpuk, sehingga kotak kita letakkan di atas kotak yang lain. Jika kemudian tumpukan dua buah kotak itu kita tambah dengan kotak ketiga, keempat dan seterusnya, maka akan kita peroleh sebuah tumpukan kotak, yang terdiri dari N kotak.

Contohnya kita menumpuk Compo di posisi terakhir, maka Compo akan menjadi elemen  teratas dalam tumpukan. Sebaliknya,  karena kita menumpuk Televisi pada saat  pertama kali, maka elemen Televisi menjadi elemen terbawah dari tumpukan. Dan jika  kita mengambil elemen dari tumpukan,  maka secara otomatis akan terambil elemen teratas, yaitu Compo juga.

Dengan demikian, pada stuktur ini hanya ada dua fungsi utama, yaitu push (memasukkan node/data ke dalam stack), dan pop (mengambil node/data dari stack). 

Underflow (kekurangan data) yang diakibatkan pengambilan data sedangkan tong stack sudah kosong.

OverFlow (kelebihan data) yang diakibatkan oleh penambahan data dimana tong stack sudah penuh.

Operasi-operasi/fungsi Stack

- Push : digunakan untuk menambah item pada stack pada tumpukan paling atas
- Pop : digunakan untuk mengambil item pada stack pada tumpukan paling atas
- Clear : digunakan untuk mengosongkan stack
- IsEmpty : fungsi yang digunakan untuk mengecek apakah stack sudah kosong
- IsFull : fungsi yang digunakan untuk mengecek apakah stack sudah penuh

OPERASI PUSH (menambah data)

OPERASI POP (mengambil data)

  

OPERASI PUSH DAN POP

CONTOH PEMANFAATAN STACK

Pemanfaatan stack antara lain untuk menulis ungkapan dengan menggunakan notasi tertentu.
Contoh :
( A + B ) * ( C – D )
Tanda kurung selalu digunakan dalam penulisan ungkapan numeris untuk mengelompokkan bagian mana yang akan dikerjakan terlebih dahulu.
Dari contoh ( A + B ) akan dikerjakan terlebih dahulu, kemudian baru ( C– D ) dan terakhir hasilnya akan dikalikan.
A + B * C – D
B * C akan dikerjakan terlebih dahulu, hasil yang didapat akan berbeda dengan hasil notasi dengan tanda kurung

KESIMPULAN

Pada “STACK” Data hanya bisa diambil secara berurutan, tidak bisa diambil secara langsung. Hal ini berbeda dengan sistem yang ada pada “LINKED LIST” dimana data dapat diambil secara acak, bisa di tengah, di atas atau di akhir, bahkan dapat data dapat langsung dihapus.

Sorting (Pengurutan Data)

Pengurutan data dalam struktur data sangat penting untuk data yang beripe data numerik ataupun karakter. Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun).

Pengurutan (Sorting) adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu.

Contoh:

Data Acak : 5 6 8 1 3 25 10

Ascending : 1 3 5 6 8 10 25

Descending : 25 10 8 6 5 3 1

Metode Pengurutan Data, antara lain:

1. Pengurutan berdasarkan perbandingan (comparison-based sorting) mis: Bubble sort, exchange sort
2. Pengurutan berdasarkan prioritas (priority queue sorting method) mis: Selection sort, heap sort
3. Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and keep sorted method) mis: Insertion sort, tree sort
4. Pengurutan berdasarkan pembagian dan penguasaan (devide and conquer method) mis: Quick sort, merge sort
5. Pengurutan berkurang menurun (diminishing increment sort method) mis: Shell sort

Bubble Sort

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

• Pengurutan Ascending :Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar.
• Pengurutan Descending: Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar.
• 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 dari 0 sampai dengan iterasi sebanyak n-1.
• Kapan berhentinya?  Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.

Contoh Bubble Sort

Contoh Bubble Sort dalam Coding

void bubble_sort(){

    for(int i=1;i<n;i++){

      for(int j=n-1;j>=i;j--){

        if(data[j]<data[j-1]) tukar(&data[j],&data[j-1]); //ascending

      }

    }

  } 

Dengan prosedur diatas,  data terurut naik (ascending),  untuk  urut turun (descending) silahkan ubah bagian:

  If (data[j]<data[j-1]) tukar(&data[j],&data[j-1]);

Menjadi:

  If (data[j]>data[j-1]) tukar(&data[j],&data[j-1]);

--> Buble sort paling mudah algoritmanya tetapi paling lambat dibandingkan algoritma lain

  

Exchange Sort

• Sangat mirip dengan Bubble Sort
• Banyak yang mengatakan Bubble Sort sama dengan Exchange Sort
• Pebedaan : 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 tersebut itu akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi, begitu seterusnya.

Contoh Exchange Sort

Contoh Coding Exchange Sort

  void exchange_sort()
{     

  for (int i=0; i<n-1; i++){
     for(int j = i+1; j<n; j++){
          if (data [i] < data[j])   tukar(&data[i],&data[j]);
     }

  }

  }

Selection Sort

• Merupakan kombinasi antara sorting dan searching
• Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array.
• Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]).
• Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.

Contoh Selection Sort

Contoh Coding Selection Sort

  Void selection_sort(){

    For(int i=0;i<n-1;i++){

      pos = i;

      For(int j=i+1;j<n;j++){

        If(data[j] < data[pos]) pos = j; //ascending     

      }    

      If(pos != i) tukar(&data[pos],&data[i]);

    }

  }

Insertion Sort

• Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya.
• Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya.
• Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang 

Contoh Insertion Sort

Contoh Coding Insertion Sort

void insertion_sort(){

  int temp;

  for(int i=1;i<n;i++){

    temp = data[i];

    j = i -1;

    while(data[j]>temp && j>=0){

      data[j+1] = data[j];

      j--;

    }

    data[j+1] = temp;

  }  

} 

Tabel Perbandingan Kecepatan Metode Pengurutan Data

 

 

Pengantar Struktur Data
Bersama Soryanto Tay

Struktur data adalah cara menyimpan atau merepresentasikan data di dalam komputer agar bisa dipakai secara efisien. Sedangkan data adalah representasi dari fakta dunia nyata. Fakta atau keterangan tentang kenyataan yang disimpan, direkam atau direpresentasikan dalam bentuk tulisan, suara, gambar, sinyal atau symbol.

Secara garis besar type data dapat dikategorikan menjadi :

1. Type data sederhana, di mana type data sederhana juga terbagi menjadi:

   a. Type data sederhana tunggal, misalnya Integer, real, boolean dan karakter

   b. Type data sederhana majemuk, misalnya String

2. Struktur Data, meliputi

   a. Struktur data sederhana, misalnya array dan record  
   b. Struktur data majemuk, yang terdiri dari

       - Linier : Stack, Queue, serta List dan Multilist

       - Non Linier : Pohon Biner dan Graph

Pemakaian struktur data yang tepat di dalam proses pemrograman akan menghasilkan algoritma yang lebih jelas dan tepat, sehingga menjadikan program secara keseluruhan lebih efisien dan sederhana.

Struktur data yang ″standar″ yang biasanya digunakan dibidang informatika adalah :

• Sorting (Pengurutan Data)
• List linier (Linked List) dan variasinya
• Stack (Tumpukan)
• Queue (Antrian)
• Tree ( Pohon )
• Graph ( Graf )