Graph

Apa itu Graph?

Graf adalah sekumpulan vertex/node yang dihubungkan oleh nol atau lebih edge.

Terminologi

• weight - "berat" dari suatu edge. dapat juga diartikan sebagai panjang sebuah edge
• un/weighted graph - istilah dimana edge pada suatu graph memiliki atau tidak memiliki weight
• un/directed edge - istilah untuk menyatakan apabila sebuah edge bersifat dua arah atau satu arah
• path - urutan satu atau lebih edge yang dilewati untuk menghubungkan dua buah vertex
• connected - sebuah graph dimana terdapat setidaknya satu buah path untuk setiap pasang vertex.
• cycle - sebuah path yang berawal dan berakhir pada satu buah vertex yang sama tanpa melewati dua buah edge yang sama
• tree - sebuah undirected connected graph yang tidak memiliki cycle.
• root - vertex dengan kedalaman terendah.
• ancestor - himpunan vertex yang dilewati dalam suatu path dari root ke sebuah vertex.
• parent - ancestor suatu node yang memiliki kedalaman tertinggi
• child - kumpulan vertex yang terhubung dengan suatu edge dan bukan merupakan ancestor.

Cara Merepresentasikan Graph

• Adjacency Matrix

            Kita dapat merepresentasikan graph dengan menggunakan array 2 dimensi Adjmat[V][V]

dengan AdjMat[i][j] bernilai 1 apabila terdapat edge yang menghubungan vertex i dan vertex j dan 0 jika tidak ada. Nilai AdjMat[i][j] bisa juga bernilai weight dari suatu edge untuk weighted graph.

• Adjacency List

        Masalah utama dari penggunaan adjacency matrix adalah penggunaan memory yang cukup besar untuk graph sehingga tidak memungkinkan untuk graph dengan ukuran besar. Solusi dari permasalah tersebut adalah dengan menggunakan Adjacency List. Ide dari perepresentasian dengan menggunakan Adjacency List adalah dengan hanya menyimpan daftar dari vertex-vertex lain yang memiliki edge yang terhubung dengan suatu vertex.

Implementasi dan Dokumentasi

• Adjacency Matrix

• Adjacency List