Laiuse esimese otsingu (BFS) algoritm koos EXAMPLE'iga

Mis on BFS-i algoritm (Breadth-First Search)?

Breadth-first search (BFS) on algoritm, mida kasutatakse andmete graafikuks või puu otsimiseks või struktuuride läbimiseks. BFS-i täisvorm on Breadth-first otsing.

Algoritm külastab ja märgib tõhusalt kõiki graafiku võtmesõlmi täpselt laiuse suunas. See algoritm valib graafikul ühe sõlme (alg- või lähtepunkti) ja seejärel külastab kõiki valitud sõlmega külgnevaid sõlme. Pidage meeles, et BFS pääseb neile sõlmedele ükshaaval juurde.

Kui algoritm külastab ja märgib algussõlme, liigub see lähimate külastamata sõlmede poole ja analüüsib neid. Pärast külastamist on kõik sõlmed märgitud. Need iteratsioonid jätkuvad seni, kuni kõik graafiku sõlmed on edukalt külastatud ja märgitud.

Mis on graafiku läbimine?

Graafi läbimine on tavaliselt kasutatav metoodika tipu asukoha määramiseks graafikus. See on täiustatud otsingu algoritm, mis suudab graafikut kiiresti ja täpselt analüüsida koos külastatud tippude järjestuse märgistamisega. See protsess võimaldab teil kiiresti külastada graafiku iga sõlme, ilma et oleksite lukustatud lõpmatusse ahelasse.

BFS-i algoritmi arhitektuur

1. Andmete erinevatel tasemetel 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.
2. Nüüd külastab BFS lähimaid ja külastamata sõlme ning märgib need. Need väärtused lisatakse ka järjekorda. Järjekord töötab FIFO mudel.
3. Sarnasel viisil analüüsitakse graafiku ülejäänud lähimaid ja külastamata sõlmpunkte märgistatuna ja lisatakse järjekorda. Need üksused kustutatakse ootejärjekorrast ja prinditakse tulemuseks.

Miks me vajame BFS-i algoritmi?

Andmestiku otsimiseks BFS-i algoritmi kasutamiseks on palju põhjuseid. Mõned kõige olulisemad aspektid, mis muudavad selle algoritmi teie esimeseks valikuks, on järgmised:

• BFS on kasulik graafiku sõlmede analüüsimiseks ja nende läbimiseks lühima tee konstrueerimiseks.
• BFS suudab läbida graafiku väikseima arvu iteratsioonidega.
• BFS-i algoritmi arhitektuur on lihtne ja vastupidav.
• BFS-algoritmi tulemusel on teiste algoritmidega võrreldes kõrge täpsus.
• BFS-i iteratsioonid on sujuvad ja see algoritm ei saa lõpmatu ahela probleemiga vahele jääda.

Kuidas BFS-i algoritm töötab?

Graafiku läbimine nõuab, et algoritm külastaks, kontrolliks ja/või värskendaks puulaadses struktuuris iga üksikut külastamata sõlme. Graafiku läbimised liigitatakse graafiku sõlmede külastamise järjekorra järgi.

BFS-algoritm alustab toimingut graafiku esimesest ehk algussõlmest ja läbib selle põhjalikult. Kui see algsõlme edukalt läbib, külastatakse ja märgitakse graafiku järgmine läbimata tipp.

Seega võib öelda, et esimeses iteratsioonis külastatakse ja läbitakse kõik praeguse tipuga külgnevad sõlmed. BFS-i algoritmi töö rakendamiseks kasutatakse lihtsat järjekorra metoodikat ja see koosneb järgmistest sammudest:

Step 1)

Graafi iga tipp või sõlm on teada. Näiteks saate sõlme märkida kui V.

Step 2)

Kui tipule V ei pääseta juurde, lisage tipp V BFS-i järjekorda

Step 3)

Käivitage BFS-otsing ja pärast lõpetamist märkige tipp V külastatuks.

Step 4)

BFS-i järjekord ei ole ikka veel tühi, seetõttu eemaldage graafiku tipp V järjekorrast.

Step 5)

