Grafik Struktur Data

Daftar Isi

Terminologi Grafik
Representasi Grafik
Operasi Grafik

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 User, Photo, Album, Event, Group, Page, Comment, Story, Video, Link, Note… apapun yang memiliki data adalah node.

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.

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)

Simpul dan tepi

Dalam grafik,

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

Terminologi Grafik

Adjacency : Sebuah simpul dikatakan berdekatan dengan simpul lain jika ada sebuah tepi yang menghubungkannya. Simpul 2 dan 3 tidak berdekatan karena tidak ada tepi di antara keduanya.
Path : Urutan tepi yang memungkinkan Anda untuk pergi dari simpul A ke simpul B disebut jalur. 0-1, 1-2 dan 0-2 adalah lintasan dari simpul 0 ke simpul 2.
Graf Berarah : Grafik di mana sebuah 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 dari salah satu elemen a(i)(j)adalah 1, ini menyatakan bahwa ada sisi yang menghubungkan simpul i dan simpul j.

Matriks adjacency untuk grafik yang kita buat di atas adalah

Buat grafik matriks adjacency

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 hubungan 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 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.