Laiuse esimese otsingu (BFS) algoritm koos EXAMPLE'iga

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

Laiuseotsing (inglise keeles broadth-first search, BFS) on algoritm, mida kasutatakse andmete graafikute loomiseks, puu otsimiseks või struktuuride läbimiseks. BFS-i täielik vorm on laiuseotsing.

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 tasanditel saate märkida mis tahes sõlme läbimise alustamiseks algus- või algsõlmeks. BFS külastab sõlme, märgib selle külastatuks ja asetab järjekorda.
2. Nüüd külastab BFS lähimaid ja külastamata sõlmi ning märgib need. Need väärtused lisatakse samuti järjekorda. Järjekord töötab FIFO mudel.
3. Sarnasel viisil analüüsitakse, märgistatakse ja lisatakse graafikule lähimad ja külastamata sõlmed. Need elemendid kustutatakse järjekorrast kohe, kui need on vastu võetud, ja tulemus prinditakse.

Miks me vajame BFS-i algoritmi?

BFS-algoritmi kasutamiseks andmestiku otsimiseks on arvukalt põhjuseid. Mõned kõige olulisemad aspektid, mis teevad sellest algoritmist teie esimese valiku, 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-algoritmi toimimise 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 tippu V ei pääseta juurde, lisage tipp V BFS-i järjekorda.

Step 3)

Käivita BFS-i otsing ja pärast selle lõpetamist märgi 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)

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

Step 6)

Iga külgneva tipu, näiteks V1, kohta, kui seda pole veel külastatud, lisage V1 BFS-i järjekorda.

Step 7)

BFS külastab V1-d, märgib selle külastatuks ja kustutab järjekorrast.

BFS-i algoritmi näide

Step 1)

Sul on graafik seitsmest arvust vahemikus 0 kuni 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ülgnevad ja külastamata sõlmed külastatakse, märgistatakse ja lisatakse järjekorda.

Step 5)

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

BFS-i algoritmi reeglid

BFS-algoritmi kasutamiseks on olulised reeglid järgmised:

• Järjekord (FIFO – esimesena sisse, esimesena välja) andmete struktuur kasutab BFS.
• Sa märgid graafikus suvalise sõlme juureks ja hakkad sealt andmeid läbima.
• BFS läbib kõik graafi sõlmed ja hoiab languseping need lõpetatuks.
• BFS külastab külgnevat külastamata sõlme, märgib selle tehtuks ja lisab järjekorda.
• See eemaldab eelmise tipu järjekorrast juhul, kui külgnevat tippu ei leita.
• BFS-i algoritm itereerib seni, kuni kõik graafi 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 suudab hõlpsalt luua lühima tee ja minimaalse ulatuvusega puu, et külastada kõiki graafi 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. See leiab vajalikud andmed kiiremini üles.
• 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.

KKK