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ásElindulunk 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égeEljárás végeAz 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:
Távolságok feltüntetése Mélységi bejárásElindulunk 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égeEljárás végeIrányított gráfban, kezdési és befejezési időkkel
|
Programozás > Gráfalgoritmusok >
