MATRIKS PENYAJIAN GRAPH

Matriks Penyajian Graph
Matriks Adjacency dari Graph G, yaitu Matriks yang menghubungkan Vertex dengan Vertex, tanpa ruas sejajar adalah Matriks A berukuran (NxN).
Matriks Adjacency merupakan matriks simetri.
Matriks Incidence dari Graph, yaitu Matriks yang menghubungkan Vertex dengan edge, tanpa self-loop diefinisikan sebagai matriks M berukuran (NxM).

Graph Terarah (Directed Graph / Digraph)
Graph terarah adalah grap yang dapat menghubungkan V1 ke V2 saja (1 arah).
Maksimum jumlah busur dari n simpul adalah :



Graph Tak Terarah (Undirected Graph)
Graph tak terarah adalah graph yang menghubungkan 2 vertex V1 ke V2 dan V2 ke V1 (2 arah). Bila Vertex = n, maka Graph tak terarah komplit akan mempunyai busur edge sama dengan :


Penelusuran graph
Dapat dilakukan dengan 2 cara, yaitu :
1. Depth First Search (DFS)
Penelusuran dengan DFS pada graph tak berarah dengan melakukan pengecekan pada node dengan kedalaman pertama dari node yang ditinjau.
2. Breadh First Searh (BFS)
Berbeda dengan cara BFS, dengan BFS penelusuran akan diawasi dari node-1, kemudian melebar pada Adjacent Node dari Node-1 dan diteruskan pada Node-2, Node-3 dan seterusnya.

GRAPH

Graph
Suatu graph mempunyai 2 himpunan, yaitu :
Himpunan V yang elemennya disebut simpul (Vertex atau Point atau Node atau Titik)
Himpunan E yang merupakan pasangan tak urut dari simpul. Anggotanya disebut Ruas (Edge atau rusuk atau sisi)
Graph seperti dimaksud diatas, ditulis sebagai sebagai G(E,V).
Banyak simpul (vertex) disebut Order, sedangkan banyaknya ruas (edge) disebut Size dari graph.
Graph sederhana atau simple graph : Suatu graph yang tidak mengandung ruas sejajar ataupun self-loop.
Graph Berlabel
Graph G disebut berlabel jika ruas dan atau simpulnya dikaitkan dengan suatu besaran tertentu.
Derajat Graph
Derajat simpul V, ditulis d(v) adalah banyaknya ruas yang menghubungi v. Karena setiap ruas dihitung dua kali ketika menentukan derajat suatu Graph.
Bila jumlah derajat semua simpul sama dengan genap, maka disebut EULER GRAPH.

KETERHUBUNGAN
Walk atau perjalanan dalam graph G adalah barisan simpul dan ruas berganti-ganti : V1,e1,V2,e2,……,e n-1,Vn
Disini ruas ei menghubungkan simpul Vi dan Vi+1.
Banyaknya ruas disebut Panjang Walk.
Walk disebut terbuka, yang menghubungkan V1 dan Vn, yaitu setiap ruas menghubungkan Simpul Awal dan Akhir.
Trail adalah Walk dengan semua ruas dalam barisan adalah berbeda.
Path atau jalur adalah Walk yang semua simpul dalam barisan adalah berbeda. Jadi suatu Path pastilah sebuah Trail.
Cycle atau sirkuit adalah suatu trail tertutup dengan derajat setiap simpul =2. Cycle dengan panjang k disebut dengan k-cycle. Demikian pula jalur dengan panjang k disebut k-jalur.
Grap yang tidak mengandung Cycle disebut Acyclic.
Contoh dari Graph Acyclic adalah pohon atau Tree.
Subgraph yang terhubung pada suatu Graph disebut komponen dari G bila Subgraph tersebut tidak terkandung dalam Subgraph terhubung lain yang lebih besar.

STRUKTUR SEARCHING SEQUENTIAL SEARCH

• Suatu teknik pencarian data dalam array dimensi 1 yang akan menelusuri semua elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu (acak).
• Kemungkinan terbaik (best case) adalah jika data yang dicari terletak di index array terdepan sehingga waktu yang dibutuhkan untuk pencarian data sangat singkat (waktu minimal).
• Kemungkinan terburuk (worst case) adalah jika data yang dicari terletak di index array terakhir sehingga waktu yang dibutuhkan untuk pencarian data sangat lama (waktu maksimal).

BINARY SEARCHING
Merupakan metode terbaik dalam search (pencarian), karena memulai pencarian dari lokasi tengah (m).

