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:
- Egy csúcs szomszédainak ábrázolása. (Szomszédsági lista vagy mátrix.)
- 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
