Representasi Binary Tree Pada Array

Index dari array mempresentasikan atau menunjukan nomor node.
index ke-0 merupakan root.
index dari left Child adalah 2p + 1,dimana p = index dari parent
index dari Right Child adalah 2p+ 2,dimana p= index dari parent
index dari Parent adalah(p-1)/p
Right Child dari kanan Lebih besar daripada Left Child
Predecesor = node yang berada diatas node tertentu.
Successor = node yang berada dibawah node tertentu
Ancestor = seluruh node yang terletak setelah node tertentu dan terkletak pada jalur yang sama
Descendat = Seluruh node yang terletak setelah node tertentu dan terletak pada jalur yang sama
Parent = predecesor satu level diatas duatu node
Child = Successor satu level dibawah suatu node
Sibling = node node yang memiliki Parent yang sama
Subtree = suatu node beserta desencandtnya
size = banyaknya node dalam suatu tree
root = node khusus yang tidak memiliki predecesor
leaf = node node dalam tree yang tidak memiliki successsor
degree = banyaknya child dalam suatu tree















TRee
Tree Statik : isi node-nodenya tetap karena bentuk pohonya sudah di tentukan
Tree Dinamik : isi nodenya berubah-ubah karena proses penambahan dan pengahapusan
Node Root
Node root dalam sebuah tree adlah suatu node yang memiliki hiarki tertinggi dan dapat juga memiliki node node anak.semua node dapat di telusuri dari node root tersebut
Node root adalah node khususs yang tercipta pertama kalinya.
Node-Node lain di bawah node root saling terhubung satusama lain dan disebut subtree.

• Graph adalah kumpulan dati titik (node) dan garis dimana pasangan – pasangan titik (node) tersebut dihubungkan oleh segmen garis. Node ini biasa disebut simpul (vertex) dan segmen garis disebut ruas (edge)
• Simpul dan ruas dalam graph dapat diperluas dengan penambahan informasi. Sebagai contoh, simpul bias diberi nomor atau label dan ruas dapat diberi nilai juga. Perluasan dengan pemberian informasi ini sangat berguna dalam penggunaan graph untuk banyak aplikasi computer. Contoh, graph dengan simpul yang merepresentasikan kota dan ruas merepresentasikan jarak yang ditempuh diantara kota – kota tersebut. (atau harga tiket pesawat antara kota – kota tersebut)
• Dapat digunakan sebagai “transportation network” untuk mempelajari total jarak (atau harga) dari suatu perjalanan dengan banyak kota pemberhentian. Satu kemungkinan pertanyaan yang bias muncul adalah “jalur mana yang terpendek dengan satu atau lebih tempat pemberhentian, yang menghubungkan kota tertentu menuju kota tertentu lainnya dalam transportation network tersebut?”

KELAHIRAN TEORI GRAPH

• Jembatan Konigsberg

Menurut catatan sejarah, masalah jembatan Konigsberg adalah masalah yang pertama kali menggunakan graph (th. 1736). Masalah jembatan Konigsberg adalah : “apakah mungkin melalui tujuh buah jembatan masing – masing tepat satu kali. Dan kembali lagi ke tempat semula?”. Tak seorangpun yang dapat memecahkan masalah ini. Barulah euler yang pertama kali menemukan jawabannya. Ia memodelkan masalah dengan memodelkannya ke dalam graph. Daratan (titik – titik yang dihubungkan oleh jembatan) dinyatakannya sebagai simpul (vertex) dan jembatan sebagai sisi. Graph dibuat oleh Euler diperlihatkan pada gambar dibawah atas.

• Jawabannya adalah : orang tidak mungkin berjalan melalui ketujuh jembatan masing – masing satu kali dan kembali ke tempat asal keberangkatan. Singkatnya, tidak terdapat siklus Euler pada graph tersebut
• Graph yang memenuhi kondisi diatas tersebut kemudian dikenal dengan nama graph Euler dan perjalannya disebut perjalanan Euler
• Perjalanan Euler adalah perjalanan dari suatu simpul kembali ke simpul tersebut dengan melalui setiap ruas tepat satu kali
• Perjalanan Euler akan terjadi, jika :

