Barion Pixel BFS fa és DFS fa | mateking
 

Számítástudomány epizód tartalma:

Megnézzük, mi az a BFS fa és DFS fa, hogyan kell legyártani. Rekonstruálunk egy gráfot a BFS fái alapján. Szélességi keresés, mélységi keresés, gráfalgoritmusok.

A képsor tartalma
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: Adjuk meg az eredeti gráfot. Lássuk, hogyan tudnánk hasznosítani a BFS fákat. Készítünk egy ilyen kis szomszédsági táblázatot. Aztán pedig kezdjük is az első BFS fával. Eddig jó. Vannak még kétségek, de ezeket reméljük a másik BFS fa hamarosan eloszlatja. Az, hogy a C és D csúcsok között vezet él, immár biztosabb, mint a halál. Hát, ez kész. Már csak föl kell rajzolnunk. Csodás. Egy gráfban minden csúcs fokszáma páros, és két különböző kezdőpont alapján készített BFS fája: Hát, úgy tűnik eddig jutottunk. Nem baj, azért kezdjünk el rajzolgatni. Ezek itt a kérdőjeles élek. Viszont tudjuk még, hogy a gráf minden csúcsának a fokszáma páros. Ha mindkét élt elhagyjuk, az nem jó, mert akkor lesz páratlan fokszámú csúcs. És, ha mindkét élt behúzzuk, az se jó, mert akkor keletkezik harmadfokú csúcs. Ha csak az egyik élt húzzuk be… akkor így lesz egy elsőfokú csúcs. Így viszont minden csúcs páros fokszámú.
Egy lépésre vagy attól, hogy a matek melléd álljon és ne eléd.
  • 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
  • Sokkal jobb, mint bármelyik egyetemi előadásom.

    Dani, 20
  • Zseniális bármilyen matek ismeret elsajátításához.

    Ákos, 19
  • 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
BelépekvagyRegisztrálok Back arrow Ugrás az
összeshez