Schmieder László: Gráfalgoritmusok 2.

Az előző részben két csúcs között kerestünk útvonalat egy gráfban. Az ott megismert szélességi keresés a start csúcstól a cél csúcsig megtalál egy legrövidebb útvonalat, ha van út a két csúcs között. Amennyiben a keresés során nem adunk meg cél csúcsot, akkor a start csúcsból elérhető összes csúcsra kapunk egy legrövidebb útvonalat, vagyis bejárja a start csúcsból elérhető részgráfot. Az útvonal úgy áll elő, hogy a keresés során mindegyik érintett csúcshoz följegyezzük, hogy melyik szomszédjától értünk el hozzá.

A szélességi keresés/bejárás természetesen csak az egyik lehetséges módja a start csúcstól egy másikhoz vezető út megtalálásának, vagy a start csúcsból elérhető csúcsokhoz vezető utak fölírásának. Amikor ki akarunk találni egy labirintusból, akkor a gyakorlatban inkább a \emph{mélységi keresés} algoritmusát követjük. Elindulunk a (valamilyen sorrend szerinti) első járaton, majd megérkezünk a járat végéhez. Ha ez a kijárat (a gráfban a cél), akkor a keresésnek vége, ha nem, akkor két eset lehetséges: vagy nem tudunk tovább menni, innen nem nyílnak további járatok, vagy ez egy elágazás, ahonnan nyílnak más, még nem bejárt részek. Ha zsákutcában vagyunk vagy az adott elágazás minden járatát már bejártuk, akkor visszamegyünk ahhoz az elágazáshoz, ahonnan ide érkeztünk, és ott a (sorrend szerinti) következő járaton folytatjuk a keresést. Ha elágazáshoz értünk, akkor az előbb leírt stratégiát ismételjük meg, a következő, még el nem ért szomszéd felé indulunk el.

Az előbbi példában labirintusra megfogalmazott eljárás gráfokra is működik, ha az elágazásoknak megfeleltetjük a csúcsokat és a járatoknak az éleket. Bár egy labirintus megfelelője egy irányítatlan gráf, a mélységi bejárás az irányított gráfokat is a fent leírt módon bejárja, ha az éleken az irányítottságnak megfelelően haladunk előre. Visszalépéskor az irányítottsággal ellentétes irányban is haladhatunk. Ez a~mozgás nem lesz a megtalált útvonal része, ahogy a szélességi keresésnél is egyik csúcsból egy nem szomszédos csúcsba léptünk az algoritmus végrehajtása közben.

Készítsük el ezek alapján a mélységi bejárás algoritmusát, vagyis keressünk egy kiinduló csúcsból az onnan elérhető csúcsokhoz utakat. Vegyük észre, hogy minden csúcsban ugyanazt a műveletsort kell végrehajtanunk, vagyis bejárnunk a még meg nem látogatott szomszédjai által elérhető részét a gráfnak. Ez az algoritmus nagyon egyszerűen megfogalmazható rekurzívan. Bejárás közben nem szeretnénk egy csúcsot kétszer megvizsgálni, ezért a szélességi kereséshez hasonlóan most is megjelöljük a már meglátogatott csúcsokat egy jártunk tömbben. Az útvonalak tárolásához most is fölveszünk egy honnan táblázatot, amelyből a mélységi bejárás után az összes kiinduló csúcsból elérhető út kiolvasható.

A folytatás a lapban olvasható.