Jenis-Jenis Grafik dalam Struktur Data Beserta Contohnya
Grafik adalah struktur data non-linier yang terdiri dari simpul dan sisi. Simpul berisi informasi atau data, dan ujung-ujungnya berfungsi sebagai penghubung antara sepasang simpul.
Grafik dapat terdiri dari beberapa jenis, bergantung pada posisi node dan tepinya. Berikut beberapa jenis Grafik yang penting:
Grafik Sutradara
Tepi Grafik Berarah berisi panah yang menunjukkan arah. Panah menentukan di mana tepinya menunjuk atau berakhir.
Berikut ini contoh Grafik Terarah.

- Kita bisa berpindah dari Node A ke D.
- Namun, kita tidak bisa berpindah dari node D ke node A karena titik tepinya dari A ke D.
- Karena Graf tersebut tidak mempunyai bobot, maka biaya perjalanan dari titik A ke D sama dengan biaya perjalanan dari D ke F.
Grafik Tidak Berarah
Grafik Tidak Terarah berisi tepi tanpa pointer. Artinya kita bisa melakukan perjalanan sebaliknya antara dua simpul.
Berikut contoh sederhana Graf tak berarah.
Pada Grafik di atas,
- Kita bisa berpindah dari A ke B
- Kita juga bisa berpindah dari B ke A
- Tepinya tidak mengandung arah.
Ini adalah contoh graf tak berarah yang memiliki jumlah simpul dan sisi berhingga tanpa bobot.
Grafik Tertimbang
Graf yang memuat bobot atau biaya pada sisi-sisinya disebut Graf berbobot. Nilai numerik umumnya mewakili biaya perpindahan dari satu simpul ke simpul lainnya. Graf Berarah dan Tidak Berarah dapat memiliki bobot pada tepinya.
Berikut contoh grafik berbobot (Directed).
- A ke B, ada tepinya, dan bobotnya 5, artinya berpindah dari A ke B akan dikenakan biaya 5.
- A menunjuk ke B, namun pada Grafik ini, B tidak memiliki tepi langsung terhadap A. Jadi, kita tidak dapat melakukan perjalanan dari B ke A.
- Namun, jika kita ingin berpindah dari A ke F, ada beberapa jalur. Jalurnya adalah ADF, ABF. ADF akan dikenakan biaya (10+11) atau 21.
- Di sini, jalur ABF akan berharga (5+15) atau 20. Di sini kita menambahkan bobot setiap tepi di jalur tersebut.
Berikut contoh Grafik Tak Berarah dengan bobot:
Di sini, tepinya memiliki bobot tetapi tidak memiliki arah. Jadi, berarti perjalanan dari titik A ke D dikenakan biaya 10 dan sebaliknya.
Grafik Dua Arah
Grafik dua arah dan tidak berarah memiliki sifat yang sama. Itu adalah
- Secara umum, Graf tak berarah dapat memiliki satu sisi di antara dua simpul.
Sebagai contoh:
- Di sini, berpindah dari A ke D atau D ke A akan dikenakan biaya 10.
- Dalam Graf Dua Arah, kita dapat memiliki dua sisi di antara dua simpul.
Berikut ini adalah contohnya:
Perjalanan dari A ke D akan dikenakan biaya 17, tetapi perjalanan dari D ke A akan dikenakan biaya 12. Jadi, kita tidak dapat menetapkan dua bobot berbeda jika grafik tersebut tidak berarah.
Grafik Tak Terbatas
Grafik akan berisi tepi dan node dalam jumlah tak terbatas. Jika suatu graf tak terhingga dan juga merupakan graf terhubung, maka graf tersebut juga mempunyai jumlah sisi yang tak terhingga. Di sini, tepi yang diperluas berarti lebih banyak tepi yang dapat dihubungkan ke node ini melalui tepi.
Berikut contoh Grafik tak hingga:
Grafik Nol
Grafik Null hanya berisi node atau simpul tetapi tanpa sisi. Jika diberikan Graf G = (V, E), dimana V adalah simpul dan E adalah sisi, maka akan bernilai nol jika jumlah sisi E sama dengan nol.
Berikut ini contoh Grafik Null:
Grafik Sepele
Suatu struktur data graf dianggap sepele jika hanya ada satu simpul atau simpul yang tidak memiliki sisi.
Berikut ini contoh Grafik Trivial:
Multi Grafik
Suatu graf disebut multigraf jika terdapat banyak sisi di antara dua simpul, atau simpul tersebut memiliki loop. Yang dimaksud dengan “Loop” dalam Struktur Data Graf adalah suatu sisi yang menunjuk pada node atau titik yang sama. Multigraf dapat diarahkan atau tidak diarahkan.
Berikut contoh Multi Grafik:
Ada dua sisi dari B ke A. Selain itu, simpul E memiliki self-loop. Graf di atas merupakan graf berarah yang tidak mempunyai bobot pada sisinya.
Grafik Lengkap
Suatu graf dikatakan lengkap jika setiap simpul mempunyai sisi berarah atau tidak berarah dengan semua simpul lainnya.
Misalkan terdapat jumlah total V simpul dan setiap simpul mempunyai tepat V-1 sisi. Kemudian Grafik ini disebut Grafik Lengkap. Dalam Graf jenis ini, setiap simpul terhubung ke semua simpul lainnya melalui sisi.
Berikut contoh Graf Lengkap dengan lima simpul:
Anda dapat melihat pada gambar jumlah total node adalah lima, dan semua node memiliki tepat empat sisi.
Grafik Terhubung
Suatu Graf disebut Graf Terhubung jika kita memulai dari sebuah node atau titik dan menempuh semua node dari node awal tersebut. Untuk ini, harus ada setidaknya satu sisi di antara setiap pasangan node atau simpul.
Berikut ini contoh Grafik Terhubung:
Berikut beberapa penjelasan dari “contoh grafik lengkap” di atas:
- Dengan asumsi tidak ada tepi antara C dan F, kita tidak dapat melakukan perjalanan dari A ke G. Namun, tepi C ke F memungkinkan kita melakukan perjalanan ke simpul mana pun dari simpul tertentu.
- Graf lengkap adalah Graf Terhubung karena kita dapat berpindah dari satu node ke node lain dalam Graf tertentu.
Grafik Siklik
Suatu graf dikatakan siklik apabila pada graf tersebut terdapat satu atau lebih siklus.
Berikut ini contoh Grafik Siklik:
Di sini, simpul A, B, dan C membentuk sebuah siklus.
Sebuah grafik dapat memiliki beberapa siklus di dalamnya.
Grafik Asiklik Terarah (DAG)
Suatu Graf disebut Graf Asiklik Terarah atau DAG jika tidak terdapat siklus di dalam suatu graf. DAG penting saat melakukan Urutan Topologis atau menemukan perintah eksekusi. DAG juga penting untuk membuat sistem penjadwalan atau memindai ketergantungan sumber daya, dll. Namun, Grafik di atas tidak berisi siklus apa pun di dalamnya.
Berikut contoh sederhana Directed Acyclic Graph (DAG):
Grafik Siklus
Grafik Siklus tidak sama dengan Grafik siklik. Dalam Grafik Siklus, setiap node akan memiliki tepat dua sisi yang terhubung, artinya setiap node akan memiliki tepat dua derajat.
Berikut ini contoh Grafik Siklus:
Graf Bipartit
Jenis ini Grafik adalah jenis Graf khusus yang simpul-simpulnya ditetapkan ke dalam dua himpunan.
Graf Bipartit harus mengikuti kaidah:
- Dua himpunan simpul harus berbeda, artinya semua simpul harus dibagi menjadi dua kelompok atau himpunan.
- Kumpulan simpul yang sama tidak boleh membentuk sisi apa pun.
Grafik Euler
Struktur data graf dianggap sebagai Graf Euler jika semua simpul mempunyai derajat genap. Istilah derajat simpul berarti jumlah sisi yang menunjuk ke atau keluar dari suatu simpul tertentu.
Berikut contoh grafik Euler:
Semua simpul mempunyai derajat genap. Titik sudut A, D, E, dan H mempunyai dua derajat. Di sini, simpul C memiliki empat derajat, yaitu genap.
Grafik Hamilton
Graf Hamilton adalah Graf Hubungkan, di mana Anda dapat mengunjungi semua simpul dari suatu simpul tertentu tanpa mengunjungi kembali simpul yang sama atau menggunakan sisi yang sama. Grafik Terhubung semacam ini dikenal sebagai “Grafik Hamilton.” Jalur yang Anda kunjungi untuk memverifikasi apakah Grafik yang diberikan adalah Grafik Hamilton atau bukan dikenal sebagai Jalur Hamilton.
Berikut contoh grafik sederhana dari Hamilton:
Pada gambar ini, kita dapat mengunjungi semua simpul dari node mana pun pada Grafik di atas. Salah satu caranya bisa saja ADCHBE. Dimungkinkan juga untuk menemukan Siklus Hamilton. Siklus Hamilton bermula dan berakhir pada titik sudut yang sama. Jadi, Siklus Hamilton akan menjadi ADCHBEA.