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 szerkesztés
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 szerkesztés
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:
- verem helyett FIFO sort használ, és
- 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 szerkesztés
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 szerkesztés
Idő- és térkomplexitás szerkesztés
Ha a csúcsok száma és a grafikon éleinek száma, az időkomplexitás , mivel a legrosszabb esetben minden csúcsot és élet bejárunk. Vegyük figyelembe, hogy a bemeneti grafikontól függően és 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 , ahol 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(bd + 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 szerkesztés
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 szerkesztés
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 szerkesztés
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 szerkesztés
- ↑ a b Cormen Thomas H.. 22.3, Introduction to Algorithms. MIT Press (2009. április 25.)
- ↑ Introduction to Algorithms, 2nd edition, 22.2 Breadth-first search, 531–539. oldal
- ↑ Aziz, Adnan. 4. Algorithms on Graphs, Algorithms for Interviews, 144. o. (2010. április 25.). ISBN 978-1453792995
Források szerkesztés
- 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 szerkesztés
Fordítás szerkeszté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.