MATRIKS PENYAJIAN GRAPH

contoh bahwa G graf dengan N simpul dan M ruas. Untuk mempermudah komputasi, graf dapat disajikan dalam bentuk matriks, disebut Matriks Ruas, yang berukuran (2 x M) atau (M x 2) yang menyatakan ruas dari graf.

Matriks adjacency dari graf G tanpa ruas sejajar adalah matriks A
berukuran (N x N), yang bersifat :
     1, bila ada ruas (vi, vj)
a =
     0, dalam hal lain

Matriks adjacency merupakan matriks simetri.
Untuk graf dengan ruas sejajar, matriks adjacency didefinisikan
sebagai berikut :

        p, bila ada p buah ruas menghubungkan (vi, vj) (p > 0)
a =
       0, dalam hal lain



Matriks Incidence dari graf G, tanpa self-loop didefinisikan sebagai
matriks M berukuran (N x M)
      1, bila ruas ej berujung di simpul vi,
m =
      0, dalam hal lain

contoh :

klik untuk memperbesar gambar

GRAF BERARAH (DIGRAF)

Suatu graf berarah (digraf) D terdiri atas 2 himpunan :
1. Himpunan V, anggotanya disebut simpul
2. Himpunan A, merupakan  himpunan pasangan terurut, yang
disebut ruas berarah atau arkus.

Notasi : D(V, A)

Simpul, anggota v, digambarkan  sebagai titik (atau lingkaran
kecil). Sedangkan arkus a=(u,v), digambarkan  sebagai garis
dilengkapi dengan tanda panah mengarah dari simpul u ke simpul
v. Simpul u disebut titik pangkal, dan simpul v disebut titik terminal
dari arkus tersebut.

Read More..

GRAPH

Suatu graph mempunyai 2 himpunan :

♦ Himpunan V (Vertex) yang elemennya disebut simpul (atau
point atau node atau titik)
♦ Himpunan E (Edge) yang merupakan pasangan tak urut dari
simpul, anggotanya disebut ruas (rusuk atau sisi)

Notasi : G(V,E)

Simpul u dan v disebut berdampingan bila terdapat ruas (u,v).Graf dapat pula disajikan secara  geometrik, simpul disajikan sebagai sebuah titik, sedangkan  ruas disajikan sebagai sebuah garis yang menghubungkan 2 simpul.

Contoh 1 :

Graf G(V,E) dengan :
1. V terdiri dari 4 simpul, yaitu simpul A, B, C dan D
2. E terdiri dari 5 ruas, yaitu e1 = (A, B)    e2 = (B, C)    e3 = (A, D)
e4 = (C, D)    e5 = (B, D)

Banyak simpul disebut  ORDER,  banyak ruas disebut  SIZE  dari graf.

G R A P H   B E R L A B E L
 
Graf G disebut graf berlabel jika ruas dan atau simpulnya dikaitkan dengan suatu besaran tertentu. Jika setiap ruas e dari G dikaitkan dengan suatu bilangan non negatif d(e), maka d(e) disebut bobot
atau panjang dari ruas e.

 DERAJAT GRAF

Derajat simpul V, ditulis d(v) adalah banyaknya ruas yang menghubungi v. Karena  setiap ruas dihitung dua kali ketika menentukan derajat suatu graf, maka :
Jumlah derajat semua simpul suatu graf (derajat) = dua kali
banyaknya ruas graf (size graf).

Suatu simpul disebut genap/ganjil tergantung apakah derajat simpul tersebut genap/ganjil. Kalau terdapat self-loop, maka self-loop dihitung 2 kali pada derajat simpul. 

Contoh :  

Di sini banyaknya ruas = 7, sedangkan derajat masing-masing
simpul adalah : 

d(A) = 2  d(D) = 3  derajat graf G = 14
d(B) = 5  d(E) = 1  (2 * 7)
d(C) = 3  d(F) = 0

Catatan : E disebut simpul bergantung/akhir, yakni simpul yang
berderajat satu. Sedangkan F disebut simpul terpencil, yakni
simpul berderajat nol.

KETERHUBUNGAN

Walk  atau perjalanan dalam graf G  adalah barisan  simpul dan
ruas berganti-ganti : v1, e1, v2, e2, …, en-1, vn
Di sini ruas e1 menghubungkan simpul vi dan vI+1

Banyaknya ruas disebut panjang walk.
Walk dapat ditulis lebih singkat dengan hanya menulis deretan
ruas : e1, e2, …, en-1
atau deretan simpul : v1, v2, …, vn-1, vn
v1 disebut simpul awal, vn disebut simpul akhir

