Gráfok mélységi keresése (DFS) | mateking
 

Diszkrét matematika 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 képsor tartalma

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:

Egy lépésre vagy attól, hogy a matek melléd álljon és ne eléd.
  • Konkrétan a hetedikes öcsém megtanult deriválni, ez elég bizonyíték, hogy az oldal érthetően magyaráz.

    Gábor, 18
  • Jó árban van és hihetetlenül világos a magyarázat és annyiszor lehet visszatérni az egyes lépésekre, ahányszor arra csak szükség van a megértéshez.

    Lili, 22
  • Nagyon jó árba van, valamint jobb és érthetőbb, mint sok külön matek tanár.

    Márk, 22
  • Felsőbb éves egyetemisták ajánlották, "kötelező" címszóval.
    Ricsi, 19
BelépekvagyRegisztrálok Back arrow Ugrás az
összeshez