Számítástudomány epizód tartalma:
Mi az a mélységi keresés? Hogyan kell végrehajtani? A mélységi keresés (depth-first search, röviden DFS) egy olyan algoritmus, amely egy pontból kiindulva bejárja a gráfot úgy, hogy először igyekszik a legtávolabbi csúcsig, a legmélyebb szintig eljutni.
A gráfok bejárásának egyik lehetséges módját már láttuk.
Ez a BFS algoritmus, ami hullámszerűen fésüli át a gráfot.
Olyan, mint egy különleges alakulat, aminek a tagjai lépésről-lépésre teljes szélességben haladnak.
De nyomozni nem csak a különleges alakulatok tudnak, hanem a magányos detektívek is.
Ezt DFS algoritmusnak nevezzük.
A DFS algoritmus a gráf mélységi keresés.
A DFS algoritmus lényege, hogy elindulunk egy úton…
rendíthetetlenül.
És megyünk amíg csak tudunk.
Amikor elakadunk, mert már nem tudunk úgy továbbmenni, hogy olyan pontba jussunk, ahol még nem jártunk…
Akkor visszamegyünk egészen addig, ahonnan még lehet földerítetlen pontok felé haladni.
És megyünk a járatlan utakon tovább.
Amikor újra elakadunk, megint visszamegyünk.
Hopp.
Hát, ez ennyi.
Végül itt még vannak lehetőségek.
Így működik a mélységi bejárás.
A BFS és a DFS algoritmusok végrehajtása során a gráfnak egy-egy feszítőfáját kapjuk.
Ezeket rendkívül frappáns módon BFS és DFS fának nevezzük.
Mindketten az eredeti gráf feszítőfái.
Csak hát az a baj, hogy a BFS és DFS fák megalkotása során nagy szerepe van a véletlennek.
Ha például itt egy másik élt húzunk be…
akkor egy egészen más BFS fát kapunk.
Arról nem is beszélve, hogy az algoritmus elején a gráf bármelyik csúcsából indulhatunk.
Mindezen gubancok ellenére megpróbálhatjuk rekonstruálni az eredeti gráfot annak BSF és DSF fái alapján.
Íme, egy gráf két különböző kezdőpont alapján készített BFS fája: