Breadth First Search (BFS) algoritmus EXAMPLE-vel

Mi az a BFS algoritmus (Breadth-First Search)?

A szélességi keresés (BFS) egy algoritmus, amelyet adatok grafikonjainak ábrázolására, fában való keresésre vagy struktúrák bejárására használnak. A BFS teljes formája a szélességi 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

1. Az adat különböző szintjein bármelyik csomópontot megjelölhetjük kezdő vagy kezdeti csomópontként a bejárás megkezdéséhez. A BFS meglátogatja a csomópontot, meglátogatottként jelöli meg, és behelyezi a várólistába.
2. A BFS most meglátogatja a legközelebbi és a még nem látogatott csomópontokat, és megjelöli azokat. Ezek az értékek is hozzáadódnak a várólistához. A várólistán a következő adatok működnek: FIFO modell.
3. Hasonló módon a gráfon található legközelebbi és még meg nem látogatott csomópontokat elemzik, megjelölik és hozzáadják a várólistához. Ezeket az elemeket a rendszer a fogadásuk után törli a várólistából, és eredményként kinyomtatja.

Miért van szükségünk BFS algoritmusra?

Számos oka van annak, hogy miért érdemes a BFS algoritmust használni az adathalmaz kereséséhez. Íme néhány legfontosabb szempont, ami miatt ezt az algoritmust érdemes választani:

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

Tehát azt mondhatjuk, hogy az aktuális csúcshoz szomszédos összes csomópontot meglátogatjuk és bejárjuk az első iterációban. Egy egyszerű sorkezelési módszertant alkalmazunk a BFS algoritmus működésének megvalósításához, 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)

Ha a V csúcshoz nem férünk hozzá, akkor adjuk hozzá a V csúcsot a BFS várólistához.

Step 3)

Indítsd el a BFS keresést, és a befejezés után jelöld meg a 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)

Keresd meg a gráf összes többi csúcsát, amelyek szomszédosak az V csúccsal.

Step 6)

Minden szomszédos csúcshoz, mondjuk V1-hez, ha még nem látogatták meg, akkor adjuk hozzá V1-et a BFS várólistájához.

Step 7)

A BFS meglátogatja a V1-et, meglátogatottként jelöli meg, majd törli a sorból.

Példa BFS algoritmusra

Step 1)

Van egy grafikonod, amely hét számot ábrázol 0-tól 6-ig.

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ópontokat meglátogatja, megjelöli és beilleszti a várólistába.

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ármelyik csomópontját gyökérként jelölöd meg, és onnan kezded el bejárni az adatokat.
• A BFS bejárja a gráf összes csomópontját, és folyamatosan csökken.ping befejezettként.
• 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ál szomszédos csúcsot.
• A BFS algoritmus addig iterál, amíg a gráf összes csúcsán sikeresen át nem halad, és befejezettként nem jelöli meg őket.
• 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önnyedén létrehozza 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 és nagy pontossággal meglátogassa.
• P2P hálózatok: A BFS (Base Finder Search) megvalósítható a peer-to-peer hálózat összes legközelebbi vagy szomszédos csomópontjának megkeresésére. 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.

GYIK