breadth-first search

breadth-first search (tsz. breadth-first searches)

1. (informatika) szélességi keresés

A szélességi keresés (Breadth-First Search – BFS) egy alapvető gráf- és faalgoritmus, amelyet gyakran alkalmazunk olyan problémák megoldására, ahol a legkevesebb számú lépés (élszám) megtalálása a cél. A BFS először a gyökércsúcsból (vagy kezdőpontból) indul, majd egyszerre „körbejárja” az összes közvetlen szomszédot, mielőtt a következő, nagyobb „távolságú” szintekre lépne. A módszer garantálja, hogy ha létezik út két csúcs között, akkor a megtalált út a legrövidebb (élhosszúságú) lesz, feltéve, hogy az élek egységnyi súlyúak.

1. Kezdeti állapot

   • Adott egy gráf ${\textstyle G=(V,E)}$, ahol ${\textstyle V}$ a csúcsok halmaza és ${\textstyle E}$ az élek halmaza.
   • Van egy kezdőcsúcs ${\textstyle s\in V}$, amelyből a keresést indítjuk.

2. Adatszerkezet

   • Egy FIFO (First-In-First-Out) sor (queue), amely a következő feldolgozandó csúcsokat tartalmazza.
   • Egy tömb vagy hashtábla, amely jelzi, hogy mely csúcsokat látogattuk már meg (színjelölés vagy boolean érték).
   • (Opcionálisan) egy szülőmutató (parent) tömb, amely a megtalált legrövidebb út visszakövetéséhez szükséges.

3. Pseudokód

   BFS(G, s):
       létrehozunk egy üres sort: Q = 
       létrehozunk egy visited tömböt, minden csúcsra false
       visited = true
       parent = null
       enqueue(Q, s)
   
       amíg Q nem üres:
           u = dequeue(Q)
           feldolgozzuk u-t (pl. kiírjuk vagy vizsgáljuk)
           minden v ∈ szomszédok(u) esetén:
               ha visited == false:
                   visited = true
                   parent = u
                   enqueue(Q, v)

4. Működés

   • Először beleteszünk a kezdőcsúcsot a sorba, megjelöljük látogatottként.
   • A sorból mindig a legrégebben berakott (legkorábbi) csúcsot vesszük ki, és megnézzük összes szomszédját.
   • A még nem látogatott szomszédokat hozzáadjuk a sor végéhez, és megjelöljük látogatottként.
   • Ezzel biztosított, hogy a szintekben haladunk: először a gyökérszintet (0. szint), majd az 1. szint csúcsait, majd a 2. szintet, és így tovább.

• Időkomplexitás: ${\textstyle O(|V|+|E|)}$.
  • Minden csúcsot pontosan egyszer teszünk be és veszünk ki a sorból (${\textstyle O(|V|)}$).
  • Minden élt legfeljebb egyszer vizsgálunk meg, amikor a végpontját látogatjuk (${\textstyle O(|E|)}$).
• Helykomplexitás: ${\textstyle O(|V|)}$.
  • A visited és parent tömbök mérete ${\textstyle O(|V|)}$.
  • A sorban legfeljebb ${\textstyle |V|}$ csúcs lehet.

from collections import deque

def bfs(graph, start):
    visited = set()
    parent = {start: None}
    queue = deque()
    visited.add(start)

    while queue:
        u = queue.popleft()
        print(f"Feldolgozva: {u}")
        for v in graph:
            if v not in visited:
                visited.add(v)
                parent = u
                queue.append(v)
    return parent

• graph lehet például egy szótár, amelyben a kulcsok a csúcsok, az értékek pedig listák a szomszédos csúcsokról.
• A parent dict segítségével bármelyik célcsúcshoz visszakövethetjük a gyökérből vezető legrövidebb utat.

Tegyük fel, hogy a következő irányítatlan gráfot reprezentálja a szótár:

graph = {
    'A': ,
    'B': ,
    'C': ,
    'D': ,
    'E': ,
    'F': 
}

• Kezdőpont: 'A'.
• A BFS bejárás sorrendje:
  1. 'A'
  2. 'B', 'C'
  3. 'D', 'E', 'F'

Így látható, hogy előbb járjuk be az A-ból közvetlenül elérhető csúcsokat, majd azok szomszédait.

• Fa esetén a BFS gyakorlatilag szintenkénti faátjárást jelent.
• Iránányított gráf esetén ugyanaz az elv, csak a bejárás során a bevitt irányt követjük.
• Súlyozott gráf esetén a BFS csak egységsúlyú élek esetén adja a legrövidebb utat; általános súlyozott gráfhoz Dijkstra-algoritmus szükséges.

1. Legrövidebb út egységsúlyú gráfokban.
2. Szintszám meghatározása: minden csúcshoz rendeljük hozzá a gyökértől való távolságot.
3. Legnagyobb komponens keresése irányítatlan gráfban.
4. Szélességi fa építése, amely a gráf összes csúcsát szintek szerint szervezi.
5. Árkiegyenlítések, játékelméleti keresések, labirintusbejárás.
6. Weboldalak feltérképezése (webcrawler), ahol az oldalak a csúcsok és a linkek az élek.

• Bidirekcionális BFS: ha a keresett célcsúcs ismert, egyszerre indítunk keresést a kezdőcsúcstól és a céltól, és akkor találkozunk, amikor a két bejárás találkozik a gráf valamelyik köztes pontján. Ez drasztikusan csökkentheti a bejárt állapotok számát nagy gráfok esetén.
• B méllyebb keresések kombinálása: például A*-algoritmusban a BFS szerű szerkezetet heuristikával kiegészítve használjuk.

A szélességi keresés az egyik legegyszerűbb és leggyakrabban használt gráfbejáró algoritmus, amely garantáltan megtalálja a legrövidebb utat egységnyi súlyú élek esetén. Lineáris idő- és helykomplexitással működik, könnyen implementálható és számos problémában – a faátjárástól kezdve egészen webcrawlerekig – alkalmazható. A soralapú feldolgozás szint-szerű szemléletet ad, amely megkülönbözteti a mélységi kereséstől, ahol a cél egy adott ágon való minél mélyebb bejárás.

Forgalmasan tanulmányozva, a BFS megértése elengedhetetlen a fejlesztők és kutatók számára, hiszen alapot nyújt bonyolultabb keresési és optimalizációs algoritmusokhoz, valamint valós alkalmazási területeken is kulcsszerepet játszik.

• breadth-first search - Szótár.net (en-hu)
• breadth-first search - Sztaki (en-hu)
• breadth-first search - Merriam–Webster
• breadth-first search - Cambridge
• breadth-first search - WordNet
• breadth-first search - Яндекс (en-ru)
• breadth-first search - Google (en-hu)
• breadth-first search - Wikidata
• breadth-first search - Wikipédia (angol)