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

ArchiA BFS algoritmus tectúrája

  1. 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.
  2. 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.
  3. 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 BFS algoritmus működése

A gráf minden csúcsa vagy csomópontja ismert. Például megjelölheti a csomópontot V-ként.

Step 2)

A BFS algoritmus működése

Abban az esetben, ha az V csúcsot nem éri el, adja hozzá a V csúcsot a BFS-sorhoz

Step 3)

A BFS algoritmus működése

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 algoritmus működése

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)

A BFS algoritmus működése

Keresse ki a gráf összes többi csúcsát, amely szomszédos az V csúcsgal

Step 6)

A BFS algoritmus működése

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 algoritmus működése

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)

Példa BFS algoritmusra

Van egy grafikonja, amely hét számot tartalmaz 0 és 6 között.

Step 2)

Példa BFS algoritmusra

0 vagy nulla gyökércsomópontként lett megjelölve.

Step 3)

Példa BFS algoritmusra

A 0 meglátogatja, megjelöli és beilleszti a sor adatstruktúrájába.

Step 4)

Példa BFS algoritmusra

A fennmaradó 0 szomszédos és meg nem látogatott csomópont felkeresése, megjelölése és beillesztése a sorba.

Step 5)

Példa BFS algoritmusra

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.