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.
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.
