A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
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:
- 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
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 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
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
- ↑ 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
- 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
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.
A lap szövege Creative Commons Nevezd meg! – Így add tovább! 3.0 licenc alatt van; egyes esetekben más módon is felhasználható. Részletekért lásd a felhasználási feltételeket.
Analóg multiméterek túlterhelés elleni védelme
Egyenáram
Egyenáram mérése
Egyenirányítós lengőtekercses műszer
Elektromágnes (fizika)
Elektromos feszültség
Elektromos térerősség
Fáziseltolódás
Fázismutató
Fajlagos ellenállás
Feszültséggenerátor
Feszültségváltó
Forgó mágneses tér
Háromfázisú hálózat
Hőelektromosság
Hatásos ellenállás
A lap szövege Creative Commons Nevezd meg! – Így add tovább! 3.0 licenc alatt van; egyes esetekben más módon is felhasználható. Részletekért lásd a felhasználási feltételeket.