Walk disebut tertutup bila v1 = vn , dalam hal lain walk disebut
terbuka, yang menghubungkan v1 dan vn

Trail adalah walk dengan semua ruas dalam barisan berbeda.

Path atau  jalur adalah walk dengan semua simpul dalam barisan
berbeda. Jadi path pasti trail, sedangkan trail belum tentu path.

Dengan kata lain : Suatu path adalah suatu trail terbuka dengan
derajat setiap simpulnya = 2, kecuali simpul awal v1 dan vn simpul
akhir berderajat = 1.

Cycle atau sirkuit adalah suatu trail tertutup dengan derajat setiap
simpul = 2.

Read More..

SEARCHING

Searching adalah pencarian data dengan cara menelusuri data-data tersebut.Pada suatu data seringkali dibutuhkan pembacaan kembali informasi (retrieval information) dengan cara searching.empat pencarian data dapat berupa array dalam memori, bisa juga pada file pada external storage

Sequential Search

Adalah suatu teknik pencarian data dalam array ( 1 dimensi ) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu.

Kemungkinan terbaik (best case) adalah jika data yang dicari terletak di indeks array terdepan (elemen array pertama) sehingga waktu yang dibutuhkan untuk pencarian data sangat sebentar (minimal).Kemungkinan terburuk (worst case) adalah jika data yang dicari terletak di indeks array terakhir (elemen array terakhir) sehingga waktu yang dibutuhkan untuk pencarian data sangat lama (maksimal).

deklarasi dalam program c++

Binary Search

Adalah teknik pencarian data dalam dengan cara membagi data menjadi dua bagian setiap kali terjadi proses pencarian.Data yang ada harus diurutkan terlebih dahulu berdasarkan suatu urutan tertentu yang dijadikan kunci pencarian.

Prinsip pencarian biner adalah:

• Data diambil dari posisi 1 sampai posisi akhir N
• Kemudian cari posisi data tengah dengan rumus: (posisi awal
+ posisi akhir) / 2
• Kemudian data yang dicari dibandingkan dengan data yang di
tengah, apakah sama atau lebih kecil, atau lebih besar?
• Jika lebih besar, maka proses pencarian dicari dengan posisi
awal adalah posisi tengah + 1
• Jika lebih kecil, maka proses pencarian dicari dengan posisi
akhir adalah posisi tengah –1
• Jika data sama, berarti ketemu.

deklarasi dalam program c++ 

Read More..

SORTING

Sorting adalah proses menyusun elemen – elemen dengan tata urut tertentu dan
proses tersebut terimplementasi dalam bermacam aplikasi. Kita ambil contoh pada
aplikasi perbankan. Aplikasi tersebut mampu menampilkan daftar account yang aktif.
Hampir seluruh pengguna pada sistem akan memilih tampilan daftar berurutan
secara ascending demi kenyamanan dalam penelusuran data.

Beberapa macam algoritma sorting : selection sort,bubble sort,merge sort,quick sort,insertion sort,heap sort.

1.Selection sort



metode pengurutan selection sort,prosedur atau algorimatnya adalah sbb :


- pengecekan dimulai dari data ke -1 sampai dengan data ke -n

- tentukan bilangan dengan index terkecil dari data bilangan tersebut

- tukar bilangan dengan index terkecil tersebut dengan bilangan pertama (I= 1)dari bilangan tersebut

- lakukanlah langkah 2 dan 3 untuk bilangan berikut (I=I+1)sampai dapatkan urutan yang optimal



deklarasi dalam program c++ 

2.Bubble Sort



metode pengurutan buble sort,prosedur atau algorimatnya adalah sbb:


-.pengecekan dimulai dari data ke-1 sampai dengan data ke-n

- bandingkan data ke-n dengan data sebelumnya (n-1),jika lebih kecil maka tukar bilangan tersebut dengan data yang ada didepanya satu persatu (n-1,n-2,n-3,..dst)

- lakukan langkah ke 2 sampai mendapatkan urutan yang maksimal



deklarasi dalam program c++ 

3.Merge sort





metode pengurutan merge sort,prosedur atau algorimatnya adalah sbb:



- kelompokan 2 deret bilangan menjadi 2 bagian,4 bagian,8 bagian dst


- urutkan secara langsung bilangan dalam kelompok tersebut

- lakukanlah langkah diatas untuk kondisi bilangan yang lain sampai didapatkan urutan yang maksimal






deklarasi dalam program c++ 

4.Quick Sort






