Mis on BFS-i algoritm (laiuse esimene otsing)?
Laiuse esimene otsing (BFS) on algoritm, mida kasutatakse andmete graafikaks või puu otsimiseks või läbivate struktuuride otsimiseks. BFS-i täielik vorm on laius-esimene otsing.
Algoritm külastab ja tähistab graafikus kõiki võtmesõlme tõhusalt ja täpselt. See algoritm valib graafikust ühe sõlme (alg- või lähtekoha) ja külastab seejärel kõiki valitud sõlmega külgnevaid sõlme. Pidage meeles, et BFS pääseb nendele sõlmedele ükshaaval juurde.
Kui algoritm külastab ja tähistab algussõlme, liigub see lähimate külastamata sõlmede suunas ja analüüsib neid. Pärast külastamist märgitakse kõik sõlmed. Need iteratsioonid jätkuvad seni, kuni graafiku kõik sõlmed on edukalt külastatud ja märgistatud.
Selles algoritmi õpetuses saate teada:
- Mis on BFS-i algoritm (laiuse esimene otsing)?
- Mis on graafiku läbimine?
- BFS-i algoritmi arhitektuur
- Miks me vajame BFS-i algoritmi?
- Kuidas BFS-i algoritm töötab?
- Näide BFS-i algoritmist
- BFS-i algoritmi reeglid
- BFS-i algoritmi rakendused
Mis on graafiku läbimine?
Graafi läbimine on graafiku tipupositsiooni leidmiseks tavaliselt kasutatav metoodika. See on täiustatud otsingu algoritm, mis võimaldab graafikut kiiruse ja täpsusega analüüsida koos külastatud tippude järjestuse märkimisega. See protsess võimaldab teil kiiresti külastada graafiku iga sõlme, lukustamata seda lõpmatusse silmusesse.
BFS-i algoritmi arhitektuur
- Andmete erinevatel tasanditel saate läbimise alustamiseks märkida mis tahes sõlme algus- või algsõlmeks. BFS külastab sõlme ja märgib selle külastatuks ning asetab selle järjekorda.
- Nüüd külastab BFS lähimaid ja külastamata sõlme ning märgistab need. Need väärtused lisatakse ka järjekorda. Järjekord töötab FIFO mudeli järgi.
- Sarnasel viisil analüüsitakse graafikus ülejäänud lähimaid ja külastamata sõlme märgistatuna ja lisatakse järjekorda. Need üksused kustutatakse vastuvõtmise järjekorrast ja selle tulemusena prinditakse.
Miks me vajame BFS-i algoritmi?
Andmekogumi otsimisel on BFS-i algoritmi kasutamiseks mitmeid põhjuseid. Mõned kõige olulisemad aspektid, mis muudavad selle algoritmi teie esimeseks valikuks, on:
- BFS on kasulik graafil olevate sõlmede analüüsimiseks ja nende kaudu läbitava lühima tee ehitamiseks.
- BFS saab graafiku kaudu liikuda kõige väiksemas korduste arvus.
- BFS-i algoritmi arhitektuur on lihtne ja vastupidav.
- BFS-i algoritmi tulemus on teiste algoritmidega võrreldes kõrge täpsusega.
- BFS-i kordused on sujuvad ja puudub võimalus, et see algoritm jääks lõputu silmusprobleemi vahele.
Kuidas BFS-i algoritm töötab?
Graafiku läbimine nõuab, et algoritm külastaks, kontrolliks ja / või värskendaks puulaadse struktuuri iga üksikut külastamata sõlme. Graafiku läbimine liigitatakse graafiku sõlmede külastamise järjekorra järgi.
BFS-i algoritm alustab operatsiooni graafiku esimesest või algsõlmest ja läbib selle põhjalikult. Kui see läbib edukalt algsõlme, külastatakse graafiku järgmist läbimata tippu ja märgitakse see.
Seega võite öelda, et kõik praeguse tipuga külgnevad sõlmed külastatakse ja läbitakse esimeses iteratsioonis. BFS-i algoritmi töö juurutamiseks kasutatakse lihtsat järjekorra metoodikat ja see koosneb järgmistest sammudest:
Samm 1)
Graafiku iga tipp või sõlm on teada. Näiteks võite sõlme märkida tähega V.
2. samm)
Kui tipule V ei pääse juurde, lisage tipp V BFS-i järjekorda
3. samm)
Alustage BFS-i otsingut ja pärast lõpetamist märkige tipp V külastatuks.
4. samm)
BFS-i järjekord pole ikka veel tühi, seega eemaldage graafiku tipp V järjekorrast.
5. samm)
Leidke graafikult kõik ülejäänud tipud, mis külgnevad tipuga V
6. samm)
Oletame iga külgneva tipu puhul V1, kui seda veel ei külastata, lisage V1 BFS-i järjekorda
7. samm)
BFS külastab V1, märgib selle külastatuks ja kustutab selle järjekorrast.
Näide BFS-i algoritmist
Samm 1)
Teil on seitsmest numbrist koosnev graafik vahemikus 0–6.
2. samm)
0 või null on märgitud juursõlmeks.
3. samm)
0 külastatakse, märgitakse ja lisatakse järjekorra andmestruktuuri.
4. samm)
Ülejäänud 0 külgnevat ja külastamata sõlme külastatakse, märgitakse ja sisestatakse järjekorda.
5. samm)
Läbivaid kordusi korratakse seni, kuni kõik sõlmed on külastatud.
BFS-i algoritmi reeglid
Siin on olulised reeglid BFS-i algoritmi kasutamiseks:
- BFS kasutab järjekorra (FIFO-First in First Out) andmestruktuuri.
- Märkite kõik graafi sõlmed juurena ja hakkate sellest andmeid läbima.
- BFS läbib graafiku kõik sõlmed ja viskab neid lõpetatuna edasi.
- BFS külastab külgnevat külastamata sõlme, märgib selle tehtuks ja sisestab selle järjekorda.
- Eemaldab järjekorrast eelmise tipu juhul, kui külgnevat tippu ei leita.
- BFS-i algoritm kordub seni, kuni graafiku kõik tipud on edukalt läbitud ja täidetuks märgitud.
- Ühestki sõlmpunktist andmete liikumise ajal ei ole BFS-i põhjustatud silmuseid.
BFS-i algoritmi rakendused
Vaatame mõnda päriselus rakendust, kus BFS-i algoritmi juurutamine võib olla väga tõhus.
- Kaalumata graafikud: BFS-i algoritm suudab hõlpsasti luua lühima tee ja minimaalse ulatusega puu, et külastada graafiku kõiki tippe võimalikult lühikese aja jooksul suure täpsusega.
- P2P võrgud: BFS-i saab rakendada kõigi lähimate või naabruses asuvate sõlmede leidmiseks võrdõigusvõrgus. See leiab vajalikud andmed kiiremini.
- Veebirobotid: otsingumootorid või veebirobotid saavad BFS-i abil hõlpsasti koostada mitut indeksitaset. BFS-i juurutamine algab allikast, milleks on veebileht, ja seejärel külastab see kõik selle allika lingid.
- Navigatsioonisüsteemid: BFS aitab leida kõiki naaberkohti pea- või allikakohast.
- Võrguülekanne: BFS-i algoritm juhib levitatavat paketti kõigi sõlmede leidmiseks ja nendeni jõudmiseks, millele see on suunatud.
Kokkuvõte
- Graafiku läbimine on ainulaadne protsess, mis nõuab, et algoritm külastaks, kontrolliks ja / või värskendaks kõiki üksikuid külastamata sõlmi puulaadses struktuuris. BFS-i algoritm töötab sarnasel põhimõttel.
- Algoritm on kasulik graafi sõlmede analüüsimiseks ja nende kaudu läbitava lühima tee ehitamiseks.
- Algoritm läbib graafiku võimalikult väikeste korduste arvuga ja võimalikult lühikese ajaga.
- BFS valib graafikust ühe sõlme (alg- või lähtekoha) ja külastab seejärel kõiki valitud sõlmega külgnevaid sõlme. BFS pääseb nendele sõlmedele ükshaaval juurde.
- Külastatud ja märgitud andmed paigutab BFS järjekorda. Järjekord töötab põhimõttel "esimene in esimene". Seega kustutatakse kõigepealt graafikusse paigutatud element ja selle tulemusena prinditakse see.
- BFS-i algoritm ei saa kunagi lõputu silmusesse sattuda.
- Suure täpsuse ja kindla rakendamise tõttu kasutatakse BFS-i mitmetes reaalsetes lahendustes nagu P2P-võrgud, veebirobotid ja võrguteenused.