FIBONANCY SEARCHING
Pencarian yang menggunakan deret Fibonancy sebagai dasar pencarian.
Deret Fibonancy : 0,1,1,2,3,5,8,13,21,….......

SORTING

SORTING

Sorting adalah operasi yang sangat banyak dilakukan dalam ‘ Bussiness dta Processing’. Dalam hal ini pengurutan yang di lakukan adalah secara ascending ( menarik dari kecil ke besar)
Macam-macam sorting ( pengurutan)
1. SELECTION SORT
Metode pengurutan selection sort, prosedur atau Algoritmanya adalah sbb:
• Pengecekan dimulai dari data ke-1 samping dengan data ke-n
• Tentukan bilangan dengan index terkecil dari data bilangan tersebut
• Tukar bilangan dengan index terkecil tersebut tersebut dengan bilangan pertama (I=1) dari data bilangan tersebut
• Lakukan langkah 2 dan 3 untuk bilangan berikut (I = I+1) sampai didapatkan urutan yang pertama
2. BUBBLE SORT
Metode pengurutan bubble sort mempunyai algoritma atau prosedur sebagai berikut:
• Pengecekan dimulai sampai dengan data ke-n
• Bandingkan data ke-n dengan data sebelumnya (n-1), jika lebih kecil maka tukar bil. Tsb dengan data yang ada didepanya ( sebelumnya ) satu persatu (n-,1 n-2,n-3…..dst)
• Lakukan langkah ke-2 sampai didapatkan urutan yang optimal
3. MERGE SORT
Menggunakan motode iterative marge sort mempunyai algoritma atau prosedur sebagai berikut
• Kelompok deret bilangan kedalam 1 bagian, 4 bagian, 8 bagian …..dst…..
• Urutkan secara langsung bilangan dalam kelompok tersebut
• Lakukan langkah diatas untuk kondisi bilangan yang lain sampai didapatkan urutan yang optimal

4. QUICK SORT
Sangat baik untuk table data yang sangat besar. Algoritma atau purosedur Quick sort adalah sbb:
• Tentukan bilangan yang dinyatakan sebagai batas bawah (lower bound (I =1)) dan bilangan yang dinyatakan sebagai batas atas (Upper bound (I=N))
• Syarat pemindahan adalah LB>UB,dengan melihat perbandingan antara UB (awal bilangan ) dan LB (akhir bilangan)
• Jika LB > UB lakukan pertukaran antara dua bilangan tersebut, jika tidak dilakukan permindahan LB (I=IA+1,I=1+2…..) Ke bilangan selanjutnya dan bandingkan kembali dengan UB (I=N,I =N-1,I=N-2………)

KUNJUNGAN PADA POHON BINER

Kunjungan pada pohon biner merupakan salah satu operasi yang sering dilakukan pada suatu pohon binary tepat satu kali (Binary Tree Traversal). Operasi ini terbagi menadi 3 bentuk :

1. Kunjungan secara preorder (Depth First Order),
Mempunyai urutan :
• Cetak isi simpul yang dikunjungi (Simpul Akar)
• Kunjungi Cabang Kiri
• Kunjungi Cabang Kanan
2. Kunjungi secara Postorder, mempunyai urutan :
• Kunjungi Cabang Kiri
• Cetak isi simpul yang dikunjungi (Simpul Akar)
• Kunjungi Cabang Kanan
3. Kunjungan secara Postorder, mempunyai urutan :
• Kunjungi Cabang Kiri
• Kunjungi Cabang Kanan
• Cetak isi simpul yang dikunjungi (Simpul Akar)

Pada ketiga cara kunjungan diatas, kunjungan ke cabang kiri dilakukan terlebih dahulu, baru kemudian kunjungan ke cabang kanan.
Ketiga kunjungan diatas disebut Left To Right Oriented (LRO).
Jika kunjungan ke cabang kanan dilakukan lebih dahulu baru kemudian kunjungan ke cabang kiri, maka orientasi semacam ini disebut Right To Left Oriented (RLO).




Kunjungan LevelOrder
Merupakan kunjngan yang dimulai dari simpul yang ada pada tingkat 1 (Akar), diteruskan pada simpul di tingkat 2, tingkat 3 dan seterusnya.

APLIKASI PADA POHON BINER
Notasi Prefix, Infix dan Postfix
Pada bagian ini akan dibahas tentang bagaimana menyusun sebuah pohon binary yang apabila dikunjungi secara Preorder akan menghasilkan Notasi Prefix, kunjungan secara Inorder menghasilkan Notasi Infix, dan kunjungi PostOrder menghasilkan Notasi Postfix.

STRUKTUR POHON ( TREE)

STRUKTUR POHON ( TREE)

