Dapatkan intipati struktur data graf di sini...

Blog ini adalah untuk pembangun yang ingin mendapatkan intipati sesuatu konsep dan tidak berdepan masalah. Kami akan memahami struktur data graf dalam siaran ini. Mari kita mulakan.

Apakah itu Graf?

Graf ialah struktur data bukan linear dengan 2 komponen iaitu tepi dan nod.

Nod ialah: -

1. unit asas graf,
2. juga dikenali sebagai bucu atau bucu, dan
3. boleh dilabel atau tidak dilabel.

Sesuatu kelebihan ialah:-

1. sambungan antara dua nod,
2. juga dikenali sebagai arka dan
3. boleh dilabel atau tidak dilabel.

Jenis graf: -

1. Graf nol: Ia tidak mempunyai tepi,
2. Graf trival: Ia hanya mempunyai satu nod,
3. Graf kitaran: Ia mengandungi sekurang-kurangnya satu kitaran,
4. Graf kitaran: Semua nod disambungkan untuk membuat satu kitaran,
5. Graf terarah: Tepinya mempunyai arah,
6. Graf tidak berarah: Tepinya tidak mempunyai sebarang arah,
7. Graf berwajaran: Beberapa nilai ditetapkan pada setiap tepi,
8. Graf yang disambungkan: Kita boleh melawat mana-mana nod lain dari satu nod (ia tidak semestinya tepi yang unik),
9. Graf tidak bersambung: Sekurang-kurangnya satu nod diputuskan sambungan daripada nod,
10. Graf biasa: Setiap bucu mempunyai bilangan jiran yang sama,
11. Graf lengkap: Setiap nod disambungkan ke nod lain melalui tepi yang unik,
12. Graf asiklik terarah: Graf terarah tanpa kitaran,
13. Graf dwipartit: Nodnya boleh dibahagikan kepada 2 set supaya tiada tepi wujud di antara set.

Bagaimanakah kita menyimpan graf?

Ada 2 cara:

1. Matriks bersebelahan, dan
2. Matriks bersebelahan

matriks bersebelahan ialah matriks 2-D yang mewakili struktur data graf. Baris dan lajur mewakili nod dan nilai dalam matriks mewakili tepi.

Dalam imej di atas, 4 nod disambungkan oleh tepi. Nod A disambungkan kepada semua nod dan dengan itu nilai ditambah sebagai 1 dalam sel di mana A (sama ada baris atau lajur) bersilang dengan baris atau lajur nod lain. Nod B hanya disambungkan kepada Nod A menghasilkan nilai 1 dalam sel di mana nod B bersilang dengan nod A dan sel lain mempunyai nilai 0.

Kerumitan masa untuk menambah atau memadam kelebihan bagi matriks bersebelahan ialah O(1). Ia boleh digunakan apabila: -

1. graf mempunyai tepi maksimum yang mungkin,
2. tiada kekangan ingatan, dan
3. graf mempunyai struktur yang kompleks.

senarai bersebelahan menyimpan graf dengan bantuan berbilang senarai terpaut atau tatasusunan. Baris mewakili nod (semak imej di bawah), dan nilai yang terdapat dalam baris mewakili jiran.

Dalam imej di atas, terdapat 5 nod. Nod A disambungkan kepada nod B dan nod D itulah sebabnya tatasusunan pertama mempunyai nilai tersebut. Begitu juga, nod B disambungkan kepada nod A, nod C, nod D, dan nod E dan oleh itu tatasusunan kedua mempunyai nod tersebut dalam tatasusunan kedua.

Kerumitan masa untuk mendapatkan semula atau memadamkan tepi ialah O(n) dan kerumitan masa untuk menambah tepi ialah O(1). Senarai bersebelahan boleh digunakan apabila: -

1. nod mempunyai lebih sedikit tepi,
2. terdapat kekangan ingatan, dan
3. graf adalah kurang kompleks.

Rajah: Perbandingan visual antara senarai bersebelahan dan matriks bersebelahan.

Gunakan kes untuk graf

Satu contoh popular struktur data graf ialah: dalam bidang bola sepak setiap pemain boleh dianggap sebagai nod dan interaksi mereka mewakili tepi.

Graf digunakan dalam senario yang serupa seperti contoh sebelumnya, seperti: -

1. dalam rangkaian sosial di mana semua orang adalah nod,
2. dalam rangkaian komputer di mana PC dan penghala adalah nod,
3. dalam rangkaian pengangkutan, dan seterusnya...

Atas ialah kandungan terperinci Dapatkan intipati struktur data graf di sini.... Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!