Struktur Data - Struktur Data Grafik
Grafik adalah representasi bergambar dari sekumpulan objek di mana beberapa pasang objek dihubungkan oleh tautan. Objek yang saling berhubungan diwakili oleh poin yang disebut sebagaivertices, dan tautan yang menghubungkan simpul disebut edges.
Secara formal, grafik adalah sepasang himpunan (V, E), dimana V adalah himpunan simpul dan Eadalah himpunan tepi, menghubungkan pasangan simpul. Perhatikan grafik berikut -
Pada grafik di atas,
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}
Grafik Struktur Data
Grafik matematika dapat direpresentasikan dalam struktur data. Kita dapat merepresentasikan grafik menggunakan larik simpul dan larik tepi dua dimensi. Sebelum melangkah lebih jauh, mari kita membiasakan diri dengan beberapa istilah penting -
Vertex- Setiap simpul pada grafik direpresentasikan sebagai simpul. Dalam contoh berikut, lingkaran berlabel mewakili simpul. Jadi, A ke G adalah simpul. Kami dapat mewakili mereka menggunakan array seperti yang ditunjukkan pada gambar berikut. Di sini A dapat diidentifikasi dengan indeks 0. B dapat diidentifikasi menggunakan indeks 1 dan seterusnya.
Edge- Edge mewakili jalur antara dua simpul atau garis antara dua simpul. Dalam contoh berikut, garis dari A ke B, B ke C, dan seterusnya mewakili tepian. Kita dapat menggunakan array dua dimensi untuk merepresentasikan array seperti yang ditunjukkan pada gambar berikut. Di sini AB dapat direpresentasikan sebagai 1 pada baris 0, kolom 1, BC sebagai 1 pada baris 1, kolom 2 dan seterusnya, dengan kombinasi lain sebagai 0.
Adjacency- Dua buah simpul atau simpul bersebelahan jika keduanya terhubung satu sama lain melalui sebuah sisi. Dalam contoh berikut, B berdekatan dengan A, C berdekatan dengan B, dan seterusnya.
Path- Path merepresentasikan urutan tepi antara dua simpul. Dalam contoh berikut, ABCD merepresentasikan jalur dari A ke D.
Operasi Dasar
Berikut adalah operasi utama dasar dari sebuah Grafik -
Add Vertex - Menambahkan titik sudut ke grafik.
Add Edge - Menambahkan tepi di antara dua simpul pada grafik.
Display Vertex - Menampilkan simpul dari grafik.
Untuk mengetahui lebih lanjut tentang Grafik, silakan baca Tutorial Teori Grafik . Kita akan belajar tentang melintasi grafik di bab-bab selanjutnya.