Struktur Data Grafik dan Algorithms (Contoh)
Sarah Chen
⚡ Ringkasan Cerdas
Struktur Data Graf adalah kumpulan simpul dan sisi non-linier di mana setiap sisi menghubungkan sepasang simpul. Graf memodelkan jaringan dunia nyata seperti peta, koneksi sosial, dan halaman web, serta mendukung banyak algoritma yang ampuh.
Apa itu Grafik dalam Struktur Data?
Graf adalah struktur data non-linier yang terdiri dari simpul dan sisi, di mana simpul berisi informasi atau data, dan sisi berfungsi sebagai penghubung antara sepasang simpul.
Metode ini digunakan untuk memecahkan masalah dunia nyata seperti menemukan rute terbaik ke lokasi tujuan dan rute untuk telekomunikasi serta jejaring sosial. Pengguna dianggap sebagai simpul dalam Graf, 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 adalah contoh sederhana dari struktur data grafik:
Ini adalah graf tak berarah sederhana (salah satu jenis graf). Himpunan simpulnya adalah: {A, B, C, D, E, F}. Dua simpul membentuk sebuah sisi. Misalnya, A dan B dihubungkan dengan sebuah sisi. Namun, A dan F tidak dihubungkan dengan sisi apa pun.
Terminologi Grafik dalam Struktur Data
Berikut adalah beberapa istilah penting yang digunakan dalam struktur data graf:
| Istilah | Deskripsi |
|---|---|
| Puncak | Setiap elemen data disebut simpul atau node. Pada gambar di atas, A, B, C, D & E adalah simpul-simpulnya. |
| Tepi (Busur) | Hubungan yang menghubungkan dua simpul atau titik disebut sisi (busur). Sisi memiliki dua ujung dan direpresentasikan sebagai (titik awal, titik akhir). |
| Tepi Tidak Terarah | Ini adalah tepi dua arah. |
| Tepi Terarah | Ini adalah tepi satu arah. |
| Tepi Tertimbang | Sisi yang memiliki nilai. |
| Derajat | Dalam sebuah graf, jumlah sisi yang terhubung ke suatu simpul 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 | Titik-titik sudut dikatakan bersebelahan jika terdapat sisi yang menghubungkan keduanya. |
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
Bagaimana cara merepresentasikan graf dalam struktur data?
Graf umumnya disimpan dalam memori menggunakan salah satu dari dua representasi. Pilihan ini memengaruhi seberapa banyak memori yang digunakan graf dan seberapa cepat operasi umum dijalankan.
- Matriks Kedekatan: Sebuah array dua dimensi V × V di mana sel [i][j] bernilai 1 (atau bobot tepi) jika terdapat tepi antara simpul i dan simpul j, dan 0 jika tidak. Array ini memungkinkan pencarian tepi O(1) tetapi menggunakan ruang O(V²), sehingga paling cocok untuk graf padat.
- Daftar Kedekatan: Sebuah array berisi daftar di mana setiap simpul menyimpan daftar simpul tetangganya. Array ini menggunakan ruang O(V + E) dan efisien untuk graf jarang (sparse graph), itulah sebabnya sebagian besar graf di dunia nyata menggunakannya.
Anda dapat membaca lebih lanjut tentang hal ini di Daftar keterkaitan dan representasi matriks dari sebuah graf. tutorial.
Penerapan Struktur Data Grafik
Graf memiliki banyak kegunaan. Ada banyak algoritma yang menggunakan graf. Berikut beberapa aplikasi graf:
- Google Aplikasi peta menggunakan grafik untuk menemukan titik persimpangan dua jalan dan menghitung jarak antara dua lokasi. Misalnya, Dijkstrauntuk menemukan jarak terpendek antara lokasi sumber dan tujuan.
- Facebook menggunakan Graph untuk menemukan teman bersama antar pengguna. Algoritma yang digunakannya menganggap setiap pengguna sebagai simpul (node) dalam sebuah graph.
- Untuk alokasi sumber daya, digunakan DAG (Directed Acyclic Graph). DAG memeriksa ketergantungan antar sumber daya.
- The Google Mesin pencari menggunakan grafik untuk membuat peringkat situs web.
- Sebuah petaping Perangkat ini menggunakan struktur data grafik.
- A router dan protokolnya menggunakan Graph untuk mempelajari jalur ke tujuan.
