Grafik Struktur Data

Grafik Struktur Data

Dalam tutorial ini, Anda akan mempelajari apa itu Graph Data Structure. Juga, Anda akan menemukan representasi grafik.

Struktur data grafik adalah kumpulan node yang memiliki data dan terhubung ke node lain.

Mari kita coba memahami ini melalui sebuah contoh. Di facebook, semuanya adalah simpul. Itu termasuk Pengguna, Foto, Album, Acara, Grup, Halaman, Komentar, Cerita, Video, Tautan, Catatan … apa pun yang memiliki data adalah simpul.

Setiap hubungan adalah tepi dari satu node ke node lainnya. Baik Anda memposting foto, bergabung dengan grup, menyukai halaman, dll., Tepi baru dibuat untuk hubungan itu.

struktur data grafik dijelaskan menggunakan contoh facebook.  Pengguna, grup, halaman, acara, dll. Direpresentasikan sebagai node dan hubungannya - teman, bergabung dengan grup, menyukai halaman direpresentasikan sebagai link antar node
Contoh struktur data grafik

Semua facebook kemudian merupakan kumpulan node dan tepi ini. Hal ini dikarenakan facebook menggunakan struktur data grafik untuk menyimpan datanya.

Lebih tepatnya, grafik adalah struktur data (V, E) yang terdiri dari

  • Kumpulan simpul V
  • Kumpulan tepi E, direpresentasikan sebagai pasangan simpul terurut (u, v)
sebuah grafik berisi simpul yang seperti titik dan tepi yang menghubungkan titik-titik tersebut
Simpul dan tepi

Dalam grafik,

V = {0, 1, 2, 3}
E = {(0,1), (0,2), (0,3), (1,2)}
G = {V, E}

Terminologi Grafik

  • Kedekatan: Sebuah simpul dikatakan berdampingan dengan simpul lain jika ada sebuah sisi yang menghubungkannya. Simpul 2 dan 3 tidak berdekatan karena tidak ada tepi di antara keduanya.
  • Jalan: Urutan sisi-sisi yang memungkinkan Anda berpindah dari simpul A ke simpul B disebut jalur. 0-1, 1-2 dan 0-2 adalah lintasan dari simpul 0 ke simpul 2.
  • Grafik Berarah: Grafik di mana sisi (u, v) tidak selalu berarti bahwa ada sisi (v, u) juga. Tepi dalam grafik seperti itu diwakili oleh panah untuk menunjukkan arah tepi.

Representasi Grafik

Grafik biasanya direpresentasikan dalam dua cara:

1. Matriks Adjacency

Matriks ketetanggaan adalah larik 2D dari simpul V x V. Setiap baris dan kolom mewakili sebuah simpul.

Jika nilai elemen apa saja a[i][j] adalah 1, ini menunjukkan bahwa ada sebuah tepi yang menghubungkan simpul i dan simpul j.

Matriks ketetanggaan untuk grafik yang kita buat di atas adalah

Matriks ketetanggaan graf untuk graf sampel menunjukkan bahwa nilai elemen matriks adalah 1 untuk baris dan kolom yang memiliki sisi dan 0 untuk baris dan kolom yang tidak memiliki sisi.
Buat grafik matriks ketetanggaan

Karena ini adalah graf tidak berarah, untuk tepi (0,2), kita juga perlu menandai tepi (2,0); membuat matriks kedekatan simetris dengan diagonal.

Pencarian tepi (memeriksa apakah ada tepi antara simpul A dan simpul B) sangat cepat dalam representasi matriks ketetanggaan tetapi kita harus mencadangkan ruang untuk setiap kemungkinan tautan antara semua simpul (V x V), sehingga membutuhkan lebih banyak ruang.

2. Daftar Kedekatan

Daftar kedekatan mewakili grafik sebagai larik daftar tertaut.

Indeks dari array mewakili sebuah simpul dan setiap elemen dalam daftar tertautnya mewakili simpul lain yang membentuk sebuah sisi dengan simpul tersebut.

Daftar kedekatan untuk grafik yang kita buat pada contoh pertama adalah sebagai berikut:

representasi daftar ketetanggaan merepresentasikan grafik sebagai larik dari daftar tertaut di mana indeks mewakili puncak dan setiap elemen dalam daftar tertaut mewakili tepi-tepi yang terhubung ke simpul tersebut
Representasi daftar kedekatan

Daftar kedekatan efisien dalam hal penyimpanan karena kita hanya perlu menyimpan nilai tepinya. Untuk grafik dengan jutaan simpul, ini berarti banyak ruang yang dihemat.


Operasi Grafik

Operasi grafik yang paling umum adalah:

  • Periksa apakah elemen ada dalam grafik
  • Grafik Traversal
  • Tambahkan elemen (puncak, tepi) ke grafik
  • Menemukan jalur dari satu titik ke titik lainnya