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.

 

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

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

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. 

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