Otsi graafikult kõik ülejäänud tipud, mis külgnevad tipuga V

Step 6)

Iga külgneva tipu puhul oletame V1, kui seda pole veel külastatud, siis lisa V1 BFS-i järjekorda

Step 7)

BFS külastab versiooni V1 ja märgib selle külastatuks ning kustutab selle järjekorrast.

BFS-i algoritmi näide

Step 1)

Teil on seitsmest numbrist koosnev graafik vahemikus 0–6.

Step 2)

0 või null on märgitud juursõlmeks.

Step 3)

0 külastatakse, märgitakse ja sisestatakse järjekorra andmestruktuuri.

Step 4)

Ülejäänud 0 külgnevat ja külastamata sõlme külastatakse, märgitakse ja lisatakse järjekorda.

Step 5)

Läbivaid iteratsioone korratakse, kuni kõik sõlmed on külastatud.

BFS-i algoritmi reeglid

Siin on olulised reeglid BFS-algoritmi kasutamiseks:

• Järjekord (FIFO-First in First Out) andmete struktuur kasutab BFS.
• Märgid graafikus suvalise sõlme juureks ja hakkad sealt andmeid läbima.
• BFS läbib kõik graafikul olevad sõlmed ja kukutab need valmis.
• BFS külastab külgnevat külastamata sõlme, märgib selle tehtuks ja lisab järjekorda.
• Eemaldab järjekorrast eelmise tipu, kui külgnevat tippu ei leita.
• BFS-algoritm itereerib, kuni kõik graafiku tipud on edukalt läbitud ja märgitud lõpetatuks.
• Andmete läbimisel ühestki sõlmest pole BFS-i põhjustatud silmuseid.

BFS-i algoritmi rakendused

Vaatame mõningaid reaalelu rakendusi, kus BFS-i algoritmi rakendamine võib olla väga tõhus.

• Kaalumata graafikud: BFS-algoritm saab hõlpsasti luua lühima tee ja minimaalse ulatuva puu, et külastada graafiku kõiki tippe võimalikult lühikese aja jooksul ja suure täpsusega.
• P2P võrgud: BFS-i saab rakendada kõigi lähimate või naabersõlmede leidmiseks peer-to-peer võrgus. Nii leiate vajalikud andmed kiiremini.
• Veebiindeksoijad: Otsingumootorid või veebiindeksoijad saavad BFS-i abil hõlpsasti luua mitme taseme indekseid. BFS-i juurutamine algab allikast, mis on veebileht, ja seejärel külastab see kõiki selle allika linke.
• Navigatsioonisüsteemid: BFS võib aidata leida kõik naaberkohad põhi- või lähtekohast.
• Võrguedastus: Edastatud paketti juhib BFS-algoritm, et leida ja jõuda kõigi sõlmedeni, mille jaoks sellel on aadress.

kokkuvõte

• Graafiku läbimine on ainulaadne protsess, mis nõuab, et algoritm külastaks, kontrolliks ja/või värskendaks iga üksikut külastamata sõlme puulaadses struktuuris. BFS-i algoritm töötab sarnasel põhimõttel.
• Algoritm on kasulik graafiku sõlmede analüüsimiseks ja nende läbimiseks lühima tee konstrueerimiseks.
• Algoritm läbib graafiku väikseima arvu iteratsioonide ja võimalikult lühikese ajaga.
• BFS valib graafikul ühe sõlme (alg- või lähtepunkti) ja seejärel külastab kõiki valitud sõlmega külgnevaid sõlme. BFS pääseb neile sõlmedele ükshaaval juurde.
• Külastatud ja märgitud andmed asetab BFS järjekorda. Järjekord toimib põhimõttel "esimene sees esimene välja". Seega kustutatakse kõigepealt graafikule asetatud element ja prinditakse selle tulemusena.
• BFS-algoritm ei saa kunagi sattuda lõpmatusse ahelasse.
• Tänu suurele täpsusele ja jõulisele juurutamisele kasutatakse BFS-i mitmetes reaalsetes lahendustes, nagu P2P-võrgud, veebiindeksoijad ja võrgulevi.