Efektivní programátor potřebuje solidní pochopení datových struktur a algoritmů. Technické pohovory často otestují vaše schopnosti řešit problémy a kritické myšlení.
Grafy jsou jednou z mnoha důležitých datových struktur v programování. Ve většině případů není snadné porozumět grafům a řešit problémy založené na grafech.
Co je to graf a co o něm potřebujete vědět?
Co je to graf?
Graf je nelineární datová struktura, která má uzly (nebo vrcholy) s hranami, které je spojují. Všechny stromy jsou podtypy grafů, ale ne všechny grafy jsou stromy a graf je datová struktura, ze které stromy pocházejí.
I když můžete vytvářet datové struktury v JavaScriptu a dalších jazycích, můžete graf implementovat různými způsoby. Nejoblíbenější přístupy jsou seznamy okrajů, seznamy sousedství, a matice sousedství.
The Průvodce Khan Academy k reprezentaci grafů je skvělým zdrojem informací o tom, jak reprezentovat graf.
Existuje mnoho různých typů grafů. Jeden společný rozdíl je mezi režírovaný a neorientovaný grafy; ty se často objevují při problémech s kódováním a použití v reálném životě.
Typy grafů
- Orientovaný graf: Graf, ve kterém mají všechny hrany směr, označovaný také jako digraf.
- Neorientovaný graf: Neorientovaný graf je také známý jako dvousměrný graf. V neorientovaných grafech nezáleží na směru hran a procházení může jít libovolným směrem.
- Vážený graf: Vážený graf je graf, jehož uzly a hrany mají přidruženou hodnotu. Ve většině případů tato hodnota představuje náklady na prozkoumání daného uzlu nebo hrany.
- Konečný graf: Graf, který má konečný počet uzlů a hran.
- Nekonečný graf: Graf, který má nekonečné množství uzlů a hran.
- Triviální graf: Graf, který má pouze jeden uzel a žádnou hranu.
- Jednoduchý graf: Když každý pár uzlů grafu spojuje pouze jedna hrana, nazývá se to jednoduchý graf.
- Nulový graf: Nulový graf je graf, který nemá žádné hrany spojující jeho uzly.
- Multigraf: V multigrafu má alespoň pár uzlů více než jednu hranu, která je spojuje. V multigrafech nejsou žádné vlastní smyčky.
- Kompletní graf: Úplný graf je graf, ve kterém je každý uzel připojen ke každému jinému uzlu v grafu. Je také známý jako a plný graf.
- Pseudo graf: Graf, který má vlastní smyčku stranou od ostatních hran grafu, se nazývá pseudo graf.
- Běžný graf: Regulární graf je graf, kde všechny uzly mají stejné stupně; tj. každý uzel má stejný počet sousedů.
- Připojený graf: Souvislý graf je jednoduše jakýkoli graf, ve kterém se spojují libovolné dva uzly; tj. graf s alespoň jednou cestou mezi každými dvěma uzly grafu.
- Odpojený graf: Nesouvislý graf je přímým opakem souvislého grafu. V odpojeném grafu nejsou žádné hrany spojující uzly grafu, jako například v a nula graf.
- Cyklický graf: Cyklický graf je graf obsahující alespoň jeden cyklus grafu (cesta, která končí tam, kde začala).
- Acyklický graf: Acyklický graf je graf bez cyklů. Může být řízená nebo neorientovaná.
- Podgraf: Podgraf je odvozený graf. Je to graf vytvořený z uzlů a hran, které jsou podmnožinami jiného grafu.
A smyčka v grafu je hrana, která začíná v uzlu a končí ve stejném uzlu. Proto a vlastní smyčka je smyčka pouze přes jeden uzel grafu, jak je vidět na pseudo grafu.
Algoritmy procházení grafů
Vzhledem k tomu, že jde o typ nelineární datové struktury, je procházení grafu poměrně složité. Procházení grafu znamená procházení a prozkoumávání každého uzlu, pokud existuje platná cesta přes hrany. Algoritmy procházení grafů jsou převážně dvou typů.
- Vyhledávání na prvním místě (BFS): Prohledávání do šířky je algoritmus procházení grafu, který navštíví uzel grafu a prozkoumá jeho sousedy, než přejde k některému z jeho podřízených uzlů. Přestože můžete začít procházet grafem z libovolného vybraného uzlu, kořenový uzel je obvykle preferovaným výchozím bodem.
- Hloubkové vyhledávání (DFS): Toto je druhý hlavní algoritmus procházení grafu. Navštíví uzel grafu a prozkoumá jeho podřízené uzly nebo větve, než postoupí k dalšímu uzlu – to znamená, že nejprve půjde hluboko, než se rozšíří.
Prohledávání do šířky je doporučeným algoritmem pro co nejrychlejší nalezení cest mezi dvěma uzly, zejména nejkratší cesty.
Hloubkové vyhledávání se většinou doporučuje, když chcete navštívit každý uzel v grafu. Oba algoritmy procházení fungují v každém případě dobře, ale jeden může být ve vybraných scénářích jednodušší a optimalizovanější než druhý.
Jednoduchá ilustrace může pomoci lépe porozumět oběma algoritmům. Představte si státy jedné země jako graf a zkuste zkontrolovat, zda dva státy, X a Y, jsou propojené. Pátrání do hloubky by se mohlo vydat na cestu téměř po celé zemi, aniž by si to dostatečně brzy uvědomili Y je jen 2 státy od něj X.
Výhodou prohledávání do šířky je, že udržuje co největší blízkost k aktuálnímu uzlu, než přejde k dalšímu uzlu. Najde spojení mezi X a Y v krátkém čase, aniž byste museli prozkoumat celou zemi.
Další hlavní rozdíl mezi těmito dvěma algoritmy je ve způsobu, jakým jsou implementovány v kódu. Hledání do šířky je iterační algoritmus a využívá a fronta, zatímco hloubkové vyhledávání je obvykle implementováno jako a rekurzivní algoritmus který využívá zásobník.
Níže je několik pseudokódů demonstrujících implementaci obou algoritmů.
Hledání na prvním místě
bfs (Graph G, GraphNode root) {
nechat q být Nový Fronta// označit root jako navštívený
root.navštívené = skutečný// přidat root do fronty
q.zařadit do fronty(vykořenit)
zatímco (q není prázdný) {
nechat aktuální být q.dequeue() // odstranění předního prvku ve frontě
pro (sousedů n proudu v G) {
-li (n jene dosud navštíveno) {
// přidat do fronty - takže můžete prozkoumat i jeho sousedy
q.zařadit do fronty(n)
n.navštívil = skutečný
}
}
}
}
Hloubka-první hledání
dfs (Graph G, GraphNode root) {
// základní případ
-li (kořen je nula) vrátit se// označit root jako navštívený
root.navštívené = skutečný
pro (sousedy n odmocniny v G)
-li (n jene dosud navštíveno)
dfs (G, n) // rekurzivní volání
}
Několik dalších algoritmů pro procházení grafů vychází z prohledávání do šířky a do hloubky. Nejoblíbenější jsou:
- Obousměrné vyhledávání: Tento algoritmus je optimalizovaným způsobem nalezení nejkratší cesty mezi dvěma uzly. Používá dvě prohledávání šířky, která se srazí, pokud existuje cesta.
- Topologické řazení: Toto se používá v orientované grafy seřadit uzly v požadovaném pořadí. Topologické řazení nelze použít na neorientované grafy nebo grafy s cykly.
- Dijkstrův algoritmus: Toto je také typ BFS. Používá se také k nalezení nejkratší cesty mezi dvěma uzly v a vážený orientovaný graf, které mohou mít cykly nebo ne.
Běžné otázky k rozhovoru založené na grafech
Mezi důležité patří grafy datové struktury by měl znát každý programátor. Otázky na toto téma často přicházejí v technických rozhovorech a můžete se setkat s některými klasickými problémy souvisejícími s tématem. Patří mezi ně problémy jako „městský soudce“, „počet ostrovů“ a „cestující prodejce“.
To jsou jen některé z mnoha oblíbených problémů s rozhovory založenými na grafech. Můžete si je vyzkoušet LeetCode, HackerRanknebo GeeksforGeeks.
Pochopení datových struktur a algoritmů grafů
Grafy nejsou užitečné jen pro technické rozhovory. Mají také případy použití v reálném světě, například v sítě, mapy, a letecké systémy pro hledání cest. Používají se také v základní logice počítačových systémů.
Grafy jsou vynikající pro organizaci dat a pomáhají nám vizualizovat složité problémy. Grafy by se však měly používat pouze tehdy, je-li to nezbytně nutné, aby se předešlo problémům s prostorem nebo pamětí.