Struktur Data Grafik dan Algorithms (Contoh)
Sarah Chen
Apa itu Grafik dalam Struktur Data?
Graf adalah suatu struktur data nonlinier yang terdiri dari simpul dan sisi, dimana simpul berisi informasi atau data, dan sisi tersebut berfungsi sebagai penghubung antar pasangan simpul.
Ini digunakan untuk memecahkan masalah nyata seperti menemukan rute terbaik ke lokasi tujuan dan rute untuk telekomunikasi dan jejaring sosial. Pengguna dianggap sebagai simpul dalam Grafik, dan kabel adalah sisi yang menghubungkan pengguna.
Jika sisi direpresentasikan sebagai E dan simpul direpresentasikan sebagai V, maka graf G dapat ditulis sebagai himpunan simpul dan sisi, seperti G (V, E)
Contoh Grafik dalam Struktur Data
Berikut contoh sederhana struktur data grafik:
Ini adalah grafik sederhana tidak berarah (salah satu jenis Grafik). Di sini himpunan titik sudutnya adalah: {A, B, C,D,E,F}. Dua simpul menciptakan sebuah tepi. Misalnya A dan B dihubungkan dengan sebuah rusuk. Namun, A dan F tidak terhubung dengan sisi mana pun.
Terminologi Grafik dalam Struktur Data
Berikut ini adalah beberapa istilah penting yang digunakan dalam struktur data grafik:
| Istilah | Description |
|---|---|
| Puncak | Semua elemen data disebut simpul atau simpul. Pada gambar di atas, A, B, C, D & E adalah simpulnya. |
| Tepi (Busur) | Tautan yang menghubungkan antara dua node atau simpul disebut tepi (Arc). Ini memiliki dua ujung dan direpresentasikan sebagai (Vertex awal, Vertex akhir). |
| Tepi Tidak Terarah | Ini adalah tepi dua arah. |
| Tepi Terarah | Ini adalah tepi satu arah. |
| Tepi Tertimbang | Sebuah keunggulan dengan nilai di atasnya. |
| Derajat | Dalam Graf, banyaknya sisi yang terhubung pada suatu titik disebut derajat. |
| derajat dalam | Jumlah total sisi masuk yang terhubung ke sebuah titik. |
| Derajat keluar | Jumlah total sisi keluar yang terhubung ke sebuah titik. |
| Putaran mandiri | Suatu sisi disebut self-loop jika kedua titik ujungnya berimpit. |
| Kedekatan | Simpul-simpul dikatakan bertetangga jika suatu sisi terhubung. |
Jenis Grafik dalam Struktur Data
Berikut adalah daftar yang paling umum jenis grafik dalam struktur data:
- Grafik Sutradara
- Grafik Tidak Berarah
- Grafik Tertimbang
- Grafik Dua Arah
- Grafik Tak Terbatas
- Grafik Nol
- Grafik Sepele
- Multi Grafik
- Grafik Lengkap
- Grafik Terhubung
- Grafik Siklik
- Grafik Asiklik Terarah (DAG)
- Grafik Siklus
- Graf Bipartit
- Grafik Euler
- Grafik Hamilton
Penerapan Struktur Data Grafik
Grafik memiliki banyak kasus penggunaan. Ada banyak algoritma yang banyak menggunakan Grafik. Berikut beberapa penerapan Grafik:
- Google Maps menggunakan grafik untuk menemukan persimpangan dua jalan dan menghitung jarak antara dua lokasi.
Sebagai contoh, Dijkstra, untuk mencari jarak terpendek antara lokasi sumber dan tujuan. - Facebook menggunakan Grafik untuk menemukan teman bersama para pengguna. Algoritmenya menganggap setiap pengguna sebagai simpul grafik.
- Untuk alokasi sumber daya, DAG (Direct Acyclic Graph) digunakan. Ini memeriksa ketergantungan sumber daya.
- Mesin Pencari Google menggunakan grafik untuk membuat peringkat situs web.
- Perangkat pemetaan menggunakan struktur data grafik.
- router dan protokol t menggunakan Grafik untuk mempelajari jalur jalur tujuan.
