Mi az a BFS algoritmus (szélesség-első keresés)?
A Szélesség első keresése (BFS) egy algoritmus, amelyet adatok ábrázolására, vagy fa vagy bejáró struktúrák keresésére használnak. A BFS teljes formája a Szélesség első keresése.
Az algoritmus hatékonyan meglátogatja és megjelöli az összes kulcscsomópontot egy grafikonon, pontosan szélességben. Ez az algoritmus egyetlen csomópontot (kezdeti vagy forráspontot) választ ki a grafikonból, majd meglátogatja a kiválasztott csomópont mellett található összes csomópontot. Ne feledje, hogy a BFS egyesével éri el ezeket a csomópontokat.
Miután az algoritmus meglátogatta és megjelöli a kezdő csomópontot, akkor a legközelebbi meg nem látogatott csomópontok felé halad és elemzi őket. Miután meglátogatta, az összes csomópont meg van jelölve. Ezek az iterációk addig folytatódnak, amíg a grafikon összes csomópontját sikeresen meg nem látogatták és meg nem jelölte.
Ebben az algoritmus oktatóanyagban megtudhatja:
- Mi az a BFS algoritmus (szélesség-első keresés)?
- Mi az a grafikon bejárása?
- A BFS algoritmus architektúrája
- Miért van szükségünk BFS algoritmusra?
- Hogyan működik a BFS algoritmus?
- Példa BFS algoritmusra
- A BFS algoritmus szabályai
- A BFS algoritmus alkalmazásai
Mi az a grafikon bejárása?
A gráf bejárása általánosan alkalmazott módszertan a csúcs pozíciójának a grafikonon történő meghatározására. Ez egy fejlett keresési algoritmus, amely gyorsan és pontosan elemezheti a gráfot, a megjelölt csúcsok sorrendjének megjelölésével együtt. Ez a folyamat lehetővé teszi, hogy gyorsan meglátogassa a grafikon egyes csomópontjait anélkül, hogy bezáródna egy végtelen ciklusba.
A BFS algoritmus architektúrája
- Az adatok különféle szintjein bármely csomópontot megjelölhet kezdő vagy kezdő csomópontként az átjárás megkezdéséhez. A BFS meglátogatja a csomópontot, meglátogatottként megjelöli, és elhelyezi a sorban.
- Most a BFS meglátogatja a legközelebbi és meg nem látogatott csomópontokat, és megjelöli őket. Ezek az értékek szintén hozzáadódnak a sorhoz. A sor a FIFO modellen működik.
- Hasonló módon elemezzük a grafikonon a legközelebbi és a meg nem látogatott csomópontokat megjelölve és hozzáadva a sorhoz. Ezeket az elemeket vételként törli a sorból, és ennek eredményeként kinyomtatja őket.
Miért van szükségünk BFS algoritmusra?
Számos oka van annak, hogy a BFS algoritmust használja az adatkészlet keresésére. Néhány legfontosabb szempont, amely miatt ez az algoritmus az első választás:
- A BFS hasznos a csomópontok grafikonon történő elemzéséhez és az ezeken való áthaladás legrövidebb útjának felépítéséhez.
- A BFS egy grafikonon haladhat át a legkisebb számú iterációban.
- A BFS algoritmus felépítése egyszerű és robusztus.
- A BFS algoritmus eredménye nagy pontossággal rendelkezik más algoritmusokhoz képest.
- A BFS iterációi zökkenőmentesek, és nincs esély arra, hogy ez az algoritmus végtelen hurokproblémába keveredjen.
Hogyan működik a BFS algoritmus?
A grafikon bejárásához az algoritmusnak meg kell látogatnia, ellenőriznie és / vagy frissítenie kell egy fa-szerű szerkezet minden egyes meg nem látogatott csomópontját. A grafikonok bejárása sorrendbe van sorolva, amelyben meglátogatják a grafikon csomópontjait.
A BFS algoritmus a grafikon első vagy kezdő csomópontjától kezdi a műveletet, és alaposan bejárja azt. Miután sikeresen áthaladt a kezdeti csomóponton, akkor meglátogatja és megjelöli a grafikon következő nem bejárt csúcsát.
Ennélfogva elmondhatja, hogy az aktuális csúccsal szomszédos összes csomópont az első iterációban meglátogatott és bejáratott. Egy egyszerű várakozási módszertant alkalmaznak a BFS algoritmus működésének megvalósításához, amely a következő lépésekből áll:
1. lépés)
A grafikon minden csúcsa vagy csomópontja ismert. Például a csomópontot V-ként jelölheti meg.
2. lépés)
Abban az esetben, ha az V csúcs nem érhető el, adja hozzá az V csúcsot a BFS várólistához
3. lépés)
Indítsa el a BFS keresést, és a befejezés után jelölje meg az V. csúcsot meglátogatottként.
4. lépés)
A BFS sor még mindig nem üres, ezért távolítsa el a grafikon V csúcsát a sorból.
5. lépés)
Szerezze be a grafikon összes többi csúcsát, amelyek szomszédosak az V csúccsal
6. lépés)
Tegyük fel, hogy minden szomszédos csúcsnál V1, ha még nem látogatta meg, adja hozzá a V1-et a BFS-sorhoz
7. lépés)
A BFS meglátogatja a V1-et, meglátogatja látogatottként, és törli a sorból.
Példa BFS algoritmusra
1. lépés)
Hét számgrafikonja van, 0 és 6 között.
2. lépés)
A 0 vagy nulla értéket gyökércsomópontként jelöltük meg.
3. lépés)
A 0 meglátogatásra kerül, megjelölik és beszúrják a várólista adatstruktúrájába.
4. lépés)
A fennmaradó 0 szomszédos és nem látogatott csomópont felkeresi, megjelöli és beszúrja a sorba.
5. lépés)
Az áthaladó iterációkat addig ismételjük, amíg az összes csomópontot meg nem látogatjuk.
A BFS algoritmus szabályai
Itt vannak a BFS algoritmus használatának fontos szabályai:
- Soros (FIFO-First in First Out) adatstruktúrát használ a BFS.
- A gráfban lévő bármelyik csomópontot gyökérként megjelöli, és elkezdi bejárni az adatokat belőle.
- A BFS áthalad a grafikon összes csomópontján, és befejezésként folyamatosan dobja őket.
- A BFS meglátogatja a szomszédos nem látogatott csomópontot, készként megjelöli és beszúrja 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 ismétlődik, amíg a grafikon összes csúcsát sikeresen bejárja és befejezettként jelöli.
- Nincs csomópontból származó adatok áthaladása során a BFS által okozott hurkok.
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 nagyon hatékony lehet.
- Súlyozatlan grafikonok: A BFS algoritmus könnyen létrehozhatja a legrövidebb utat és egy minimális átfogó fát, hogy a grafikon összes csúcsát a lehető legrövidebb idő alatt, nagy pontossággal látogassa meg.
- P2P hálózatok: A BFS megvalósítható az összes legközelebbi vagy szomszédos csomópont megkeresésére a 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öbbszintű indexeket BFS alkalmazásával. A BFS megvalósítása a forrásból indul ki, amely a weboldal, majd meglátogatja az adott forrás összes hivatkozását.
- 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 vezérli, hogy megtalálja és elérje az összes csomópontot, amelynek címe van.
Összegzés
- A grafikon bejárása olyan egyedi folyamat, amely megköveteli, hogy az algoritmus meglátogasson, ellenőrizzen és / vagy frissítsen egy fa nélküli szerkezet minden egyes meg nem látogatott csomópontját. A BFS algoritmus hasonló elven működik.
- Az algoritmus hasznos a csomópontok grafikonon történő elemzéséhez és az ezeken való áthaladás legrövidebb útjának felépítéséhez.
- Az algoritmus a grafikont a lehető legkevesebb ismétléssel és a lehető legrövidebb idő alatt járja be.
- A BFS egyetlen csomópontot (kezdeti vagy forráspontot) választ ki a grafikonból, majd meglátogatja a kiválasztott csomópont mellett található összes csomópontot. A BFS egyesével éri el ezeket a csomópontokat.
- A meglátogatott és megjelölt adatokat a BFS sorba rakja. A várakozási sor az első az első kimenetel alapján működik. Ezért a grafikonon először elhelyezett elemet először törlik, és ennek eredményeként kinyomtatják.
- A BFS algoritmus soha nem ragadhat bele egy végtelen ciklusba.
- A nagy pontosságú és robusztus megvalósítás miatt 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.