Kas yra BFS algoritmas („Pirmojo pločio paieška“)?
Pirmojo pločio paieška (BFS) yra algoritmas, kuris naudojamas duomenims braižyti, medžiui ar perėjimo struktūroms ieškoti. Visa BFS forma yra „Pirmojo platumo“ paieška.
Algoritmas efektyviai aplanko ir tiksliai pažymi visus pagrindinius mazgus grafike. Šis algoritmas grafike parenka vieną mazgą (pradinį arba šaltinio tašką) ir tada aplanko visus mazgus, esančius šalia pasirinkto mazgo. Atminkite, kad BFS prie šių mazgų prisijungia po vieną.
Kai algoritmas aplanko ir pažymi pradinį mazgą, jis juda link artimiausių nelankytų mazgų ir juos analizuoja. Apsilankę visi mazgai yra pažymėti. Šios iteracijos tęsiasi tol, kol visi grafiko mazgai bus sėkmingai aplankyti ir pažymėti.
Šioje algoritmo pamokoje sužinosite:
- Kas yra BFS algoritmas („Pirmojo pločio paieška“)?
- Kas yra grafiko perėjimai?
- BFS algoritmo architektūra
- Kodėl mums reikia BFS algoritmo?
- Kaip veikia BFS algoritmas?
- BFS algoritmo pavyzdys
- BFS algoritmo taisyklės
- BFS algoritmo taikymai
Kas yra grafiko perėjimai?
Grafiko perėjimas yra dažniausiai naudojama metodika, skirta nustatyti viršūnės padėtį grafike. Tai yra išplėstinis paieškos algoritmas, kuris gali greitai ir tiksliai analizuoti grafiką ir pažymėti aplankytų viršūnių seką. Šis procesas leidžia greitai aplankyti kiekvieną diagramos mazgą, neužsiblokavus begalinėje kilpoje.
BFS algoritmo architektūra
- Įvairiuose duomenų lygiuose galite pažymėti bet kurį mazgą kaip pradinį ar pradinį mazgą, kad pradėtumėte važiuoti. BFS aplankys mazgą, pažymės jį kaip aplankytą ir patalpins jį į eilę.
- Dabar BFS aplankys artimiausius ir neaplankytus mazgus ir juos pažymės. Šios vertės taip pat pridedamos prie eilės. Eilė veikia pagal FIFO modelį.
- Panašiai analizuojami pažymėti ir pridėti prie eilės likę artimiausi ir neaplankyti mazgai diagramoje. Šie elementai ištrinami iš eilės kaip gaunami ir atspausdinami kaip rezultatas.
Kodėl mums reikia BFS algoritmo?
Yra daugybė priežasčių, kodėl BFS algoritmą reikia naudoti ieškant jūsų duomenų rinkinio. Keli svarbiausi aspektai, dėl kurių šis algoritmas yra jūsų pirmasis pasirinkimas, yra šie:
- BFS yra naudinga analizuojant mazgus diagramoje ir sukonstruojant trumpiausią kelią per juos.
- BFS per grafiką gali pereiti mažiausią kartojimų skaičių.
- BFS algoritmo architektūra yra paprasta ir tvirta.
- BFS algoritmo rezultatas turi aukštą tikslumo lygį, palyginti su kitais algoritmais.
- BFS iteracijos yra vientisos ir nėra galimybės, kad šis algoritmas pakliūtų į begalinę kilpos problemą.
Kaip veikia BFS algoritmas?
Norint pereiti grafiką, algoritmas turi aplankyti, patikrinti ir (arba) atnaujinti kiekvieną atskirai neaplankytą mazgą, panašų į medį. Grafikų perėjimai skirstomi į kategorijas, pagal kurias jie aplanko grafo mazgus.
BFS algoritmas paleidžia operaciją nuo pirmojo ar pradinio mazgo grafike ir kruopščiai jį pereina. Kai jis sėkmingai praeina pradinį mazgą, tada aplankoma ir pažymima kita grafiko viršūnių viršūnė.
Taigi galite sakyti, kad visi mazgai, esantys šalia dabartinės viršūnės, yra aplankomi ir pereinami per pirmąją iteraciją. BFS algoritmui įgyvendinti naudojama paprasta eilės metodika, kurią sudaro šie žingsniai:
1 žingsnis)
Kiekviena grafiko viršūnė ar mazgas yra žinomi. Pavyzdžiui, galite pažymėti mazgą kaip V.
2 žingsnis)
Jei viršūnė V nepasiekiama, pridėkite viršūnę V į BFS eilę
3 žingsnis)
Pradėkite BFS paiešką, o baigus pažymėkite V viršūnę kaip aplankytą.
4 žingsnis)
BFS eilė vis dar nėra tuščia, todėl pašalinkite grafiko viršūnę V iš eilės.
5 žingsnis)
Gaukite visas likusias grafiko viršūnes, esančias šalia V viršūnės
6 žingsnis)
Tarkime, kad kiekviena gretima viršūnė yra V1, jei ji dar neaplankyta, pridėkite V1 prie BFS eilės
7 žingsnis)
BFS apsilankys V1, pažymės jį kaip aplankytą ir ištrins iš eilės.
BFS algoritmo pavyzdys
1 žingsnis)
Turite septynių skaičių grafiką, svyruojantį nuo 0 iki 6.
2 žingsnis)
0 arba nulis pažymėtas kaip šakninis mazgas.
3 žingsnis)
0 aplankoma, pažymima ir įtraukiama į eilės duomenų struktūrą.
4 žingsnis)
Likę 0 gretimų ir neaplankytų mazgų aplankomi, pažymimi ir įterpiami į eilę.
5 žingsnis)
Kertamos iteracijos kartojamos, kol aplankomi visi mazgai.
BFS algoritmo taisyklės
Čia pateikiamos svarbios BFS algoritmo naudojimo taisyklės:
- BFS naudoja eilės („FIFO-First in First Out“) duomenų struktūrą.
- Bet kurį diagramos mazgą pažymite kaip šaknį ir pradedate keliauti iš jo esančiais duomenimis.
- BFS kerta visus grafiko mazgus ir vis juos numeta kaip užbaigtus.
- BFS aplanko gretimą nelankytą mazgą, pažymi jį kaip atliktą ir įtraukia į eilę.
- Pašalina ankstesnę viršūnę iš eilės, jei gretimos viršūnės nerandama.
- BFS algoritmas kartojasi, kol visos diagramos viršūnės sėkmingai praeinamos ir pažymimos kaip baigtos.
- Keliaujant duomenis iš bet kurio mazgo, nėra BFS kilpų.
BFS algoritmo taikymai
Pažvelkime į kai kurias realaus gyvenimo programas, kuriose BFS algoritmo diegimas gali būti labai efektyvus.
- Neįvertinti grafikai: BFS algoritmas gali lengvai sukurti trumpiausią kelią ir minimalų tarpatramį medį, kad būtų galima aplankyti visas grafiko viršūnes per trumpiausią įmanomą laiką ir labai tiksliai.
- P2P tinklai: BFS gali būti įdiegtas norint rasti visus artimiausius ar kaimyninius mazgus tinkle „peer to peer“. Tai padės reikalingus duomenis rasti greičiau.
- Žiniatinklio tikrintuvai : Paieškos varikliai ar žiniatinklio tikrintuvai gali lengvai sukurti kelių lygių indeksus naudodami BFS. BFS diegimas prasideda nuo šaltinio, kuris yra tinklalapis, ir tada jis aplanko visas to šaltinio nuorodas.
- Navigacijos sistemos: BFS gali padėti surasti visas kaimynines vietas iš pagrindinės ar šaltinio vietos.
- Tinklo transliavimas: transliuojamą paketą valdo BFS algoritmas, kad surastų ir pasiektų visus mazgus, kuriems jis turi adresą.
Santrauka
- Grafiko perėjimas yra unikalus procesas, reikalaujantis algoritmo aplankyti, patikrinti ir (arba) atnaujinti kiekvieną atskirą neaplankytą mazgą, panašų į medį. BFS algoritmas veikia panašiu principu.
- Algoritmas yra naudingas analizuojant mazgus diagramoje ir sukonstruojant trumpiausią kelią per juos.
- Algoritmas grafiką kerta per mažiausią kartojimų skaičių ir kuo trumpesnį laiką.
- BFS grafike parenka vieną mazgą (pradinį arba šaltinio tašką) ir tada aplanko visus mazgus, esančius greta pasirinkto mazgo. BFS prie šių mazgų prisijungia po vieną.
- Lankomus ir pažymėtus duomenis BFS pateikia eilėje. Eilė veikia pagal principą „pirmas iš pirmojo“. Taigi pirmiausia grafike įdėtas elementas pirmiausia pašalinamas ir atspausdinamas.
- BFS algoritmas niekada negali pakliūti į begalinę kilpą.
- Dėl didelio tikslumo ir patikimo diegimo BFS naudojamas įvairiuose realaus gyvenimo sprendimuose, tokiuose kaip P2P tinklai, žiniatinklio tikrintuvai ir tinklo transliacijos.