Szélességi bejárás

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez
Animált példa a szélességi bejárásra

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:

  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[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.

Dél-Németország térképe a városok közötti kapcsolatokkal
A szélességi bejárási fát akkor kapjuk, amikor az algoritmus lefut az adott térképen

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:

Jegyzetek[szerkesztés]

  1. a b Cormen Thomas H.. 22.3, Introduction to Algorithms. MIT Press (2009. szeptember 30.) 
  2. Introduction to Algorithms, 2nd edition, 22.2 Breadth-first search, 531–539. oldal
  3. Aziz, Adnan. 4. Algorithms on Graphs, Algorithms for Interviews, 144. o. (2010. szeptember 30.). ISBN 978-1453792995 

Források[szerkesztés]

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 jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.