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