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

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

Gráfok egy adott pontjából való feltérképezésére alkalmas módszer a szélességi keresés (BFS = Breadth-first search).

Működése:

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.

Az algoritmus aztán így folytatódik, és szép lassan végez.