Breadth First Search (BFS) algoritmus EXAMPLE-vel
Mi az a BFS algoritmus (Breadth-First Search)?
A Breadth-first keresés (BFS) egy algoritmus, amelyet adatok ábrázolására vagy fa keresésére vagy struktúrák bejárására használnak. A BFS teljes formája a Breadth-first keresés.
Az algoritmus hatékonyan felkeresi és megjelöli a gráf összes kulcscsomópontját, pontos szélességben. Ez az algoritmus egyetlen csomópontot (kezdeti vagy forráspontot) választ ki a gráfban, majd felkeresi a kiválasztott csomóponttal szomszédos összes csomópontot. Ne feledje, a BFS egyenként éri el ezeket a csomópontokat.
Miután az algoritmus meglátogatja és megjelöli a kezdő csomópontot, akkor a legközelebbi nem látogatott csomópontok felé halad, és elemzi azokat. Miután meglátogatta, minden csomópont meg van jelölve. Ezek az iterációk addig folytatódnak, amíg a gráf összes csomópontját sikeresen meg nem látogatták és meg nem jelölték.
Mi az a gráfbejárás?
A gráf bejárása egy általánosan használt módszer a csúcspozíció meghatározására a gráfban. Ez egy fejlett keresési algoritmus, amely gyorsan és pontosan tudja elemezni a gráfot, valamint megjelölni a meglátogatott csúcsok sorrendjét. Ez a folyamat lehetővé teszi, hogy gyorsan meglátogassa a grafikon egyes csomópontjait anélkül, hogy egy végtelen hurokba lenne zárva.
A BFS algoritmus architektúrája
- Az adatok különböző szintjein bármely csomópontot megjelölhet kezdő vagy kezdeti csomópontként a bejárás megkezdéséhez. A BFS felkeresi a csomópontot, megjelöli látogatottként, és behelyezi a sorba.
- Most a BFS felkeresi a legközelebbi és még nem látogatott csomópontokat, és megjelöli azokat. Ezek az értékek szintén hozzáadódnak a sorhoz. A sor a FIFO modell.
- Hasonló módon a gráf többi legközelebbi és meg nem látogatott csomópontjait megjelölve elemzi és hozzáadja a sorhoz. Ezeket az elemeket a rendszer vételkor törli a sorból, és eredményként kinyomtatja.
Miért van szükségünk BFS algoritmusra?
Számos oka van annak, hogy a BFS-algoritmust használja az adatkészlet megkeresésére. A legfontosabb szempontok közül néhány, amelyek miatt ez az algoritmus az Ön első választása:
- A BFS hasznos a gráf csomópontjainak elemzéséhez, és a legrövidebb áthaladási útvonal megalkotásához.
- A BFS a legkevesebb iterációval képes áthaladni egy gráfon.
- A BFS-algoritmus felépítése egyszerű és robusztus.
- A BFS algoritmus eredménye más algoritmusokhoz képest magas szintű pontossággal rendelkezik.
- A BFS-iterációk zökkenőmentesek, és nincs lehetőség arra, hogy ez az algoritmus beleragadjon egy végtelen hurok problémájába.
Hogyan működik a BFS algoritmus?
A gráf bejárásához az algoritmusnak meg kell látogatnia, ellenőriznie kell és/vagy frissítenie kell minden egyes meg nem látogatott csomópontot egy faszerű struktúrában. A gráfbejárások aszerint vannak kategorizálva, hogy milyen sorrendben keresik fel a gráf csomópontjait.
A BFS algoritmus a gráf első vagy kezdő csomópontjától kezdi a műveletet, és alaposan bejárja azt. Ha sikeresen bejárta a kezdeti csomópontot, akkor a gráf következő nem bejárt csúcsát meglátogatja és megjelöli.
Ezért azt mondhatjuk, hogy az első iteráció során az aktuális csúcshoz tartozó összes csomópontot meglátogatjuk és bejárjuk. A BFS-algoritmus működésének megvalósításához egy egyszerű sormódszert használnak, amely a következő lépésekből áll:
Step 1)
A gráf minden csúcsa vagy csomópontja ismert. Például megjelölheti a csomópontot V-ként.
Step 2)
Abban az esetben, ha az V csúcsot nem éri el, adja hozzá a V csúcsot a BFS-sorhoz
Step 3)
Indítsa el a BFS keresést, és a befejezés után jelölje meg az V csúcsot látogatottként.
Step 4)
A BFS sor még mindig nem üres, ezért távolítsa el a gráf V csúcsát a sorból.
Step 5)
Keresse ki a gráf összes többi csúcsát, amely szomszédos az V csúcsgal
Step 6)
Minden szomszédos csúcshoz mondjuk a V1-et, ha még nem látogatták meg, akkor adjuk hozzá a V1-et a BFS-sorhoz
Step 7)
A BFS meglátogatja a V1-et, és megjelöli látogatottként, és törli a sorból.
Példa BFS algoritmusra
Step 1)
Van egy grafikonja, amely hét számot tartalmaz 0 és 6 között.
Step 2)
0 vagy nulla gyökércsomópontként lett megjelölve.
Step 3)
A 0 meglátogatja, megjelöli és beilleszti a sor adatstruktúrájába.
Step 4)
A fennmaradó 0 szomszédos és meg nem látogatott csomópont felkeresése, megjelölése és beillesztése a sorba.
Step 5)
A bejárási iterációk addig ismétlődnek, amíg az összes csomópontot meg nem látogatják.
A BFS algoritmus szabályai
Íme a BFS-algoritmus használatának fontos szabályai:
- Egy sor (FIFO-First in First Out) adatszerkezet a BFS használja.
- A gráf bármely csomópontját gyökérként megjelöli, és elkezdi bejárni az adatokat.
- A BFS bejárja a grafikon összes csomópontját, és folyamatosan eldobja őket, amikor elkészült.
- A BFS meglátogat egy szomszédos nem látogatott csomópontot, készként jelöli meg, és beilleszti egy sorba.
- Eltávolítja az előző csúcsot a sorból, ha nem található szomszédos csúcs.
- A BFS algoritmus addig iterál, amíg a gráf összes csúcsát sikeresen bejárják és befejezettként meg nem jelölik.
- Nincsenek BFS által okozott hurkok az adatok egyik csomópontról történő bejárása során sem.
A BFS algoritmus alkalmazásai
Vessünk egy pillantást néhány olyan valós alkalmazásra, ahol a BFS-algoritmus megvalósítása rendkívül hatékony lehet.
- Súlyozatlan grafikonok: A BFS algoritmus könnyen létrehozhatja a legrövidebb utat és egy minimális feszítőfát, hogy a gráf összes csúcsát a lehető legrövidebb idő alatt, nagy pontossággal meglátogassa.
- P2P hálózatok: A BFS megvalósítható az összes legközelebbi vagy szomszédos csomópont megtalálására egy peer to peer hálózatban. Ez gyorsabban megtalálja a szükséges adatokat.
- Webrobotok: A keresőmotorok vagy a webrobotok könnyen létrehozhatnak több szintű indexet a BFS használatával. A BFS megvalósítás a forrásból indul, amely a weboldal, majd meglátogatja az összes hivatkozást a forrásból.
- Navigációs rendszerek: A BFS segíthet megtalálni az összes szomszédos helyet a fő vagy a forrás helyéről.
- Hálózati műsorszórás: A sugárzott csomagot a BFS algoritmus irányítja, hogy megtalálja és elérje az összes csomópontot, amelynek címe van.
Összegzésként
- A gráfbejárás egy egyedi folyamat, amelyhez az algoritmusnak meg kell látogatnia, ellenőriznie kell és/vagy frissítenie kell minden egyes meg nem látogatott csomópontot egy faszerű struktúrában. A BFS algoritmus hasonló elven működik.
- Az algoritmus hasznos a gráf csomópontjainak elemzésére és az ezeken való áthaladás legrövidebb útvonalának megalkotására.
- Az algoritmus a lehető legkisebb számú iterációval és a lehető legrövidebb idő alatt bejárja a gráfot.
- A BFS egyetlen csomópontot (kezdeti vagy forráspontot) választ ki a gráfban, majd felkeresi a kiválasztott csomóponttal szomszédos összes csomópontot. A BFS egyenként éri el ezeket a csomópontokat.
- A meglátogatott és megjelölt adatokat a BFS egy sorba helyezi. A sor az első beérkezés alapján működik. Ezért a grafikonon először elhelyezett elem törlődik először, és ennek eredményeként kerül kinyomtatásra.
- A BFS algoritmus soha nem akadhat bele egy végtelen hurokba.
- A nagy pontosságú és robusztus megvalósításnak köszönhetően a BFS-t számos valós megoldásban használják, például P2P-hálózatokban, webrobotokban és hálózati műsorszórásban.