Programozás‎ > ‎Gráfalgoritmusok‎ > ‎

Bejárások

Egy gráfról fontos lehet tudni, hogy összefüggő-e. Erre bejárási algoritmusokat használhatunk: akkor és csak akkor összefüggő egy gráf, ha bármelyik csúcsából indulva bejárhatjuk úgy, hogy minden csúcsba elérünk. A gyakorlatban kétféle bejárási algoritmust használunk.

Szélességi bejárás

Elindulunk egy csúcsból és összes szomszédját meglátogatjuk. A meglátogatott szomszédok egy sorba kerülnek. Amíg a sor nem üres, kivesszük az első elemét, és annak még meg nem látogatott szomszédai bekerülnek a sor végére.

Eljárás szélességi_bejárás(start)
    bejárt[] := hamis
    bejárt[start] := igaz
    sorba(start)
    Ciklus amíg nem üres_sor()
        := sorból()
        Ciklus u összes v szomszédjára
            Ha nem bejárt[v] akkor
                bejárt[v] := igaz
                sorba(v)
            Elágazás vége
        Ciklus vége
    Ciklus vége
Eljárás vége

Az algoritmus "szintenként" látogatja meg a gráf csúcsait.
Az algoritmus hatékonysága két adatábrázolási megoldástól függ leginkább:
  1. Egy csúcs szomszédainak ábrázolása. (Szomszédsági lista vagy mátrix.)
  2. A SOR adatszerkezet hatékony megvalósításától.

Távolságok feltüntetése


Mélységi bejárás

Elindulunk egy csúcsból és valamilyen sorrendben bejárjuk a szomszédait. A szomszéd bejárásához rekurzívan meghívjuk a mélységi bejárást, ez azt eredményezi, hogy addig megyünk befelé a gráfba, amíg zsákutcába nem jutunk, akkor pedig visszalépünk addig a csúcsig, ahol lehet más irányban folytatni a bejárást.

Eljárás mélységi_bejárás(u)
    bejárt[u] := igaz
    Ciklus u minden v szomszédjára
        Ha nem bejárt[v] akkor mélységi_bejárás(v)
    Ciklus vége
Eljárás vége

Irányított gráfban, kezdési és befejezési időkkel


Nagyítható 

A mélységi bejárás tulajdonságai

További olvasnivalók

Breadth First Search (szélességi keresés)
Deep First Search (mélységi keresés)