Panduan kepada Struktur Data Graf

Panduan kepada Struktur Data Graf

Pengaturcara yang berkesan memerlukan pemahaman yang kukuh tentang struktur data dan algoritma. Temu bual teknikal selalunya akan menguji kemahiran menyelesaikan masalah dan pemikiran kritis anda.





Graf adalah salah satu daripada banyak struktur data penting dalam pengaturcaraan. Dalam kebanyakan kes, memahami graf dan menyelesaikan masalah berasaskan graf bukanlah sesuatu yang mudah.



permainan percuma yang menyeronokkan untuk dimainkan apabila anda bosan
MAKEUSEOF VIDEO OF THE DAY

Apakah itu graf, dan apakah yang anda perlu tahu mengenainya?





Apakah itu Graf?

Graf ialah struktur data bukan linear yang mempunyai nod (atau bucu) dengan tepi yang menghubungkannya. Semua pokok ialah subjenis graf, tetapi bukan semua graf ialah pokok, dan graf ialah struktur data dari mana pokok berasal.

cara menjalankan windows xp pada windows 10
Perwakilan visual graf

Walaupun anda boleh membina struktur data dalam JavaScript dan bahasa lain, anda boleh melaksanakan graf dalam pelbagai cara. Pendekatan yang paling popular ialah senarai tepi , senarai bersebelahan , dan matriks bersebelahan .



The Khan Academy panduan untuk mewakili graf ialah sumber yang bagus untuk belajar tentang cara mewakili graf.

Terdapat pelbagai jenis graf. Satu perbezaan umum adalah antara diarahkan dan tidak terarah graf; ini banyak timbul dalam cabaran pengekodan dan penggunaan dalam kehidupan sebenar.



Jenis-jenis Graf

  1. Graf terarah: Graf di mana semua tepi mempunyai arah, juga dirujuk sebagai digraf. Graf terarah
  2. Graf tidak terarah: Graf tidak berarah juga dikenali sebagai graf dua hala. Dalam graf tidak terarah, arah tepi tidak penting dan traversal boleh pergi ke mana-mana arah.
  3. Graf berwajaran: Graf berwajaran ialah graf yang nod dan tepinya mempunyai nilai yang berkaitan. Dalam kebanyakan kes, nilai ini mewakili kos meneroka nod atau tepi itu.
  4. Graf terhingga: Graf yang mempunyai bilangan nod dan tepi yang terhingga.
  5. Graf tak terhingga: Graf yang mempunyai jumlah nod dan tepi yang tidak terhingga.
  6. Graf remeh: Graf yang hanya mempunyai satu nod dan tiada tepi.
  7. Graf mudah: Apabila hanya satu tepi menghubungkan setiap pasangan nod graf, ia dipanggil graf ringkas.
  8. Graf nol: Graf nol ialah graf yang tidak mempunyai tepi yang menghubungkan nodnya.
  9. Multigraf: Dalam multigraf, sekurang-kurangnya sepasang nod mempunyai lebih daripada satu tepi yang menghubungkannya. Dalam multigraf, tiada gelung kendiri.
  10. Graf lengkap: Graf lengkap ialah graf di mana setiap nod bersambung dengan setiap nod lain dalam graf. Ia juga dikenali sebagai a graf penuh .
  11. Graf pseudo: Graf yang mempunyai gelung kendiri selain daripada tepi graf lain dipanggil graf pseudo.
  12. Graf biasa: Graf biasa ialah graf di mana semua nod mempunyai darjah yang sama; iaitu setiap nod mempunyai bilangan jiran yang sama.
  13. Graf bersambung: Graf bersambung hanyalah sebarang graf di mana mana-mana dua nod bersambung; iaitu graf dengan sekurang-kurangnya satu laluan antara setiap dua nod graf.
  14. Graf terputus sambungan: Graf terputus adalah bertentangan langsung dengan graf bersambung. Dalam graf terputus, tiada tepi yang menghubungkan nod graf, seperti dalam null graf.
  15. Graf kitaran: Graf kitaran ialah graf yang mengandungi sekurang-kurangnya satu kitaran graf (laluan yang berakhir di mana ia bermula).
  16. Graf asiklik: Graf asiklik ialah graf tanpa kitaran sama sekali. Ia boleh sama ada diarahkan atau tidak diarahkan.
  17. Subgraf: Subgraf ialah graf terbitan. Ia ialah graf yang terbentuk daripada nod dan tepi yang merupakan subset graf lain.