| dbo:abstract
|
- 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. 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). (hu)
- 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. 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). (hu)
|
