Traverz grafu - Graph traversal

v počítačová věda, přechod grafu (také známý jako vyhledávání grafů) odkazuje na proces návštěvy (kontroly a / nebo aktualizace) každého vrcholu v a graf. Tyto přechody jsou klasifikovány podle pořadí, ve kterém jsou vrcholy navštíveny. Traverz stromu je speciální případ křížení grafu.

Nadbytek

Na rozdíl od procházení stromu může procházení grafů vyžadovat, aby byly některé vrcholy navštíveny více než jednou, protože před přechodem na vrchol není nutně známo, že již byl prozkoumán. Jak se grafy stávají více hustý, tato redundance se stává častější, což vede ke zvýšení doby výpočtu; s tím, jak se grafy stávají řídšími, platí opak.

Obvykle je tedy nutné si pamatovat, které vrcholy již algoritmus prozkoumal, aby se vrcholy navštěvovaly co nejméně často (nebo v nejhorším případě, aby se zabránilo tomu, aby traverz pokračoval donekonečna). Toho lze dosáhnout přidružením každého vrcholu grafu ke stavu „barvy“ nebo „návštěvy“ během procházení, který se poté kontroluje a aktualizuje, když algoritmus navštíví každý vrchol. Pokud byl vrchol již navštíven, je ignorován a cesta není dále sledována; jinak algoritmus zkontroluje / aktualizuje vrchol a pokračuje dolů po své aktuální cestě.

Několik zvláštních případů grafů implikuje vizitaci jiných vrcholů v jejich struktuře, a proto nevyžadují, aby byla vizitace explicitně zaznamenána během procházení. Důležitým příkladem je strom: během procházení lze předpokládat, že všechny vrcholy „předků“ aktuálního vrcholu (a další v závislosti na algoritmu) již byly navštíveny. Oba nejdříve do hloubky a prohledávání šíře prvního grafu jsou adaptace stromových algoritmů, které se vyznačují primárně nedostatkem strukturně určeného „kořenového“ vrcholu a přidáním datové struktury pro záznam stavu návštěvy procházení.

Algoritmy pro procházení grafů

Poznámka. - Pokud má každý vrchol v grafu procházet algoritmem založeným na stromech (například DFS nebo BFS), musí být algoritmus vyvolán alespoň jednou pro každý připojená součást grafu. Toho lze snadno dosáhnout iterací všemi vrcholy grafu a provedením algoritmu na každém vrcholu, který je při zkoumání stále neviditelný.

Neverbální popis tří algoritmů pro procházení grafů: náhodně, hloubkově prohledávané a prošlé šířkou.

Hledání do hloubky

Hledání do hloubky (DFS) je algoritmus pro procházení konečným grafem. DFS navštíví podřízené vrcholy před návštěvou sourozeneckých vrcholů; to znamená, že prozkoumá hloubku jakékoli konkrétní cesty, než prozkoumá její šířku. Zásobník (často program zásobník volání přes rekurze ) se obvykle používá při implementaci algoritmu.

Algoritmus začíná zvoleným „kořenovým“ vrcholem; pak iterativně přechází z aktuálního vrcholu na sousední, nenavštívený vrchol, dokud již nemůže najít neprozkoumaný vrchol, ze kterého by mohl přejít ze svého aktuálního umístění. Algoritmus pak doprovodné stopy podél dříve navštívených vrcholů, dokud nenajde vrchol spojený s ještě nezmapovaným územím. Poté bude postupovat po nové cestě tak, jak to bylo dříve, při zpětném sledování, když narazí na slepé uličky, a končí pouze v případě, že algoritmus od prvního kroku vrátil zpět původní „kořenový“ vrchol.

DFS je základem mnoha algoritmů souvisejících s grafy, včetně topologické druhy a testování rovinnosti.

Pseudo kód

Vstup: Graf G a vrchol proti z G.
Výstup: Označení hran v připojené součásti proti jako objevovací hrany a zadní hrany.

postup DFS (G, proti) je    označení proti jak prozkoumány pro všechny hrany E v G.incidentEdges (proti) dělat        -li okraj E je neprozkoumaná pak            w ← G.adjacentVertex (proti, E)            -li vrchol w je neprozkoumaná pak                označení E jako objevená hrana rekurzivně volá DFS (G, w)            jiný               označení E jako zadní hrana

Šířka první vyhledávání

Šířka první vyhledávání (BFS) je další technika pro procházení konečným grafem. BFS navštíví vrcholy sourozenců před návštěvou podřízených vrcholů, a fronta se používá v procesu hledání. Tento algoritmus se často používá k nalezení nejkratší cesty z jednoho vrcholu do druhého.

Pseudo kód

Vstup: Graf G a vrchol proti z G.
Výstup: Nejbližší vrchol proti splňující určité podmínky, nebo null, pokud žádný takový vrchol neexistuje.

postup BFS (G, proti) je    vytvořit frontu Q    zařadit do fronty proti na Q    označit proti    zatímco Q není prázdný dělat        w ← Q.dequeue () -li w je to, co hledáme pak            vrátit se w        pro všechny hrany E v G.adjacentEdges (w) dělat            X ← G.adjacentVertex (w, E)            -li X není označen pak                označit X                zařadit do fronty X na Q    vrátit se nula

Aplikace

Vyhledávání na šířku lze použít k řešení mnoha problémů v teorii grafů, například:

