Struktur Data Grafik

Isi kandungan

Terminologi Graf
Perwakilan Graf
Operasi Grafik

Dalam tutorial ini, anda akan belajar apa itu Struktur Data Grafik. Anda juga akan mendapat gambaran grafik.

Struktur data grafik adalah kumpulan nod yang mempunyai data dan disambungkan ke nod lain.

Mari cuba fahami ini melalui contoh. Di facebook, semuanya adalah node. Itu termasuk Pengguna, Foto, Album, Acara, Kumpulan, Halaman, Komen, Cerita, Video, Pautan, Catatan … apa sahaja yang mempunyai data adalah simpul.

Setiap hubungan adalah kelebihan dari satu simpul ke simpul yang lain. Sama ada anda menyiarkan foto, menyertai kumpulan, seperti halaman, dll., Kelebihan baru dibuat untuk hubungan itu.

Contoh struktur data grafik

Semua facebook kemudiannya merupakan kumpulan simpul dan tepi ini. Ini kerana facebook menggunakan struktur data grafik untuk menyimpan datanya.

Lebih tepat lagi, grafik adalah struktur data (V, E) yang terdiri daripada

Kumpulan simpul V
Koleksi tepi E, diwakili sebagai pasangan bucu yang disusun (u, v)

Tegak dan tepi

Dalam grafik,

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

Terminologi Graf

Adjacency : Bucu dikatakan bersebelahan dengan bucu lain jika ada tepi yang menghubungkannya. Tegak 2 dan 3 tidak bersebelahan kerana tidak ada tepi di antara mereka.
Laluan : Urutan tepi yang membolehkan anda pergi dari bucu A ke bucu B disebut jalan. 0-1, 1-2 dan 0-2 adalah jalan dari bucu 0 ke bucu 2.
Graf Terarah : Grafik di mana pinggir (u, v) tidak semestinya bermaksud bahawa ada tepi (v, u) juga. Tepi dalam grafik sedemikian dilambangkan dengan anak panah untuk menunjukkan arah tepi.

Perwakilan Graf

Grafik biasanya ditunjukkan dalam dua cara:

1. Matriks Adjacency

Matriks adjacency ialah susunan 2D bucu V x V. Setiap baris dan lajur mewakili bucu.

Sekiranya nilai unsur mana pun a(i)(j)adalah 1, ia menunjukkan bahawa ada tepi yang menghubungkan bucu i dan bucu j.

Matriks adjacency untuk grafik yang kami buat di atas adalah

Matriks adjacency graf

Oleh kerana ia adalah graf yang tidak diarahkan, untuk tepi (0,2), kita juga perlu menandakan tepi (2,0); menjadikan matriks adjacency simetrik mengenai pepenjuru.

Pencarian tepi (memeriksa apakah ada tepi antara bucu A dan bucu B) sangat cepat dalam perwakilan matriks adjacency tetapi kita harus menempah ruang untuk setiap kemungkinan hubungan antara semua bucu (V x V), jadi ia memerlukan lebih banyak ruang.

2. Senarai Kecukupan

Senarai adjacency mewakili grafik sebagai susunan senarai terpaut.

Indeks array mewakili bucu dan setiap elemen dalam senarai terpautnya mewakili bucu lain yang membentuk pinggir dengan bucu.

Senarai adjacency untuk grafik yang kami buat pada contoh pertama adalah seperti berikut:

Perwakilan senarai kecukupan

Senarai adjacency adalah cekap dari segi penyimpanan kerana kita hanya perlu menyimpan nilai untuk tepi. Untuk graf dengan berjuta-juta bucu, ini boleh bermakna banyak ruang yang dijimatkan.