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

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…

Egy lépésre vagy attól, hogy a matek melléd álljon és ne eléd.
  • Nem találsz külön tanárt? Ne is keress! Irány a mateking!!!!

    Bori, 19
  • Olyan weboldal, ami még egy vak lovat is megtanítana integrálni.

    Petra, 26
  • A mateking miatt sikerült az érettségi és az összes egyetemi matekos tárgyam.

    Míra, 21
  • Zseniális bármilyen matek ismeret elsajátításához.

    Ákos, 19
BelépekvagyRegisztrálok Back arrow Ugrás az
összeshez