Sprievodca štruktúrou údajov grafu

Efektívny programátor potrebuje dôkladné pochopenie dátových štruktúr a algoritmov. Technické pohovory často preveria vaše schopnosti riešiť problémy a kritické myslenie.

Grafy sú jednou z mnohých dôležitých dátových štruktúr v programovaní. Vo väčšine prípadov pochopenie grafov a riešenie problémov založených na grafoch nie je jednoduché.

VYUŽITIE VIDEA DŇA

Čo je to graf a čo o ňom potrebujete vedieť?

Čo je to graf?

Graf je nelineárna dátová štruktúra, ktorá má uzly (alebo vrcholy) s hranami, ktoré ich spájajú. Všetky stromy sú podtypy grafov, ale nie všetky grafy sú stromy a graf je dátová štruktúra, z ktorej stromy pochádzajú.

Hoci môžete vytvárať dátové štruktúry v JavaScripte a iných jazykoch, môžete graf implementovať rôznymi spôsobmi. Najpopulárnejšie sú prístupy okrajové zoznamy , zoznamy susedstva , a matice susednosti .

The Khan Academy sprievodca reprezentovaním grafov je skvelým zdrojom informácií o tom, ako znázorniť graf.

Existuje mnoho rôznych typov grafov. Jeden spoločný rozdiel je medzi riadený a neriadený grafy; tieto sa často vyskytujú pri problémoch s kódovaním a používaní v reálnom živote.

Typy grafov

Orientovaný graf: Graf, v ktorom všetky hrany majú smer, označovaný aj ako digraf.
Neorientovaný graf: Neorientovaný graf je známy aj ako obojsmerný graf. V neorientovaných grafoch nezáleží na smere hrán a prechod môže ísť ktorýmkoľvek smerom.
Vážený graf: Vážený graf je graf, ktorého uzly a hrany majú priradenú hodnotu. Vo väčšine prípadov táto hodnota predstavuje náklady na preskúmanie daného uzla alebo hrany.
Konečný graf: Graf, ktorý má konečný počet uzlov a hrán.
Nekonečný graf: Graf, ktorý má nekonečné množstvo uzlov a hrán.
Triviálny graf: Graf, ktorý má len jeden uzol a žiadnu hranu.
Jednoduchý graf: Keď len jedna hrana spája každý pár uzlov grafu, nazýva sa to jednoduchý graf.
Nulový graf: Nulový graf je graf, ktorý nemá žiadne hrany spájajúce jeho uzly.
Multigraf: V multigrafe má aspoň pár uzlov viac ako jednu hranu, ktorá ich spája. V multigrafoch nie sú žiadne vlastné slučky.
Kompletný graf: Úplný graf je graf, v ktorom sa každý uzol spája s každým iným uzlom v grafe. Je tiež známy ako a úplný graf .
Pseudo graf: Graf, ktorý má vlastnú slučku okrem ostatných hrán grafu, sa nazýva pseudo graf.
Bežný graf: Pravidelný graf je graf, kde všetky uzly majú rovnaké stupne; t.j. každý uzol má rovnaký počet susedov.
Prepojený graf: Súvislý graf je jednoducho akýkoľvek graf, v ktorom sú spojené ľubovoľné dva uzly; tj graf s aspoň jednou cestou medzi každými dvoma uzlami grafu.
Odpojený graf: Nespojený graf je priamym opakom spojeného grafu. V odpojenom grafe nie sú žiadne hrany spájajúce uzly grafu, ako napríklad v a nulový graf.
Cyklický graf: Cyklický graf je graf obsahujúci aspoň jeden cyklus grafu (cesta, ktorá končí tam, kde začala).
Acyklický graf: Acyklický graf je graf bez cyklov. Môže byť riadený alebo neriadený.
Podgraf: Podgraf je odvodený graf. Je to graf vytvorený z uzlov a hrán, ktoré sú podmnožinami iného grafu.