ISTILAH-ISTILAH DASAR
Pohon atao tree adalah satu bentuk satu bentuk graph terhubung yang tidak mengandung sirkuit.
Karena merupakan graph terhubung , maka pada pohon ( tree) selalu terdapat path atau jalur yang menghubungkan setiap simpul dalam dua pohon.
Pohon (tree) dapat juga didenfinisikan sebagai kumpulan elemen yang salah satu elemennya disebut dengan akar (Root) dan sisa elemen lain (simpul)yang terpecah menjadi sejumlah himpunan yang saling tidak terhubung yang disebut dengan Subpohon (subtree) atau cabang.
Sifat Utama Pohon Berakar
1. jika pohon mempunyai simpul sebanyak n, maka banyaknya ruas atau adge adalah ( n-1)
2. mempunyai simpul khusus yang di sebut rood.
3. mempunyai simpul yang disebut sebagai daun atau leaf
4. setiap simpul mempunyai tingkayan atau level yang dimulai dari root yang level nya =1 sampai dengan levek ke-n pada daun paling bawah. Simpul yang mempunyai level sama disebut bersaudara atu brother atau stribling
5. pohon mempunyai ketinggian atau kedalaman atau height, yang merupakan lever tertinggi.
6. pohon memepunyai weight atau berat atau bobot , yang banyaknya daun (leaf) pada pohon .
7. banyaknya simpul maksimum sampai level n adalah:


8. banyaknya simpul untuk setiap level 1 adalah :




Hutan (Forest) adalah kumpulan pohon yang tidak saling berhubungan

POHON BINAR (BINARY TREE)
Pohon binary (Binary Tree) adalah kumpulan simpul yang mungkin kosong atau mempunyai akar dan dua subpohon yang saling terpisah yang disebut dengan subpohon kiri / cabang kiri (Left Subtree) dan Subpohon Kanan / cabang kanan (Right Subtree).
Karakteristik Pohon Binar (Binary Tree) :
1. Setiap simpul banyak hanya memiliki dua buah anak
2. Derajat Tertinggi dari setiap simpul adalah dua
3. Dibedakan antara Cabang kiri dan Cabang kanan
4. Dimunginkan tidak mempunyai simpul

Istilah pada pohon biner
• Pohon Biner Penuh (Full Binary Tree)
• Pohon Biner Lengkap (Complete Binary Tree)
• Pohon Biner Similer
• Pohon Biner Ekivalent
• Pohon Biner Miring (Skewad Tree)

QUEUE ( ANTREAN )

QUEUE ( ANTREAN )

PENGERTIAN QUEUE (ANTREAN)
Suatu data Antrean (queue)adalah suatu bentuk khusus dari list linier dengan operasi pemasukan data hanya diperbolehkan pada salah satu sisi, yang tersebut sisi belakang /ekor (tail)dan operasi penghapus hanya diperolehkan pada sisi lainnya ang disebut sisi depan / kepala (Head) dari linkedlist.

OPERASI QUEUE
CREATE
• Untuk menciptakan dan menginisialisasi Queue dengan cara membuat Head dan TAIL =-1
ISEMPTY
• Untuk memeriksa apakah queue kosong
ISFULL
• Untuk memeriksa apakah queue sudah penuh
ENQUEUE
• Untuk menambah item pada posisi paling belakang
DEQUEUE
• Untuk menghapus item dari posisi palng depan
CLEAR
• Untuk mengosokan queue

Fungsi IsFULL
• Untuk mengecek apakah antrian sudah penuh atau belum
• Dengan Cara
Mengecek nilai Tail jika tail = MAX=-1 berarti antrian sudah penuh (MAX-1 adalah batas elemen array dalam program C++)

Fungsi Enqueue
• Untuk menambah elemen ke dalamAntrian, penamahan elemen selalu dilakukan pada elemen paling belakang
• Penambahan elemen selalu menggerakan variable tail dengan cara menambahkan tail terlalu dahulu
Fungsi Dequeue
• Digunakan untuk menghapus elemen terdepan (head)dari antrian
• Dengan Cara
Menggeser semua elemen antrian kedepan dan mengurangi tail dengan 1. penggeseran dilakukan dengan menggunakan looping
Fungsi Clear
• Untuk menghaous elemen-elemen antrian dengan cara membuat tail dan head-1
• Penghapus elemen-elemen antrian sebenarnya tidak menghapus arraynya, namun hanya mengeset indeks pengaksesan-nyake nilai-1 sehingga elemen-elemen antrian tidak lagi terbaca sehingga mengembalikan antrian seperti keadaan semula