Vodič za strukturu podataka grafikona

Vodič za strukturu podataka grafikona

Učinkovit programer treba solidno razumijevanje struktura podataka i algoritama. Tehnički intervjui često će testirati vaše vještine rješavanja problema i kritičkog razmišljanja.





Grafovi su jedna od mnogih važnih struktura podataka u programiranju. U većini slučajeva razumijevanje grafova i rješavanje problema temeljenih na grafovima nije lako.



MAKEUSEOF VIDEO DANA

Što je graf i što trebate znati o njemu?





Što je grafikon?

Graf je nelinearna podatkovna struktura koja ima čvorove (ili vrhove) s rubovima koji ih povezuju. Sva stabla su podvrste grafova, ali nisu svi grafovi stabla, a graf je struktura podataka iz koje stabla potječu.

Vizualni prikaz grafa

Iako možete izgraditi strukture podataka u JavaScriptu i drugim jezicima, možete implementirati graf na razne načine. Najpopularniji pristupi su rubne liste , liste susjedstva , i matrice susjedstva .



The Khan Academy vodič za predstavljanje grafova odličan je izvor za učenje o tome kako prikazati graf.

Postoji mnogo različitih vrsta grafikona. Jedna uobičajena razlika je između usmjerena i neusmjeren grafovi; oni se često pojavljuju u izazovima kodiranja iu stvarnom životu.



Vrste grafova

  1. Usmjereni graf: Graf u kojem svi rubovi imaju smjer, također se naziva digraf. Usmjereni graf
  2. Neusmjereni graf: Neusmjereni graf je također poznat kao dvosmjerni graf. U neusmjerenim grafovima, smjer rubova nije bitan, a obilazak može ići u bilo kojem smjeru.
  3. Ponderirani grafikon: Ponderirani graf je graf čiji čvorovi i rubovi imaju pridruženu vrijednost. U većini slučajeva ova vrijednost predstavlja trošak istraživanja tog čvora ili ruba.
  4. Konačni graf: Graf koji ima konačan broj čvorova i rubova.
  5. Beskonačni graf: Graf koji ima beskonačnu količinu čvorova i rubova.
  6. Trivijalni graf: Graf koji ima samo jedan čvor i nema ruba.
  7. Jednostavan grafikon: Kada samo jedan rub povezuje svaki par čvorova grafa, naziva se jednostavnim grafom.
  8. Nulti graf: Nulti graf je graf koji nema rubove koji povezuju njegove čvorove.
  9. Multigraf: U multigrafu, barem par čvorova ima više od jednog ruba koji ih povezuje. U multigrafima nema samopetlji.
  10. Potpuni grafikon: Potpuni graf je graf u kojem se svaki čvor povezuje sa svakim drugim čvorom u grafu. Također je poznat kao a puni graf .
  11. Pseudo graf: Graf koji ima samopetlju osim ostalih rubova grafa naziva se pseudograf.
  12. Uobičajeni grafikon: Regularni graf je graf u kojem svi čvorovi imaju jednake stupnjeve; tj. svaki čvor ima isti broj susjeda.
  13. Povezani graf: Povezani graf je jednostavno bilo koji graf u kojem se spajaju bilo koja dva čvora; tj. graf s najmanje jednom stazom između svaka dva čvora grafa.
  14. Isključeni grafikon: Nepovezani graf je izravna suprotnost povezanom grafu. U nepovezanom grafu, nema rubova koji povezuju čvorove grafa, kao što je u a ništavan graf.
  15. Ciklični grafikon: Ciklički graf je graf koji sadrži najmanje jedan ciklus grafa (put koji završava tamo gdje je započeo).
  16. Aciklički graf: Aciklički graf je graf bez ikakvih ciklusa. Može biti usmjeren ili neusmjeren.
  17. Podgraf: Podgraf je izvedeni graf. To je graf formiran od čvorova i rubova koji su podskupovi drugog grafa.