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.
É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…
Diszkrét matematika epizód.