metode pengurutan Quick sort,prosedur atau algorimatnya adalah sbb:



- tentukan bilangan batas bawah (lower bound(I = 1)) dan tentukan bilangan batas atas (upper bound(I = N))


- syarat pemindahan adalah LB>UB


- Jika LB>UB lakukan pertukaran diantara dua bilangan tersebut


- lakukana langkah 2 dan langkah 3 untuk bilangan selanjutnya sampai mendapat urutan yang optimal






deklarasi dalam program c++ 

5.Insertion Sort






metode pengurutan insertion sort,prosedur atau algorimatnya adalah sbb:



- pengecekan dimulai dari data ke -1 sampai dengan data ke -n

- Pengurutan dilakukan dengan cara membandingkan data ke- 1


- Bandingkan data ke- 1 dengan data sebelumnya,jika lebih kecil data tersebut bisa


- lakukan langkah 2 dan 3 sampai mendapatkan urutan yang optimal





deklarasi dalam program c++ 

6.heap sort






metode pengurutan insertion sort,prosedur atau algorimatnya adalah sbb



- Buat Heap Maksimum


- Jika N lebih besar dari 1 maka tukarkan Nilai/Prioritas root dengan prioritas
simpul terakhir (simpul ke-N) tetapi jika N sama dengan 1 maka ambil nilai yang
ada di root.

- Kemudian nilai banyak simpul (N) dikurangi 1.

- Jika N > 1 maka lakukan reorganisasi heap yaitu proses sift down terhadap root.

- Lakukan langkah 2 sampai 4 sampai simpul habis (N=0).

Read More..

KUNJUNGAN PADA POHON BINER

Ada tida macam kunjungan pada pohon biner, yaitu kunjungan PreOrder, InOrder, dan PostOrder. Selain itu ada kunjungan LevelOrder, yaitu yang berdasarkan kedudukan tiap simpul dalam pohon. Keempat kunjungan itu dibagi menjadi orientasi, yaitu left to right oriented (LRO) atau kunjungan dilakukan di cabang kiri dulu baru ke cabang kanan dan right to left oriented (RLO) atau kunjungan dilakukan di cabang kanan dulu baru ke cabang kiri.

1. Kunjungan PreOrder
Kunjungan PreOrder LRO atau sering disebut dengan depth first order
menggunakan urutan sebagai berikut :
Cetak isi simpul yang dikunjungi.
Kunjungi cabang kiri.
Kunjungi cabang kanan.

Prosedur kunjungan PreOrder dapat dilakukan dengan cara rekursif atau non rekursif. Prosedur kunjungan secara PreOrder LRO dengan rekursif disajikan berikut ini :

Procedure PreOrder (Root:Pohon);
Begin
If Root <> nil then
Begin
Write (Root^.Info);
PreOrder (Root^.kiri);
PreOrder (Root^.kanan);
End;
End;

2. Kunjungan InOrder

Kunjungan InOrder LRO atau sering disebut dengan symmetric order,menggunakan urutan sebagai berikut :

Kunjungi cabang kiri.
Cetak isi simpul yang dikunjungi.
Kunjungi cabang kanan.

Seperti pada kunjungan PreOrder, prosedur kunjungan InOrder dapat dilakukan
dengan cara rekursif atau non rekursif.
Prosedur kunjungan secara InOrder LRO dengan rekursif disajikan berikut ini :

Procedure InOrder (Root:Pohon);
Begin
If Root <> nil then
Begin
InOrder (Root^.kiri);
Write (Root^.Info);
InOrder (Root^.kanan);
End;
End;

3. Kunjungan PostOrder

Kunjungan PostOrder LRO menggunakan urutan sebagai berikut :
Kunjungi cabang kiri.
Kunjungi cabang kanan.
Cetak isi simpul yang dikunjungi.

Seperti halnya PreOrde dan InOrder, prosedur kunjungan PostOrder juga dapat
dilakukan dengan cara rekursif atau non rekursif.
Prosedur kunjungan secara PostOrder LRO dengan rekursif disajikan berikut ini :

Procedure PostOrder (Root:Pohon);
Begin
If Root <> nil then
Begin
PostOrder (Root^.kiri);
PostOrder (Root^.kanan);
Write (Root^.Info);
End;
End;

4 Kunjungan LevelOrder 

Kunjungan Level order mempunyai urutan sebagai berikut :

kunijungan dimulai dari simpul yang ada pada tingkat 1 (akar),

diteruskan pada simpul ditingkat 2 ,tingkat 3 dan seterusnya

Read More..