Gráfok szélességi keresése (BFS) | mateking
 

Diszkrét matematika epizód tartalma:

Mi az a szélességi keresés? Hogyan kell szélességi keresést csinálni egy gráfban? A szélességi keresés (breadth-first search, röviden BFS) egy olyan bejárási algoritmus, amely igyekszik először egy adott csúcshoz legközelebbi csúcsokat átvizsgálni, és csak azután folytatja a keresést a mélyebb csúcsokon.

A képsor tartalma

Van itt ez a gráf.

És szeretnénk föltérképezni egy adott pontjából kiindulva.

Az egyik módszer a gráf földerítésére a szélességi keresés.

A BFS algoritmus működése nagyon egyszerű.

Elindulunk egy adott pontból, és megkeressük az összes szomszédos pontot.

Ezek az 1 egység távolságra lévő szomszédok és mindegyikre ragasztunk egy 1-es címkét.

Most ezeknek keressük meg az 1 egység távoli szomszédjait.

De csak azokat, akiken még nincsen címke.

Ők a kiinduló ponttól 2 egység távolságra vannak és 2-es címkét kapnak.

Ha valamelyik 2-es szomszédba több él is vezet, akkor csak az egyiket hagyjuk meg.

Mindegy melyiket.

Itt jönnek aztán a kiindulóponttól 3 egység távolságra lévő pontok.

És persze itt is elég egy él.

Az algoritmus folytatódik. Most a 3-as címkéjű pontoknak keressük meg a szomszédjait.

És szép lassan végzünk.

A BFS algoritmus úgy működik, mint egy hullám, ami a gráf élein szétterjed.

Olyan, mint egy különleges alakulat, aminek a tagjai lépésről-lépésre átfésülik a gráfot.

Nyomozni persze nem csak a különleges alakulatok tudnak…

hanem a magányos detektívek is.

Akik idejüket nem kímélve egyedül bejárják a gráf minden zegzugát.

Ez egy egészen más mentalitást igényel, amit mélységi keresésnek nevezünk.

Egy lépésre vagy attól, hogy a matek melléd álljon és ne eléd.
  • Nagyon jó árba van, valamint jobb és érthetőbb, mint sok külön matek tanár.

    Márk, 22
  • Olyan weboldal, ami még egy vak lovat is megtanítana integrálni.

    Petra, 26
  • Értelmes, szórakoztató, minden pénzt megér.

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

    Míra, 21
BelépekvagyRegisztrálok Back arrow Ugrás az
összeshez