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 szerkesztés

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 szerkesztés

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 szerkeszté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ó.

A mélységi keresés szemléltetése

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 szerkesztés

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 szerkeszté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 szerkesztés

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 szerkesztés

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 szerkesztés

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 szerkesztés

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 szerkesztés

↑ 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. június 6.). „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. június 6.). „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 szerkeszté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. június 6.). „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. június 6.). „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]