Gráfbejárás

A számítástechnikában a gráfbejárás (más néven gráfkeresés) arra utal, hogy a gráf valamennyi csúcsát bejárja (ellenőrzi és/vagy frissíti) az algoritmus. Az ilyen bejárásoknál fontos a csúcsok bejárásának sorrendje. A fabejárás a gráf bejárásának egy különleges esete.

Redundancia

A fabejárással ellentétben a gráfbejárásnál a csúcsokat egynél többször is bejárhatjuk, mert előre nem tudható, hogy azokat csúcsokat már korábban bejárták-e. Ahogy a gráfok sűrűbbé válnak, nő a megoldáshoz szükséges idő; a gráfok egyszerűsödésénél ennek az ellenkezője igaz. Nem szabad megfeledkezni arról, hogy mely csúcsokat járta már be korábban az algoritmus, hogy a lehető legkevesebb alkalommal kerüljön sor vizsgálatra (illetve, hogy megakadályozzuk a folyamat végtelen futását). Ez úgy valósítható meg, hogy a gráf csúcsait „szín” vagy „megtekintett” állapothoz kapcsoljuk a bejárás során, amit ellenőrizni és frissíteni kell, ha az algoritmus eljut egy-egy csúcshoz. Ha egy csúcsnál már járt az algoritmus, akkor azt figyelmen kívül hagyja, és lezárja azt az útvonalat, ellenkező esetben az algoritmus ellenőrzi/frissíti a csúcsot és folytatja az utat tovább.

A gráfok számos speciális esete magában foglalja a szerkezetükben lévő más-más csúcsok bejárását, így nem szükséges rögzíteni az áthaladás tényét. Jó példa erre a fa: az áthaladás során feltételezhető, hogy az aktuális csúcs minden összes „elődjét” (és az algoritmustól függően mást is) bejártak már korábban. Mind a mélységi, mind a szélességi gráfkeresés faalapú algoritmusok adaptációja, amelyet elsősorban a szerkezetileg meghatározott „gyökér” csúcs hiánya és egy olyan adatszerkezet hozzáadása jellemez, mely tartalmazza a csúcsok állapotát a bejárás tekintetében.

Gráfbejáró algoritmusok

Ha egy gráf minden csúcsát faalgoritmus segítségével kell bejárni (például DFS vagy BFS), akkor az algoritmust legalább egyszer meg kell hívni a gráf minden komponensén. Ez könnyen megvalósítható, ha a gráf minden egyes csúcsán iterációt végzünk, és minden egyes olyan csúcson elvégezzük az algoritmust, amelyet még nem jártunk be.

Mélységi keresés

A mélységi keresés (DFS) egy algoritmus, mely véges gráfot jár be. A DFS bejárja az élek mentén a csúcsokat, mielőtt elindul a szomszédos csúcsokhoz, vagyis áthalad minden út mélységén, mielőtt feltárná annak szélességét. Az algoritmus megvalósításához általában egy verem (gyakran a program hívási verme rekurzió révén) használható.

Az algoritmus egy kiválasztott „gyökér” csúcstól indul; ezután iteratívan áttér az aktuális csúcsról egy olyanra, ahol korábban még nem járt, addig amíg már nem talál bejáratlan csúcsot az aktuális él mentén. Az algoritmus ezután visszalépked a korábban bejárt csúcsok mentén, amíg meg nem talál egy csúcsot, amely még nem bejárt területhez kapcsolódik. Ezután folytatja a bejárást az új útvonalon, a korábbihoz hasonlóan visszalép, ha zsákutcába ér, és ez a folyamat csak akkor fejeződik be, ha az algoritmus már az első lépésnél vissza kell, hogy lépjen a „gyökér” csúcsra.

A DFS sok gráfokhoz kapcsolódó algoritmus alapja, ideértve a topologikus sorrendet és a síkgráfteszteket.

Pszeudokód

Bemenet: Adott egy G gráf, és a G egy v csúcsa.
Kimenet: a v-hez csatlakoztatott élek felfedezett és hátsó élként vannak feltüntetve

eljaras DFS ( G, v ) is
   v-t bejartnak jelöli
   for all el e in G.incidentEdges (V) do
      if e el bejaratlan, then
         w ← G .adjacentVertex ( v, e )
         if w csucsot nem jartak be then
           jelölje meg az e- t bejart elkent
           rekurzivan hivja a DFS-t ( G, w )
       else
           jelölje meg az e-t hatso elkent

Szélességi keresés

A szélességi keresés (BFS) egy másik módszer a véges gráfok bejárására. A BFS először a szomszédos csúcsokat járja be, mielőtt áttérne az élek menti csúcsokra, és a keresési folyamatban sor kerül felhasználásra. Ezt az algoritmust gyakran használják arra, hogy megtalálják a legrövidebb útvonalat az egyik csúcstól a másikig.

Pszeudokód

Bemenet: Adott egy G gráf, és a G egy v csúcsa.
Kimenet: A v-hez legközelebb eső csúcs, ami bizonyos feltételeknek felel meg, vagy nulla, ha nem létezik ilyen csúcs.

 eljaras BFS (G, v) is
     hozzon letre egy Q sort
     vigyük v csucsot Q-ra
     jelöljük v-t 
     while Q nem üres do
        w ← Q .dequeue ()
        if w az amit keresünk then
              return w
        for all el e in G.adjacentEdges(w)do
             x ← G.adjacentVertex ( w, e )
             if x nincs megjelölve then
                x 
                vigyük x-t a Q-ra
      return null

