GRAF DAN POHON
PENJELASAN
GRAF
1.
Pengertian
Graf
adalah
kumpulan noktah (simpul) di dalam bidang dua dimensi yang dihubungkan dengan
sekumpulan garis (sisi). Graph dapat digunakan untuk merepresentasikan
objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi
visual dari graph adalah dengan menyatakan objek sebagai noktah, bulatan
atau titik (Vertex), sedangkan hubungan antara objek dinyatakan dengan garis
(Edge).
G = (V, E)
Dimana
G = Graph
V = Simpul atau Vertex, atau Node,
atau Titik
E = Busur atau Edge, atau arc
Graf merupakan suatu cabang ilmu
yang memiliki banyak terapan. Banyak sekali struktur yang bisa
direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan
bantuan graf. Seringkali graf digunakan untuk merepresentasikan suaru jaringan.
Misalkan jaringan jalan raya dimodelkan graf dengan kota sebagai simpul (vertex/node)
dan jalan yang menghubungkan setiap kotanya sebagai sisi (edge) yang
bobotnya (weight) adalah panjang dari jalan tersebut.
Ada beberapa cara untuk menyimpan
graph di dalam sitem komputer. Struktur data bergantung pada struktur graph dan
algoritma yang digunakan untuk memmanipulasi graph. Secara teori salah satu
dari keduanya dapat dibedakan antara struktur list dan matriks, tetapi dalam penggunaannya
struktur terbaik yang sering digunakan adalah kombinasi keduanya.
• Graph
tak berarah (undirected graph atau non-directed graph) :
• Urutan
simpul dalam sebuah busur tidak dipentingkan. Misal busur e1 dapat disebut
busur AB atau BA
• Graph berarah (directed graph) :
• Urutan simpul mempunyai arti.
Misal busur AB adalah e1 sedangkan busur BA adalah e8.
• Graph Berbobot (Weighted Graph)
• Jika setiap busur mempunyai nilai
yang menyatakan hubungan antara 2 buah simpul, maka busur tersebut dinyatakan
memiliki bobot.
• Bobot sebuah busur dapat
menyatakan panjang sebuah jalan dari 2 buah titik, jumlah rata-rata kendaraan
perhari yang melalui sebuah jalan, dll.
2.
Istilah-istilah dalam graf
Kemudian
terdapat istilah-istilah
yang berkaitan dengan graph yaitu:
a. Vertex Adalah himpunan node /
titik pada sebuah graph.
b. Edge Adalah
himpunan garis yang menghubungkan tiap node / vertex.
c.
Adjacent Adalah dua buah titik dikatakan berdekatan (adjacent) jika dua
buah titik tersebut terhubung dengan sebuah sisi. Adalah Sisi e3 = v2v3 insident
dengan titik v2 dan titik v3, tetapi sisi e3 = v2v3 tidak insident dengan
titik v1 dan titik v4. Titik v1 adjacent dengan
titik v2 dan titik v3, tetapi titik v1 tidak adjacent dengan
titik v4.
d. Weight Adalah Sebuah graf G = (V, E) disebut sebuah graf
berbobot (weight graph), apabila terdapat sebuah fungsi bobot
bernilai real W pada himpunan E,
W : E ® R,
nilai W(e) disebut bobot untuk sisi e, " e Î E. Graf berbobot tersebut
dinyatakan pula sebagai G = (V, E, W).
Graf berbobot G = (V, E, W) dapat
menyatakan
* suatu sistem perhubungan udara, di mana
· V = himpunan kota-kota
· E = himpunan penerbangan langsung dari satu kota ke kota
lain
· W = fungsi bernilai real pada E yang menyatakan jarak atau
ongkos atau waktu
* suatu sistem jaringan komputer, di mana
· V = himpunan komputer
· E = himpunan jalur komunikasi langsung antar dua komputer
· W = fungsi bernilai real pada E yang menyatakan jarak atau
ongkos atau waktu
e. Path Adalah Walk dengan setiap vertex berbeda. Contoh, P = D5B4C2A Sebuah walk (W) didefinisikan sebagai
urutan (tdk nol) vertex & edge. Diawali origin vertex dan diakhiri terminus
vertex. Dan setiap 2 edge berurutan adalah series. Contoh, W = A1B3C4B1A2.
f. Cycle Adalah Siklus ( Cycle ) atau Sirkuit ( Circuit
) Lintasan yang berawal dan berakhir pada simpul yang sama
3. Representasi Graf
Dalam
pemrograman, agar data yang ada dalam graph dapat diolah, maka graph harus
dinyatakan dalam suatu struktur data yang dapat mewakili graph tersebut. Dalam
hal ini graph perlu direpresentasikan kedalam bentuk array dan dimensi yang
sering disebut matrix atau direpresentasikan dalam bentuk linked list. Bentuk
mana yang dipilih biasanya tergantung kepada efisiensi dan kemudahan dalam
membuat program. Berikut ini beberapa bentuk representasi graph:
1. Representasi
Graph dalam bentuk Matrix:
1. Adjacency Matrik Graf Tak Berarah
Matrik yang digambarkan pada gambar 1b
merupakan representasi dalam bentuk Adjacency Matrik dari graf yang digambarkan
pada gambar 1a. Beberapa hal yang dapat dilihat atau dapat diterangkan pada
Adjacency Matrik tersebut adalah sebagai berikut :
1. Matrik yang
terbentuk adalah matrik bujur sangkar n x n, dimana n = jumlah simpul yang ada
dalam graf tersebut. Matrik ini menyatakan hubungan antara simpul satu dengan
simpul lainnya.
2. Matrik yang
terbentuk adalah matrik simetris dengan sumbu simetris adalah diagonal dari
titik kiri atas ke titik kanan bawah.
3. Data yang
tedapat baik dalam baris maupun kolom, dapat menyatakan degree sebuah simpul.
Contoh : baik pada baris D maupun kolom D jumlah angka 1 nya adalah 3 buah,
dimana jumlah ini menyatakan degree simpul D.
2.
Adjacency Matrik Graf Berarah
Matrik
yang digambarkan pada gambar 2b merupakan representasi dalam bentuk Adjacency
Matrik dari graf yang digambarkan pada gambar 2a. Beberapa hal yang dapat
dilihat atau dapat diterangkan pada Adjacency Matrik tersebut adalah sebagai
berikut :
1. Matrik
yang terbentuk adalah matrik bujur sangkar n x n, dimana n = jumlah simpul yang
ada dalam graf tersebut. Matrik ini
menyatakan hubungan antara simpul satu dengan simpul lainnya.
2. Matrik yang terbentuk mungkin simetris
mungkin juga tidak simetris. MenjadiSimetris bila hubungan antara dua buah
simpul (v1 dan v2) terdapat busur dari v1 ke v2 dan juga sebaliknya.
3. Hal pokok yang
dinyatakan oleh matrik ini adalah : busur yang ’keluar’ dari suatu simpul.
Dengan demikian, data yang terdapat dalam suatu baris, dapat menyatakan
outdegree simpul yang bersangkutan. Contoh : Jumlah elemen yang nilainya = 1
pada baris B ada 3 elemen,ini menyatakan jumlah outdegree simpul B adalah 3
buah.
4. Data yang
terdapat dalam suatu kolom, dapat menyatakan indegree simpul bersangkutan. Contoh : Jumlah
elemen yang nilainya 1 pada kolom B ada 2 elemen, ini menyatakan indegree
simpul B adalah 2 buah.
3. Adjacency
Matrik Graf Berbobot Tak Berarah
Nilai
yang ada dalam tiap elemen matrik, menyatakan bobot busur yang menghubungkan
dua buah simpul yang bersangkutan. Untuk dua buah simpul yang tidak berhubungan
langsung oleh sebuah busur, maka dianggap dihubungkan oleh sebuah busur yang
nilai bobotnya tidak terhingga. Dalam pemograman, karena keperluan algoritma,
maka dari total bobot seluruh busur yang ada atau yang mungkin ada. Contoh:
pada gambar 3a simpul A dan C tidak berhubungan langsung melalui sebuah busur,
maka untuk elemen matrik yang bersangkutan diisi dengan nilai 999 karena nilai 999 dalam kasus ini cukup
mewakili nilai tidak terhingga.
2. Representasi
graf dalam bentuk Linked List
1. Adjacency List
Bila ingin direpresentasikan
dalambentuk linked list, dapat diilustrasikan secara sederhana seperti gamabar
4b. Dari ilustrasi sederhana tersebut terlihat ada 5 buah simpul A,B,C,D,dan E
yang dibariskan dari atas kebawah seperti pada gambar 4a. Kemudian dari
masing-masing simpul ’keluar’ pointer kearah kanan yang menunjuk simpul-simpul
lain. Salah satu contoh, yang dapat dilihat pada gambar 4b dimana A menunjuk
simpul B dan simpul D.
Dalam Adjacency List, kita
perlu membedakan antara simpul-vertex dan simpul-edge. Simpul-vertex untuk
menyatakan simpul atau vertex, dan simpul-edge untuk menyatakan hubungan antar
simpul yang biasa disebut busur. Struktur keduanya bisa sama, bisa juga tidak
sama,tergantung kebutuhan.Untuk memudahkan pembuatan program, struktur kedua
macam simpul dibuat sama seperti yang digambarkan pada gambar 5c. Yang
membedakan antara simpul-vertex dan simpul-edge, adalah anggapan terhadap
simpul tersebut. Dalam contoh
ini, terlihat struktur simpul dibuat terdiri dari 3 elemen. Satu elemen untuk
INFO, dua elemen untuk pointer.pointer kiri (left) dan pointer kanan (right).
Struct tipes{
Struct tipes *Left;
int INFO;
Struct tipes *Right;
};
Struct tipes *First,*Pvertex,*Pedge;
- Bila
simpul dianggap sebagai simpul-vertex, maka :
Pointer left digunakan untuk menunjuk simpul berikutnya dalam untaian
simpul-simpul yang ada,atau diisi NULL bila sudah tidak ada simpul yang pelu
ditunjuk.Sedangkan pointer Right digunakan untuk menunjuk simpul edge yang
pertama.
- Bila
Simpul dianggap sebagai simpul-edge, maka :
Pointer left digunakan untuk menunjuk simpul-vertex
‘tujuan’ yang berhubungan dengan simpul-vertex ‘asal’ dan pointer right
digunakan untuk menunjuk simpul-edge berkiutnya bila masih ada, atau diisi NULL
bila tak ada lagi simpul-busur yang ditunjuk.
PENJELASAN
TREE
1. Pengertian
Tree
dalam pemrograman
merupakan struktur data yang tidak linear / non linear yang digunakan terutama
untuk merepresentasikan hubungan data yang bersifat hierarkis antara
elemen-elemennya. Kumpulan elemen yang salah satu elemennya disebut dengan root
(akar) dan sisa elemen yang lain disebut sebagai simpul (node/vertex) yang
terpecah menjadi sejumlah himpunan yang tidak saling berhubungan satu sama
lain, yang disebut subtree / cabang.
Adapun Perbedaan Graph dengan Tree sebagai berikut:
a. Pada Tree tidak terdapat Cycle
b. Pada Graph tidak memiliki root
