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. Menjadi
Simetris 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.
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.
Sumber : t4urusboy08.blogspot.co.id
