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

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…

Egy lépésre vagy attól, hogy a matek melléd álljon és ne eléd.
  • Zseniális bármilyen matek ismeret elsajátításához.

    Ákos, 19
  • Felsőbb éves egyetemisták ajánlották, "kötelező" címszóval.
    Ricsi, 19
  • Értelmes, szórakoztató, minden pénzt megér.

    Tibor, 23
  • Otthonról elérhető és olcsóbb, mint egy magántanár és akkor használom, amikor akarom.

    Milán, 19
BelépekvagyRegisztrálok Back arrow Ugrás az
összeshez