Diszkrét matematika epizód tartalma:

Gyorsan és egyszerűen elmeséljük, hogyan működik a BFS algoritmus irányított gráfokban. Megnézzük a szélességi keresés lépéseit egy konkrét példán keresztül és elkészítjük a BFS-fát.

A képsor tartalma

És most lássuk, hogyan is működik itt a BFS algoritmus.

Az algoritms lényege, hogy kiindulunk egy csúcsból…

Aztán megkeressük a közvetlen szomszédjait.

A gráf irányított, ezért a 7-es csúcsba sajna nem vezet él az 1-esből.

Úgy tűnik, hogy két szomszédot találtunk.

Most folytatjuk a keresést, és az új csúcsoknak keressük meg a szomszédjait.

Nagyszerű dolog, hogy a 4-es csúcs mindkét korábbi csúcsnak szomszédja, de ilyenkor csak az egyik élt választjuk.

Mindegy melyiket.

És megyünk tovább…

Hát, ez meg is van.

A BFS algoritmus eredményeként kapjuk a BFS-fát.

Hogyha a BFS-fába berajzoljuk az eredeti gráf többi élét is…

Akkor ezek az élek három típusba sorolhatóak.

Ahogyan korábban a DFS-fánál már láttuk, vannak „előre-él”ek, „vissza-él”ek és „kereszt-él”ek.

Pontosabban csak „vissza-él”ek vannak…

és „kereszt-él”ek.

„Előre-él” nincs.

Ha ugyanis lenne egy „előre-él”…

mondjuk például itt…

Akkor lenne egy közvetlen él a 3-as csúcsból a 6-os csúcsba.

De akkor a 3-as csúcsnak a 6-os is közvetlen szomszédja lenne…

és így hibás lenne a BFS-fa.

Azokban az esetekben, amikor a gráf súlyozott, a BFS algoritmus nem működik.

Ilyenkor a BFS helyett egy másik algoritmus van forgalomban.

Nézzük meg ezt is…

 

BFS-algoritmus irányított gráfokban, BFS-fa

02
hang
Hopsz, úgy tűnik nem vagy belépve, pedig itt olyan érdekes dolgokat találsz, mint például:

Gyorsan és egyszerűen elmeséljük, hogyan működik a BFS algoritmus irányított gráfokban. Megnézzük a szélességi keresés lépéseit egy konkrét példán keresztül és elkészítjük a BFS-fát.

Végül is miért ne néznél meg
még egy epizódot?
Ugrás az
összeshez