My first Magazine pemrograman-kompetitif-dasar | Page 101

9.2 Jenis Graf
9.2.1 Tree
Tree merupakan bentuk khusus dari graf. Seluruh node pada tree terhubung (tidak ada
node yang tidak dapat dikunjungi dari node lain) dan tidak terdapat cycle . Cycle merupakan
sekumpulan K node unik [n 0 , n 1 , ..., n K−1 ], yang mana K > 1, dan setiap elemen n i memiliki tetangga
ke n (i+1) mod K . Banyaknya edge dalam sebuah tree pasti V − 1, dengan V adalah banyaknya node .
F
F
B
E
B
A
D
C
(a)
A
G
D
C
I
E
H
(b)
(c)
Gambar 9.5: Gambar (a) bukan tree karena memiliki cycle, salah satunya [E, A, D], sedangkan
gambar (b) dan (c) merupakan tree .
Tree sendiri bisa dikategorikan menjadi beberapa jenis, tergantung karakteristiknya.
Rooted Tree
Suatu tree yang memiliki hierarki dan memiliki sebuah akar disebut sebagai rooted tree.
Setiap node pada rooted tree memiliki kedalaman yang menyatakan jarak node tersebut ke
node root (node root memiliki kedalaman 0).
Gambar 9.6: Contoh rooted tree. Bagian root ditunjukkan pada node yang berada di paling
atas.
Binary Tree
Suatu rooted tree yang setiap node -nya memiliki 0, 1, atau 2 anak disebut dengan binary
tree.
Gambar 9.7: Contoh binary tree.
91