nalezení všech vrcholů v jednom připojená součást;
Cheneyho algoritmus;
najít nejkratší cesta mezi dvěma vrcholy;
testování grafu pro bipartitita;
Algoritmus Cuthill – McKee číslování ok;
Algoritmus Ford-Fulkerson pro výpočet maximální průtok v toková síť;
serializace / deserializace binárního stromu vs serializace v seřazeném pořadí (umožňuje efektivní konstrukci stromu);
algoritmy generování bludiště;
povodňová výplň algoritmus pro značení souvislých oblastí dvourozměrného obrazu nebo n-rozměrného pole;
analýza sítí a vztahů.

Průzkum grafů

Na problém průzkumu grafů lze pohlížet jako na variantu přechodu grafu. Jde o problém online, což znamená, že informace o grafu se odhalí až za běhu algoritmu. Běžný model je následující: daný připojený graf G = (PROTI, E) s nezápornými hmotnostmi hran. Algoritmus začíná na nějakém vrcholu a zná všechny dopadající odchozí hrany a vrcholy na konci těchto hran - ale ne více. Když je navštíven nový vrchol, jsou opět známy všechny dopadající odchozí hrany a vrcholy na konci. Cílem je navštívit všechny n vrcholy a návrat na počáteční vrchol, ale součet vah prohlídky by měl být co nejmenší. Problém lze také chápat jako konkrétní verzi problém obchodního cestujícího, kde musí obchodník graf objevit i na cestách.

U obecných grafů jsou nejznámější algoritmy pro neorientované i směrované grafy jednoduché chamtivý algoritmus:

V neřízeném případě je chamtivá prohlídka maximálně Ó(ln n)-krát delší než optimální prohlídka.^[1] Nejlepší dolní mez známá pro jakýkoli deterministický online algoritmus je 2.5 − ε;^[2]
V nasměrovaném případě je chamtivá prohlídka maximálně (n − 1) -krát delší než optimální prohlídka. To odpovídá dolní hranici n − 1.^[3] Analogická konkurenční spodní hranice Ω(n) platí také pro randomizované algoritmy, které znají souřadnice každého uzlu v geometrickém vložení. Pokud místo návštěvy všech uzlů musí být nalezen pouze jeden uzel „pokladu“, jsou konkurenční hranice Θ(n²) na grafech zaměřených na jednotkovou hmotnost pro deterministické i randomizované algoritmy.

Univerzální traversální sekvence

A univerzální traverzová sekvence je posloupnost instrukcí, která obsahuje přechod grafu pro libovolnou běžný graf se stanoveným počtem vrcholů a pro libovolný počáteční vrchol. Pravděpodobnostní důkaz použili Aleliunas et al. ukázat, že existuje univerzální traverzová posloupnost s úměrným počtem instrukcí Ó(n⁵) pro každý běžný graf s n vrcholy.^[4] Kroky uvedené v sekvenci jsou relativní k aktuálnímu uzlu, nikoli absolutní. Například pokud je aktuální uzel proti_j, a proti_j má d sousedé, pak traverzová sekvence určí další uzel k návštěvě, proti_j+1jako i^th soused z proti_j, kde 1 ≤ i ≤ d.

Reference

^ Rosenkrantz, Daniel J .; Stearns, Richard E .; Lewis, II, Philip M. (1977). "Analýza několika heuristik pro problém obchodního cestujícího". SIAM Journal on Computing. 6 (3): 563–581. doi:10.1137/0206041.
^ Dobrev, Stefan; Královic, Rastislav; Markou, Euripides (2012). "Online průzkum grafů s radami". Proc. 19. mezinárodního kolokvia o strukturální informační a komunikační složitosti (SIROCCO). Přednášky z informatiky. 7355: 267–278. doi:10.1007/978-3-642-31104-8_23. ISBN 978-3-642-31103-1.
^ Foerster, Klaus-Tycho; Wattenhofer, Roger (prosinec 2016). „Dolní a horní konkurenční hranice pro online řízený průzkum grafů“. Teoretická informatika. 655: 15–29. doi:10.1016 / j.tcs.2015.11.017.
^ Aleliunas, R .; Karp, R .; Lipton, R .; Lovász, L .; Rackoff, C. (1979). "Náhodné procházky, univerzální sekvence procházení a složitost problémů s bludištěm". 20. výroční sympozium o základech informatiky (SFCS 1979): 218–223. doi:10.1109 / SFCS.1979.34.

Viz také

Procházení grafu externí paměti

[1] Rosenkrantz, Daniel J .; Stearns, Richard E .; Lewis, II, Philip M. (1977). "Analýza několika heuristik pro problém obchodního cestujícího". SIAM Journal on Computing. 6 (3): 563–581. doi:10.1137/0206041.

[2] Dobrev, Stefan; Královic, Rastislav; Markou, Euripides (2012). "Online průzkum grafů s radami". Proc. 19. mezinárodního kolokvia o strukturální informační a komunikační složitosti (SIROCCO). Přednášky z informatiky. 7355: 267–278. doi:10.1007/978-3-642-31104-8_23. ISBN 978-3-642-31103-1.

[3] Foerster, Klaus-Tycho; Wattenhofer, Roger (prosinec 2016). „Dolní a horní konkurenční hranice pro online řízený průzkum grafů“. Teoretická informatika. 655: 15–29. doi:10.1016 / j.tcs.2015.11.017.

[4] Aleliunas, R .; Karp, R .; Lipton, R .; Lovász, L .; Rackoff, C. (1979). "Náhodné procházky, univerzální sekvence procházení a složitost problémů s bludištěm". 20. výroční sympozium o základech informatiky (SFCS 1979): 218–223. doi:10.1109 / SFCS.1979.34.

[1]

[2]

[3]

[4]