Jenis-Jenis Grafik dalam Struktur Data Beserta Contohnya
Sarah Chen
⚡ Ringkasan Cerdas
Dalam struktur data, graf adalah kumpulan simpul dan sisi non-linier yang diklasifikasikan ke dalam beberapa keluarga berdasarkan strukturnya, seperti graf berarah, tak berarah, berbobot, siklik, asiklik, lengkap, terhubung, bipartit, Euler, dan Hamilton.
Graf adalah struktur data non-linier yang terdiri dari simpul (vertex) dan sisi (edge). Simpul berisi informasi atau data, dan sisi berfungsi sebagai penghubung antara sepasang simpul.
Graf dapat berupa berbagai jenis, tergantung pada posisi simpul dan sisinya. Berikut beberapa jenis graf yang penting:
Grafik Sutradara
Sisi-sisi pada graf berarah berisi panah yang menunjukkan arah. Panah tersebut menentukan ke mana sisi tersebut mengarah atau berakhir. Berikut adalah contoh graf berarah.
Grafik Sutradara
- Kita bisa berpindah dari Node A ke D.
- Namun, kita tidak dapat pergi dari simpul D ke simpul A, karena sisi tersebut mengarah 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
Graf tak berarah berisi sisi tanpa penunjuk. Artinya, kita dapat melakukan perjalanan bolak-balik antara dua simpul. Berikut adalah contoh sederhana dari graf tak berarah.
Grafik Tidak 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 terbatas dan sisi tanpa bobot.
Grafik Tertimbang
Graf yang memiliki bobot atau biaya pada sisi-sisinya disebut graf berbobot. Nilai numerik umumnya mewakili biaya perpindahan dari satu simpul ke simpul lainnya. Baik graf berarah maupun tak berarah dapat memiliki bobot pada sisi-sisinya. Berikut adalah contoh graf berbobot (berarah).
Grafik Terarah dengan bobot
- Dari A ke B, ada sisi, dan beratnya 5, yang berarti pindah dari A ke B akan membutuhkan biaya 5.
- A menunjuk ke B, tetapi dalam grafik ini, B tidak memiliki sisi langsung ke A. Jadi, kita tidak dapat melakukan perjalanan dari B ke A.
- Namun, jika kita ingin berpindah dari A ke F, ada beberapa jalur. Jalur-jalur tersebut adalah ADF dan ABF. ADF akan membutuhkan biaya (10+11) atau 21.
- Di sini, jalur ABF akan membutuhkan biaya (5+15) atau 20. Di sini kita menambahkan bobot setiap sisi dalam jalur tersebut.
Berikut adalah contoh Graf Tak Berarah dengan bobot:
Grafik Tidak 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
Graf dua arah dan graf tak berarah memiliki sifat yang sama. Yaitu:
- Secara umum, graf tak berarah dapat memiliki satu sisi yang menghubungkan 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 contohnya:
Grafik Dua Arah
Perjalanan dari A ke D akan memakan biaya 17, tetapi perjalanan dari D ke A akan memakan biaya 12. Jadi, kita tidak dapat memberikan dua bobot yang berbeda jika itu adalah graf tak berarah.
Grafik Tak Terbatas
Graf tersebut akan berisi jumlah sisi dan simpul yang tak terbatas. Jika suatu graf bersifat tak terbatas dan juga merupakan graf terhubung, maka graf tersebut juga akan berisi jumlah sisi yang tak terbatas. Di sini, sisi yang diperpanjang berarti bahwa lebih banyak sisi mungkin terhubung ke simpul-simpul ini melalui sisi-sisi lain. Berikut adalah contoh graf tak terbatas:
Grafik Tak Terbatas
Grafik Nol
Graf Nol hanya berisi simpul atau verteks tetapi tidak memiliki sisi. Jika diberikan Graf G = (V, E), di mana V adalah verteks dan E adalah sisi, maka graf tersebut akan menjadi graf nol jika jumlah sisi E adalah nol. Berikut adalah contoh Graf Nol:
Grafik Nol
Grafik Sepele
Struktur data graf dianggap trivial jika hanya memiliki satu simpul atau node tanpa sisi. Berikut contoh Graf Trivial:
Multi Grafik
Suatu graf disebut multigraf ketika terdapat banyak sisi (edge) antara dua simpul (vertex), atau simpul tersebut memiliki loop. Istilah "Loop" dalam Struktur Data Graf berarti sisi yang mengarah ke simpul atau vertex yang sama. Multigraf dapat berupa graf berarah atau tak berarah. Berikut adalah contoh Multigraf:
Terdapat dua sisi dari B ke A. Selain itu, simpul E memiliki loop sendiri. Graf di atas adalah graf berarah tanpa bobot pada sisi-sisinya.
Grafik Lengkap
Suatu graf dikatakan lengkap jika setiap simpul memiliki sisi berarah atau tak berarah yang terhubung dengan semua simpul lainnya. Misalkan terdapat total V simpul dan setiap simpul memiliki tepat V-1 sisi. Maka, graf ini akan disebut graf lengkap. Pada jenis graf ini, setiap simpul terhubung ke semua simpul lainnya melalui sisi. Berikut adalah contoh graf lengkap dengan lima simpul:
Anda dapat melihat pada gambar bahwa jumlah total node adalah lima, dan semua node memiliki tepat empat sisi.
Grafik Terhubung
Suatu graf disebut graf terhubung jika kita mulai dari sebuah simpul atau verteks dan dapat berpindah ke semua simpul dari simpul awal tersebut. Untuk itu, harus ada setidaknya satu sisi di antara setiap pasangan simpul atau verteks. Berikut adalah contoh graf terhubung:
Berikut penjelasan mengenai Connected Graph di atas:
- Dengan asumsi tidak ada sisi antara C dan F, kita tidak dapat melakukan perjalanan dari A ke G. Namun, sisi C ke F memungkinkan kita untuk 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 jika terdapat satu atau lebih siklus di dalam graf tersebut. Berikut adalah contoh graf siklik:
Di sini, simpul A, B, dan C membentuk sebuah siklus. Sebuah graf dapat memiliki banyak siklus di dalamnya.
Grafik Asiklik Terarah (DAG)
Suatu graf disebut graf berarah asiklik atau DAG jika tidak terdapat siklus di dalam graf tersebut. DAG penting saat melakukan Urutan Topologis atau untuk menemukan urutan eksekusi. DAG juga penting untuk membuat sistem penjadwalan atau memindai ketergantungan sumber daya, dll. Namun, grafik di atas tidak mengandung siklus di dalamnya. Berikut adalah contoh sederhana dari Directed Acyclic Graph (DAG):
Grafik Siklus
Graf Siklus tidak sama dengan Graf Siklik. Dalam Graf Siklus, setiap simpul akan memiliki tepat dua sisi yang terhubung, artinya setiap simpul akan memiliki tepat dua derajat. Berikut adalah contoh Graf Siklus:
Graf Bipartit
Jenis ini Grafik adalah jenis graf khusus di mana simpul-simpulnya ditugaskan ke dua himpunan. Graf bipartit harus mengikuti aturan:
- Kedua himpunan simpul harus berbeda, yang berarti semua simpul harus dibagi menjadi dua kelompok atau himpunan.
- Simpul-simpul dalam himpunan yang sama tidak boleh membentuk sisi apa pun.
Grafik Euler
Struktur data Graf dianggap sebagai Graf Euler jika semua simpulnya memiliki derajat genap. Istilah derajat simpul berarti jumlah sisi yang mengarah ke atau keluar dari simpul tertentu. Berikut adalah contoh graf Euler:
Semua simpul memiliki derajat genap. Simpul A, D, E, dan H memiliki dua derajat. Di sini, simpul C memiliki empat derajat, yang merupakan bilangan genap.
Grafik Hamilton
Graf Hamilton adalah Graf Terhubung, di mana Anda dapat mengunjungi semua simpul dari simpul tertentu tanpa mengunjungi kembali simpul yang sama atau menggunakan sisi yang sama. Graf Terhubung jenis ini dikenal sebagai "Grafik Hamilton". Jalur yang Anda kunjungi untuk memverifikasi apakah Graf yang diberikan adalah Graf Hamilton atau bukan dikenal sebagai Jalur Hamiltonian. Berikut adalah contoh graf Hamilton sederhana:
Pada gambar ini, kita dapat mengunjungi semua simpul dari node mana pun pada Grafik di atas. Salah satu caranya bisa saja ADCHBEDimungkinkan juga untuk menemukan Siklus Hamilton. Siklus Hamilton dimulai dan berakhir pada titik sudut yang sama. Jadi, Siklus Hamilton akan menjadi... ADCHBEA.
