Vodnik po podatkovni strukturi grafa

Vodnik po podatkovni strukturi grafa

Učinkovit programer potrebuje dobro razumevanje podatkovnih struktur in algoritmov. Tehnični razgovori bodo pogosto preizkusili vaše sposobnosti reševanja problemov in kritičnega mišljenja.





kako počistiti predpomnilnik na telefonu android

Grafi so ena izmed mnogih pomembnih podatkovnih struktur v programiranju. V večini primerov razumevanje grafov in reševanje problemov, ki temeljijo na grafih, ni enostavno.



MAKEUSEOF VIDEO DNEVA

Kaj je graf in kaj morate vedeti o njem?





Kaj je graf?

Graf je nelinearna podatkovna struktura, ki ima vozlišča (ali oglišča) z robovi, ki jih povezujejo. Vsa drevesa so podvrste grafov, vendar niso vsi grafi drevesa, graf pa je podatkovna struktura, iz katere izvirajo drevesa.

Vizualna predstavitev grafa

Čeprav lahko graditi podatkovne strukture v JavaScriptu in drugih jezikih, lahko graf implementirate na različne načine. Najbolj priljubljeni pristopi so robni seznami , sosednji seznami , in matrike sosednosti .



The Priročnik Akademije Khan za predstavljanje grafov je odličen vir za učenje o tem, kako predstaviti graf.

Obstaja veliko različnih vrst grafov. Ena pogosta razlika je med usmeril in neusmerjen grafi; ti se pogosto pojavljajo pri izzivih kodiranja in uporabi v resničnem življenju.



Vrste grafov

  1. Usmerjeni graf: Graf, v katerem imajo vsi robovi smer, imenovan tudi digraf. Usmerjeni graf
  2. Neusmerjeni graf: Neusmerjeni graf je znan tudi kot dvosmerni graf. V neusmerjenih grafih smer robov ni pomembna, prečkanje pa lahko poteka v katero koli smer.
  3. Uteženi graf: Uteženi graf je graf, katerega vozlišča in robovi imajo povezano vrednost. V večini primerov ta vrednost predstavlja stroške raziskovanja tega vozlišča ali roba.
  4. Končni graf: Graf, ki ima končno število vozlišč in robov.
  5. Neskončni graf: Graf, ki ima neskončno število vozlišč in robov.
  6. Trivialni graf: Graf, ki ima samo eno vozlišče in nima roba.
  7. Preprost graf: Če samo en rob povezuje vsak par vozlišč grafa, se imenuje preprost graf.
  8. Ničelni graf: Ničelni graf je graf, ki nima robov, ki povezujejo njegova vozlišča.
  9. Multigraf: V multigrafu ima vsaj par vozlišč več kot en rob, ki ju povezuje. V multigrafih ni samozank.
  10. Celoten graf: Popolni graf je graf, v katerem se vsako vozlišče povezuje z vsakim drugim vozliščem v grafu. Znan je tudi kot a celoten graf .
  11. Psevdo graf: Graf, ki ima poleg drugih robov grafa samozanko, se imenuje psevdograf.
  12. Običajni graf: Pravilni graf je graf, kjer imajo vsa vozlišča enake stopnje; t.j. vsako vozlišče ima enako število sosedov.
  13. Povezani graf: Povezani graf je preprosto vsak graf, v katerem se kateri koli dve vozlišči povežeta; tj. graf z vsaj eno potjo med vsakima dvema vozliščema grafa.
  14. Odklopljen graf: Nepovezan graf je neposredno nasprotje povezanega grafa. V nepovezanem grafu ni robov, ki bi povezovali vozlišča grafa, kot na primer v a nič graf.
  15. Ciklični graf: Ciklični graf je graf, ki vsebuje vsaj en cikel grafa (pot, ki se konča tam, kjer se je začela).
  16. Aciklični graf: Aciklični graf je graf brez ciklov. Lahko je usmerjen ali neusmerjen.
  17. Podgraf: Podgraf je izpeljan graf. Je graf, sestavljen iz vozlišč in robov, ki so podmnožice drugega grafa.