My first Magazine pemrograman-kompetitif-dasar | Page 100

9 Perkenalan Graf
Perhatikan bahwa boleh saja terdapat beberapa edge yang menghubungkan dua node yang
sama.
9.2
Jenis Graf
Berdasarkan hubungan antar node , graf dapat dibedakan menjadi:
• Graf tak berarah: edge dari A ke B dapat ditelusuri dari A ke B dan B ke A.
• Graf berarah: edge dari A ke B hanya dapat ditelusuri dari dari A ke B.
A
A
B
D
D
B
C
C
Gambar 9.2: Graf tak berarah dan graf berarah.
Sementara berdasarkan bobot dari edge , graf dapat dibedakan menjadi:
• Graf tak berbobot, yaitu graf dengan edge yang bobotnya seragam dan hanya bermakna
terdapat hubungan antar node .
• Graf berbobot, yaitu graf dengan edge yang dapat memiliki bobot berbeda-beda. Bo-
bot pada edge ini bisa jadi berupa biaya, jarak, atau waktu yang harus ditempuh jika
menggunakan edge tersebut.
A
1
B
5
B
D
2
C
A
3
D
C
Gambar 9.3: Graf tak berbobot dan graf berbobot.
Tentu saja, suatu graf dapat memiliki kombinasi dari sifat-sifat tersebut. Misalnya graf yang
berbobot dan berarah.
1
B
A
3
2
5
8
D
C
Gambar 9.4: Graf yang berbobot dan berarah.
Beberapa graf juga memiliki suatu karakteristik khusus. Contohnya adalah tree, directed
acyclic graph, atau bipartite graph. Kali ini kita akan menyinggung tree dan directed acyclic
graph.
90