Alkalmazások

A szélességi keresés számos probléma megoldására használható a gráfelméletben, például:

az összes csúcs megkeresése egy összefüggő komponensen belül;
Cheney algoritmusa;
két csúcs közötti legrövidebb út megkeresése;
egy gráf tesztelése a kétoldalúság szempontjából;
Cuthill–McKee-algoritmus hálószámozása;
Ford–Fulkerson-algoritmus a maximális folyam kiszámításához egy áramlási hálózatban;
egy bináris fa sorosítása/érdemessé tétele vs. sorba rendezés rendezett sorrendben (lehetővé teszi a fa hatékony rekonstruálását);
labirintus generációs algoritmusok;
áradás kitöltése algoritmus kétdimenziós kép vagy n-dimenziós tömb szomszédos területeinek megjelölésére;
hálózatok és kapcsolatok elemzése.

Gráf feltárása

A gráf feltárása a gráfbejárás egyik változatának tekinthető. Ez egy online probléma, ami azt jelenti, hogy a gráfra vonatkozó információk csak az algoritmus futási ideje alatt kerülnek feltárásra. Az általános modell a következő: adott G = (V,E) összekapcsolt gráf nem negatív élsúlyokkal. Az algoritmus valamelyik csúcsról indul, és ismeri az összes bemenő kimenő élt, és az ezen élek végén lévő csúcsokat - de nem többet. Ha egy új csúcsot keresünk fel, akkor ismerjük az összes kimenő élt és azok végén lévő csúcsokat. A cél az összes n csúcs bejárása és a visszatérés a kiindulási csúcshoz, de az útvonalak összegének a lehető legkisebbnek kell lennie. A problémát úgy is érthetjük, mint az utazó ügynök problémáját, ahol az ügynöknek útközben fel kell fedeznie a grafikont.

Az általános gráfok esetében a legismertebb algoritmusok az irányítatlan és irányított gráfok egyszerű mohó algoritmusa:

Irányítatlan esetben a mohó bejárás legfeljebb O(ln n) -szer hosszabb, mint az optimális bejárás.^[1] A determinisztikus online algoritmusok ismert legjobb alsó határa 2.5 − ε;^[2]
Irányított esetben a mohó bejárás legfeljebb (n − 1)-szer hosszabb, mint az optimális bejárás. Ez megegyezik az n − 1 alsó határértékével.^[3] Hasonló versenyképes alsó korlát Ω (n) ha véletlenszerű algoritmusokra is vonatkozik, amelyek megismerik az egyes csomópontok koordinátáit egy geometriai beágyazódásban.Ha az összes csomópont bejárása helyett csak egyetlen „kincs” csomópontot kell megtalálni, a korlátozások az irányított gráfon vannak Θ (n ²⁾, mind determinisztikus és véletlenszerű algoritmusok esetében is.

Univerzális bejárási szekvenciák

Az univerzális keresztirányú szekvencia olyan utasítások sorozata, amely tartalmaz egy gráf túllépést bármely szabályos gráfra, meghatározott számú csúcsra és csak a kezdő csúcsra. Egy valószínűségi bizonyítékot használták fel az Aleliunas munkatársai annak bemutatásra, hogy létezik egyetemes bejárási sorrend, amiben az utasítások száma arányos az O(n⁵) bármely n csúcsú normál gráfra.^[4] A sorozatban megadott lépések az aktuális csomópontra vonatkoznak, nem az összesre. Például, ha az aktuális csomópont v _j, és v _j d szomszédok, akkor a bejárási sorrend meghatározza a következő bejárandó csomópontot, v _{j +1,} mint az ^i-edik szomszédja v _j, ahol 1 ≤ i ≤ d.

Irodalom

↑ Rosenkrantz (1977). „An Analysis of Several Heuristics for the Traveling Salesman Problem”. SIAM Journal on Computing 6 (3), 563–581. o. DOI:10.1137/0206041.
↑ Dobrev (2012. november 4.). „Online Graph Exploration with Advice”. Proc. Of the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO) 7355, 267–278. o. DOI:10.1007/978-3-642-31104-8_23.
↑ Foerster (2016. december 1.). „Lower and upper competitive bounds for online directed graph exploration”. Theoretical Computer Science 655, 15–29. o. DOI:10.1016/j.tcs.2015.11.017.
↑ Aleliunas (1979. november 4.). „Random walks, universal traversal sequences, and the complexity of maze problems”. 20th Annual Symposium on Foundations of Computer Science (SFCS 1979), 218–223. o. DOI:10.1109/SFCS.1979.34.

Fordítás

Ez a szócikk részben vagy egészben a Graph traversal című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

[1] Rosenkrantz (1977). „An Analysis of Several Heuristics for the Traveling Salesman Problem”. SIAM Journal on Computing 6 (3), 563–581. o. DOI:10.1137/0206041.

[2] Dobrev (2012. november 4.). „Online Graph Exploration with Advice”. Proc. Of the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO) 7355, 267–278. o. DOI:10.1007/978-3-642-31104-8_23.

[3] Foerster (2016. december 1.). „Lower and upper competitive bounds for online directed graph exploration”. Theoretical Computer Science 655, 15–29. o. DOI:10.1016/j.tcs.2015.11.017.

[4] Aleliunas (1979. november 4.). „Random walks, universal traversal sequences, and the complexity of maze problems”. 20th Annual Symposium on Foundations of Computer Science (SFCS 1979), 218–223. o. DOI:10.1109/SFCS.1979.34.

[1]

[2]

[3]

[4]