Szélességi bejárás

A szélességi bejárás vagy szélességi keresés (breadth-first search, BFS) egy fa vagy gráf típusú adatszerkezet bejárására vagy keresésére szolgáló algoritmus. A fa gyökerénél (vagy egy gráf tetszőleges csomópontjánál, amelyet néha „keresési kulcsnak” hívnak) kezdődik, és megvizsgálja az összes szomszédos csomópontot (csúcsot) a jelenlegi szinten, mielőtt a következő szintekre lépne.

Ellentettje a mélységi bejárás, amely legelőször a csomópont ágát járja be a gyökérig, mielőtt rátérne a keresztező elágazásokra.^[1]

A szélességi bejárást és annak alkalmazását gráfok összefüggő komponenseinek megtalálására 1945-ben jegyezte fel Konrad Zuse (elutasított) PhD-disszertációjában a Plankalkül programozási nyelvről, bár ezt 1972-ig nem tették közzé. 1959-ben Edward F. Moore újraformálta, és arra használta, hogy megtalálja egy labirintusból kivezető legrövidebb utat, majd C. Y. Lee később huzalvezetési algoritmussá fejlesztette ki (1961-ben publikálta).

Pszeudokód

Bemenet: egy G gráf, és a gráf kezdőpontja.

Kimenet: Célállapot. A szülő-kapcsolatok meghatározzák a gyökérhez vezető legrövidebb utat.^[1]

1 eljárás szélességi bejárás(G, kezdőpont) =
2   legyen Q egy sor
3   kezdőpont felcímkézése felfedezettként
4   Q.hozzáad(kezdőpont)
5   amíg Q nem üres csináld
6     v := Q.kiemel()
7     ha v a cél akkor
8       return v
9     ciklus minden él a G.szomszédosÉlek(v)-ben v és w között csináld
10      ha w nem címkézett akkor
11        w felcímkézése felfedezettként
13        Q.hozzáad(w)

További részletek

A nem-rekurzív szélességi bejárás implementációja hasonló a mélységi bejáráséhoz, de két pontban különbözik tőle:

1. verem helyett FIFO sort használ, és
2. egy csomópont hozzáadása előtt ellenőrzi, hogy fel lett-e már fedezve, ahelyett hogy a csúcs kiemeléséig késleltetné ezt az ellenőrzést

Ha G egy fa, akkor a szélességi bejárás sorát veremmé változtatva a mélységi bejárás algoritmusát kapjuk.

A Q sor tartalmazza azt a határt, amely mentén az algoritmus jelenleg keres.

A csomópontok felfedezettként való felcímkézésére több módszer van, például egy attribútumot lehet rendelni mindegyikhez, vagy egy halmazban lehet tárolni a felfedezett csomópontokat.

Az egyes csomópontok szülői (parent node) felhasználhatóak a csúcsok legrövidebb úton való eléréséhez, például egy útvonal meghatározásához a céltől a kezdő csomópontig, miután a szélességi bejárás lefutott és a megfelelő attribútumok be lettek állítva.

A szélességi bejárás úgynevezett szélességi bejárási fát hoz létre, mint ahogy az alábbi példában is látható.

Példa

Az alábbiakban egy példát láthatunk a szélességi bejárási fára, amelyet az algoritmus futtatásával nyerünk. A bevitel német városokat tartalmaz, a kezdőpont Frankfurt.

Elemzés

Idő- és térkomplexitás

Ha ${\displaystyle |V|}$ a csúcsok száma és ${\displaystyle |E|}$ a grafikon éleinek száma, az időkomplexitás ${\displaystyle O(|V|+|E|)}$, mivel a legrosszabb esetben minden csúcsot és élet bejárunk. Vegyük figyelembe, hogy ${\displaystyle O(|E|)}$ a bemeneti grafikontól függően ${\displaystyle O(1)}$ és ${\displaystyle O(|V|^{2})}$ között változhat.^[2]

Ha a gráf csúcsainak száma idő előtt ismert, és további adatszerkezeteket használunk annak meghatározására, hogy mely csúcsokat jártunk már be, akkor a térkomplexitás kifejezhető mint ${\displaystyle O(|V|)}$, ahol ${\displaystyle |V|}$ a csúcsok száma. Ez kiegészül a magának a grafikonnak a szükséges helyével, amely az algoritmusban használt grafikonábrázolástól függ.

Ha olyan grafikonokkal dolgozik, amelyek túl nagyok az explicit tároláshoz (vagy végtelenek), célszerűbb másképpen meghatározni a komplexitást: hogy megtaláljuk a kezdőponttól d távolságra lévő csúcsokat (a bejárt élek számában mérve), az algoritmus O(b^{d + 1}) időt és memóriát vesz igénybe, ahol b a grafikon „elágazási tényezője” (branching factor; a gyermekek száma minden csúcsnál).

Teljesség

Az algoritmusok elemzésében a szélességi bejárásba való bemenetet véges gráfnak tekintik, amelyet explicit szomszédsági listaként / mátrixként vagy hasonlóként ábrázolnak. A gyakorlatban azonban (például a mesterséges intelligenciában történő gráfbejárásban) a bemenet lehet egy végtelen gráf implicit ábrázolása. Ekkor a keresési módszert akkor tekintjük teljesnek, ha garantáltan megtalálja a célállapotot, ha az létezik. A szélességi bejárás teljes, de a mélységi keresés nem (az utóbbi elvesztődhet a gráf olyan részeiben, amelyeknek nincs célállapota).

Rendezettség

A gráf csúcsainak felsorolását BFS-rendezettnek tekintjük, ha ez egy lehetséges kimenete a gráfra alkalmazott BFS-algoritmusnak.

Alkalmazásai

A szélességi bejárás számos probléma megoldására használható a gráfelméletben, például:

• Szemétgyűjtés másolása, Cheney-algoritmus
• Két u és v csomópont közötti legrövidebb út megkeresése, az út hosszát az élek számával mérve (előnye a mélységi kereséshez képest)^[3]
• (Fordított) Cuthill–McKee-hálószámozás
• Ford–Fulkerson-módszer a maximális áramlás kiszámításához egy áramlási hálózatban
• Bináris fa szerializációja/deszerializációja versus szerializáció rendezett sorrendben; lehetővé teszi a fa hatékony újrakonstruálását
• Hibafüggvény építése az Aho-Corasick-mintakeresőben
• Egy páros gráf kétoldalúságának tesztelése.

Jegyzetek

Források

• Mélységi és szélességi bejárás, Kása Zoltán
• Szélességi bejárás Archiválva 2021. június 16-i dátummal a Wayback Machine-ben, Rónyai: Algoritmusok
• Szélességi bejárás, tamop412.elte.hu
• Szélességi bejárás, elte.hu
• Graph Traversal, opendatastructures.org
• Simplified Breadth-first Search, web.piyushgarg.in

Kapcsolódó szócikkek

• Lexikográfiai szélességi bejárás
• Mélységi bejárás

Fordítás

Ez a szócikk részben vagy egészben a Breadth-first search című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.