NézetNyomtat

10. óra - Szélességi és mélységi bejárás
Elmélet > Algoritmusok > Gráfalgoritmusok
Címkék > Óra

10. óra

Gráfalgoritmusok 3. rész. Összefüggőség, 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()
        u := 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.

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

Feladat