1. Graf terhubung
2. Banyaknya ruas yang dating pada setiap simpul adalah genap

Jenis Graph

• Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graph, maka graph digolongkan menjadi dua jenis :

1. Graph sederhana (simple graph)

Graph yang tidak mengandung gelang maupun sisi ganda dinamakan graph sederhana

2. Graph tak sederhana (unsimple graph / multigraph)

Graph yang mengandung ruas ganda atau gelang dinamakan graph tak sederhana (unsimple graph / multigraph)
Berdasarkan jumlah simpul pada suatu graph, maka secara umum graph dapat digolongkan menjadi dua jenis :

1. Graph berhingga (limited graph)

Graph berhingga adalah graph yang jumlah simpulnya, n, berhingga

2. Graph tak berhingga (unlimited graph)

Graph yang jumlah simpulnya, n, tidak berhingga banyaknya
Berdasarkan orientasi arah pada sisi, maka secara umum graph dibedakan atas 2 jenis :

1. Graph tak berarah (undirected graph)

Graph yang sisinya tidak mempunyai orientasi arah

2. Graph berarah (directed graph / digraph)

DEFINISI

• Graph merupakan suatu koleksi dari himpunan VG dan EG

Notasi : G = {VG, EG}
G = Graph
VG = himpunan titik (vertex graph)
EG = himpunan garis (edge graph)

• Titik : node / vertex
• Garis : arc / edge
• Jumlah vertex dalam suatu graph disebut ORDER dari graph tresebut
• Contoh : graph G dengan order = 4 (jumlah vertex = 4; a, b, c, d)
• Suatu graph hanya ditentukan oleh vertex – vertex dan edge – edgenya. Posisi dari vertex – vertex dan edge – edge dalam penggambaran tidaklah penting
• Graph Equivalen : penggambaran graph yang sama
• 
• Suatu graph G disebut Simple Graph, jika :
• • Tidak mempunyai edge yang Self Loop (tidak ada (V,V) dalam G)
  • Tidak mempunyai Multiple Edge (hanya ada (Vi, Vj) dalam G) (V1, V2, V3, … ϵ VG)
• 
• • Multiple Edge adalah 1 vertex dihubungkan oleh beberapa edge
  • Contoh ; pada gambar graph equivalen diatas, vertex b dihubungkan oleh edge – edge 1, 2, 3, 5, 6, 7
  • Sedangkan vertex c dihubungkan oleh edge- edge 2, 3, 4
  • Self Loop adalah vertex yang dihubungkan oleh edge – edge menuju edge itu sendiri
  • Contoh : pada gambar graph equivalen diatas, vertex a dihubungkan oleh graph 8 menuju a kembali
  • Suatu graph G disebut Connected (terhubung) jika graph G dapat dipartisi (dibagi) menjadi 2 graph dengan menghapus paling sedikit 1 edge
  • Contoh yang tidak connected : suatu graph G terdiri
  G = {VG, EG}
  VG = {e, f, g, h}
  EG = {1, 2, 3}
• 
• • Path dalam graph adalah barisan dari 1 buah edge –edge yang menghubungkan 2 vertex
  • Notasi :
  P(Vi, Vj) = (Vi, X1)(X1, X2)(X2, Xn-1)(Xn-1, Xn)(Xn, Vj)
  
  • Dari gambar simple graph :
  P(b,d) = (b,c)(c,d)
  P(b,d) = (b,c)(c,b)(b,c)(c,d)
  P(b,d) = (b,d)
  P(b,d) = (b,c)(c,b)(b,d)
  
  • Length dari suatu path adalah jumlah edge – edge pada path tersebut
  • Contoh : perhatikan gambar simple graph :
  P(b,d) = (b,d)                                     length = 1
  = (b,c)(c,d)                          length = 2
  = (b,c)(c,b)(b,d)                                length = 3
  
  • Cycle adalah path yang memenuhi syarat sebagai berikut :
  1. Tidak ada edge yang tampil lebih dari satu kali dalam barisan edge dari path tersebut
  Contoh : gambar simple graph
  P(b,d) = (b,c)(c,b)(b,d)
  = tidak boleh
  
  1. Path harus berbentuk P(V,V)
  2. Tidak ada vertex yang dikunjungi lebih dari satu kali
  Contoh : P(a,a) = (a,b)(b,c)(c,d)(d,b)(b,a)
  B dikunjungi lebih dari 1x
  P(b,b) = (b,c)(c,b)(b,a)(a,c)(c,b)
  C & b dikunjungi 3x
  Contoh Cycle : P(b,b) = (b,d)(d,c)(c,b)
  
  • Acyclic adalah graph yang tidak mempunyai cycle
  • Contoh : graph G terdiri dari
  G = {VG, EG}
  VG = {a,b,c,d}
  EG = {1,2,3}
