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é.
Č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.
A slučka v grafe je hrana, ktorá začína od uzla a končí v tom istom uzle. Preto a vlastná slučka je slučka iba nad jedným uzlom grafu, ako je vidieť na pseudo grafe.
Algoritmy prechodu grafov
Keďže ide o typ nelineárnej dátovej štruktúry, prechádzanie grafom je dosť zložité. Prechádzať grafom znamená prejsť a preskúmať každý uzol, ak existuje platná cesta cez hrany. Algoritmy prechádzania grafom sú prevažne dvoch typov.
- Breadth-First Search (BFS): Hľadanie do šírky je algoritmus prechodu grafu, ktorý navštívi uzol grafu a preskúma jeho susedov predtým, ako prejde na ktorýkoľvek z jeho podriadených uzlov. Aj keď môžete začať prechádzať grafom z ľubovoľného vybraného uzla, koreňový uzol je zvyčajne preferovaným východiskovým bodom.
- Hĺbkové prvé vyhľadávanie (DFS): Toto je druhý hlavný algoritmus prechodu grafu. Navštívi uzol grafu a preskúma jeho podriadené uzly alebo vetvy predtým, ako prejde k ďalšiemu uzlu – to znamená, že najprv prejde do hĺbky a až potom sa rozšíri.
Odporúčaným algoritmom je vyhľadávanie do šírky na čo najrýchlejšie nájdenie ciest medzi dvoma uzlami, najmä najkratšej cesty.
Hĺbkové vyhľadávanie sa väčšinou odporúča, keď chcete navštíviť každý uzol v grafe. Oba algoritmy prechodu fungujú v každom prípade dobre, ale jeden môže byť vo vybraných scenároch jednoduchší a optimalizovanejší ako druhý.
Jednoduchá ilustrácia môže pomôcť lepšie pochopiť oba algoritmy. Predstavte si štáty krajiny ako graf a skúste skontrolovať, či dva štáty, X a Y, sú prepojené. Hĺbkové pátranie môže ísť na cestu takmer po celej krajine bez toho, aby ste si to dostatočne včas uvedomili Y je vzdialené len 2 štáty X.
Výhodou vyhľadávania do šírky je, že pred prechodom k ďalšiemu uzlu zachováva čo najväčšiu blízkosť k aktuálnemu uzlu. Nájde spojenie medzi X a Y v krátkom čase bez toho, aby ste museli preskúmať celú krajinu.
Ďalší hlavný rozdiel medzi týmito dvoma algoritmami je v spôsobe, akým sú implementované v kóde. Hľadanie do šírky je iteračný algoritmus a využíva a fronte, zatiaľ čo hĺbkové vyhľadávanie sa zvyčajne implementuje ako a rekurzívny algoritmus ktorý využíva stoh.
Nižšie je niekoľko pseudokódov demonštrujúcich implementáciu oboch algoritmov.
Hľadanie na prvom mieste
bfs (Graf G, koreň GraphNode) {
nech q byť Nový Fronta// označte root ako navštívený
root.navštívené = pravda// pridať root do frontu
q.zaradiť(koreň)
zatiaľ čo (q nie je prázdny) {
nech aktuálne byť q.dequeue() // odstránenie predného prvku vo fronte
pre (susedov n prúdu v G) {
ak (n jenie zatiaľ navštívené) {
// pridať do frontu - aby ste mohli preskúmať aj jeho susedov
q.zaradiť(n)
n.navštívené = pravda
}
}
}
}
Hĺbkové prvé vyhľadávanie
dfs (Graf G, koreň GraphNode) {
// základný prípad
ak (koreň je nulový) vrátiť// označte root ako navštívený
root.navštívené = pravda
pre (susedia n koreňa v G)
ak (n jenie zatiaľ navštívené)
dfs (G, n) // rekurzívne volanie
}
Niekoľko ďalších algoritmov prechádzania grafom je odvodených od vyhľadávania do šírky a hĺbky. Najpopulárnejšie sú:
- Obojsmerné vyhľadávanie: Tento algoritmus je optimalizovaný spôsob hľadania najkratšej cesty medzi dvoma uzlami. Používa dve vyhľadávania na šírku, ktoré sa zrazia, ak existuje cesta.
- Topologické zoradenie: Toto sa používa v orientované grafy zoradiť uzly v požadovanom poradí. Topologické zoradenie nemôžete použiť na neorientované grafy alebo grafy s cyklami.
- Dijkstrov algoritmus: Toto je tiež typ BFS. Používa sa tiež na nájdenie najkratšej cesty medzi dvoma uzlami v a vážený orientovaný graf, ktoré môžu mať cykly alebo nie.
Bežné otázky na pohovore založené na grafoch
Medzi dôležité patria grafy dátové štruktúry by mal poznať každý programátor. Otázky na túto tému sa často objavujú v technických rozhovoroch a môžete sa stretnúť s niektorými klasickými problémami súvisiacimi s témou. Patria sem veci ako „mestský sudca“, „počet ostrovov“ a problémy „cestujúceho obchodníka“.
Toto je len niekoľko z mnohých populárnych problémov s rozhovormi založenými na grafe. Môžete si ich vyskúšať LeetCode, HackerRank, alebo GeeksforGeeks.
Pochopenie dátových štruktúr grafov a algoritmov
Grafy nie sú užitočné len pre technické rozhovory. Majú aj prípady použitia v reálnom svete, ako napríklad v siete, mapy, a systémy leteckých spoločností na hľadanie trás. Používajú sa aj v základnej logike počítačových systémov.
Grafy sú vynikajúce na organizáciu údajov a na pomoc pri vizualizácii zložitých problémov. Grafy by sa však mali používať iba vtedy, keď je to absolútne nevyhnutné, aby sa predišlo problémom s priestorom alebo pamäťou.