• 
• Catatan :
• 1. Graph yang simple belum tentu yang acyclic
  2. Graph yang acyclic adalah graph yang simple
  • Graph yang berarah disebut DI-GRAPH / Directed Graph, adalah merupakan graph dimana edge – edgenya mempunyai suatu arah
• 
• Pada gambar ;
• (a,b) = 1 arah (b,a) = 0 arah
  
  • Graph yang tidak mempunyai arah boleh bolak – balik
• 
• Pada gambar;
• (a,b) = 1 arah (b,a) = 1 arah
  OUT DEGREE, IN DEGREE, DEGREE DARI SUATU VERTEX A
  
  • Vertex a mempunyai :
  1. Out degree (derajat luar) = N
  Jika vertex a mempunyai N edge mengarah keluar
  Misal : vertex a memunyai 2 edge mengarah ke luar (gambar digraph diatas)
  
  1. In degree (derajat masuk) = N
  Jika vertex a mempunyai N edge mengarah masuk ( gambar digraph diatas)
  
  1. Degree (derajat) = N
  Jika out degree a ditambah in degree a = N
  Misal : vertex b
  In degree    = 2
  Out degree = 3
  Degree         = 5
  
  • Contoh : pada gambar digraph diatas;
  Degree (a)          = 3
  Degree(b)           = 5
  Degree(c)            = 3
  Degree(d)           = 5
  16
  
  • Graph G dengan himpunan vertex V0 dan edge E0 diasumsikan graph berorder N untuk N ≥ 1
  • Salah satu pendekatan untuk graph ini menggunakan matriks Adjacency dengan suatu array A ukuran N x N
  A(i, j)     1 jika edge (Vi, Vj) Eij
  0 jika edge (Vi, Vj) Eij
  
  • Contoh graph Undirect / matriks simetris
• 
• Contoh : graph Direct
• 
• PENGGAMBARAN NODE DIRECTORY
  • Penggambaran node dalam directory dibagi dalam 2 bagian :
  1. Directory
  2. Himpunan link list (LL)
  • Setiap record dari link list mempunyai 2 field :
  1. Node indetifier
  2. Suatu link yang menghubungkan elemen lain dari list (next)

  NODE

  NEXT

  • Directory menggambarkan banyak node
  • Link list menunjukkan edge – edgenya
• 
• • Kalau punya harga (untuk penggambaran manajemen proyek) penggambaran node-nya dibagi 3
  • 

Advertisemen
STACK adalah salah satu list linear dalam struktur data yang digunakan untuk menyimpan dan mengambil data dengan konsep LIFO (Last In First Out). Dimana dalam stack ini kumpulan data yang masuk diletakkan di atas data yang lain. Dan berdasar konsep LIFO maka data yang terakhir kali disimpan dalam stack akan menjadi data yang pertama kali diambil. Dalam prosesnya, untuk memasukkan sebuah data ke dalam stack atau dengan kata lain ke bagian atas dari sebuah tumpukan digunakan perintah push. Dan untuk memindahkan data dari tempat tersebut digunakan perintah pop. Sedangkan dalam penyajiannya, stack bisa memakai array atau linked list.

stack

Selasa, 03 April 2018

Add Comments

NEXT PREV HOME

Cari Blog Ini

Palindrome

Masukkan Data : palindrom : Hasil palindrom : Data di dalam stack: Tampilan data Banyak Data: Data Terakhir: