Mikä on BFS-algoritmi (leveyshaku)?
Leveys-ensimmäinen haku (BFS) on algoritmi, jota käytetään tietojen piirtämiseen tai puun tai kulkevien rakenteiden etsimiseen. BFS: n koko muoto on leveyshaku.
Algoritmi vierailee ja merkitsee tehokkaasti kaikki kaavion avainsolmut tarkasti leveydeltään. Tämä algoritmi valitsee kaaviosta yhden solmun (alku- tai lähdekohdan) ja vierailee sitten kaikki valitun solmun vieressä olevat solmut. Muista, että BFS käyttää näitä solmuja yksitellen.
Kun algoritmi vierailee ja merkitsee aloitussolmun, se siirtyy kohti lähimpiä avaamattomia solmuja ja analysoi ne. Vierailun jälkeen kaikki solmut on merkitty. Nämä iteraatiot jatkuvat, kunnes kaavion kaikki solmut on vierailtu ja merkitty onnistuneesti.
Tässä algoritmin opetusohjelmassa opit:
- Mikä on BFS-algoritmi (leveyshaku)?
- Mikä on graafin läpikäynti?
- BFS-algoritmin arkkitehtuuri
- Miksi tarvitsemme BFS-algoritmia?
- Kuinka BFS-algoritmi toimii?
- Esimerkki BFS-algoritmista
- BFS-algoritmin säännöt
- BFS-algoritmin sovellukset
Mikä on graafin läpikäynti?
Kuvaajan läpikäynti on yleisesti käytetty menetelmä kärkipisteen paikantamiseksi kaaviossa. Se on edistynyt hakualgoritmi, joka pystyy analysoimaan kuvaajan nopeudella ja tarkkuudella sekä merkitsemään vierailtujen pisteiden järjestyksen. Tämän prosessin avulla voit käydä nopeasti kaavion jokaisessa solmussa lukitsematta sitä loputtomaan silmukkaan.
BFS-algoritmin arkkitehtuuri
- Tietojen eri tasoilla voit merkitä minkä tahansa solmun alkusolmuksi tai alkusolmuksi aloittaaksesi kulkemisen. BFS vierailee solmussa ja merkitsee sen käydyksi ja sijoittaa sen jonoon.
- Nyt BFS vierailee lähimmissä ja vierailemattomissa solmuissa ja merkitsee ne. Nämä arvot lisätään myös jonoon. Jono toimii FIFO-mallin mukaan.
- Samalla tavalla kaaviossa jäljellä olevat lähimmät ja vierailemattomat solmut analysoidaan merkittynä ja lisätään jonoon. Nämä kohteet poistetaan jonosta vastaanottona ja tulostetaan tuloksena.
Miksi tarvitsemme BFS-algoritmia?
On olemassa useita syitä käyttää BFS-algoritmia tietojoukon etsimiseen. Jotkut tärkeimmistä näkökohdista, jotka tekevät tästä algoritmista ensimmäisen valinnan, ovat:
- BFS on hyödyllinen solmujen analysoimiseksi kaaviossa ja lyhyimmän kulkureitin rakentamiseksi näiden läpi.
- BFS pystyy kulkemaan kaavion läpi pienimmässä määrin iteraatioita.
- BFS-algoritmin arkkitehtuuri on yksinkertainen ja kestävä.
- BFS-algoritmin tuloksella on korkea tarkkuustaso muihin algoritmeihin verrattuna.
- BFS-iteraatiot ovat saumattomia, eikä ole mahdollista, että tämä algoritmi tarttuisi loputtomaan silmukkaongelmaan.
Kuinka BFS-algoritmi toimii?
Kaavion läpikäynti vaatii algoritmin vierailemaan, tarkistamaan ja / tai päivittämään kaikki yksittäiset vierailemattomat solmut puumaisessa rakenteessa. Kaavioiden kulku on luokiteltu järjestyksessä, jossa ne käyvät kaavion solmuissa.
BFS-algoritmi aloittaa operaation kaavion ensimmäisestä tai alkusolmusta ja kulkee sen läpi perusteellisesti. Kun se kulkee onnistuneesti alkuperäisen solmun läpi, käydään ja merkitään kaavion seuraava ylittämätön kärkipiste.
Siksi voit sanoa, että kaikki nykyisen kärjen vieressä olevat solmut vierailevat ja kulkevat ensimmäisessä iteraatiossa. BFS-algoritmin toiminnan toteuttamiseen käytetään yksinkertaista jonomenetelmää, ja se koostuu seuraavista vaiheista:
Vaihe 1)
Jokainen kaavion kärki tai solmu tunnetaan. Voit esimerkiksi merkitä solmun V: ksi.
Vaihe 2)
Jos kärkeen V ei pääse, lisää sitten kärki V BFS-jonoon
Vaihe 3)
Aloita BFS-haku ja merkitse kärkipiste V suoritettuasi sen käydyksi.
Vaihe 4)
BFS-jono ei ole vieläkään tyhjä, poista siis kaavion kärki V jonosta.
Vaihe 5)
Hae kaikki jäljellä olevat kaavion kärjet, jotka ovat vierekkäin kärjen V kanssa
Vaihe 6)
Sanotaan jokaiselle vierekkäiselle kärjelle V1, jos siinä ei vielä käy, lisää V1 BFS-jonoon
Vaihe 7)
BFS vierailee versiossa V1 ja merkitsee sen vierailuksi ja poistaa sen jonosta.
Esimerkki BFS-algoritmista
Vaihe 1)
Sinulla on kaavio seitsemästä luvusta, jotka vaihtelevat välillä 0-6.
Vaihe 2)
0 tai nolla on merkitty juurisolmuksi.
Vaihe 3)
0 on käynyt, merkitty ja lisätty jonotietorakenteeseen.
Vaihe 4)
Jäljellä olevissa 0 vierekkäisessä ja käymättömässä solmussa käydään, merkitään ja lisätään jonoon.
Vaihe 5)
Liikkuvia iteraatioita toistetaan, kunnes kaikissa solmuissa käydään.
BFS-algoritmin säännöt
Tässä on tärkeitä sääntöjä BFS-algoritmin käyttämiselle:
- BFS käyttää jonon (FIFO-First in First Out) tietorakennetta.
- Merkit minkä tahansa kaavion solmun juureksi ja aloitat tiedon kulkemisen siitä.
- BFS kulkee kaavion kaikki solmut ja pudottaa ne valmiiksi.
- BFS vierailee viereisessä vierailemattomassa solmussa, merkitsee sen valmiiksi ja lisää sen jonoon.
- Poistaa edellisen kärjen jonosta, jos vierekkäistä kärkeä ei löydy.
- BFS-algoritmi toistaa, kunnes kaikki kaavion pisteet kulkevat ja merkitään valmiiksi.
- BFS ei aiheuta silmukoita datan kulkiessa mistä tahansa solmusta.
BFS-algoritmin sovellukset
Katsotaanpa joitain tosielämän sovelluksia, joissa BFS-algoritmien toteutus voi olla erittäin tehokasta.
- Painottamattomat kaaviot: BFS-algoritmi voi helposti luoda lyhimmän polun ja pienimmän ulottuvuuspuun käydäksesi kaavion kaikissa pisteissä mahdollisimman lyhyessä ajassa suurella tarkkuudella.
- P2P-verkot: BFS voidaan toteuttaa paikantamaan kaikki lähimmät tai vierekkäiset solmut vertaisverkossa. Tämä löytää tarvittavat tiedot nopeammin.
- Verkkoindeksoijat: Hakukoneet tai indeksointirobotit voivat helposti luoda useita hakemistotasoja käyttämällä BFS: ää. BFS-toteutus alkaa lähteestä, joka on verkkosivu, ja sitten se vierailee kaikki kyseisen lähteen linkit.
- Navigointijärjestelmät: BFS voi auttaa löytämään kaikki vierekkäiset sijainnit pää- tai lähdekohdasta.
- Verkkolähetys: BFS-algoritmi ohjaa lähetettyä pakettia etsimään ja saavuttamaan kaikki solmut, joille se on osoitettu.
Yhteenveto
- Kaavion läpikäynti on ainutlaatuinen prosessi, joka vaatii algoritmin vierailemaan, tarkistamaan ja / tai päivittämään kaikki yksittäiset solut puumaisessa rakenteessa. BFS-algoritmi toimii samalla periaatteella.
- Algoritmista on hyötyä kaavion solmujen analysoimiseksi ja niiden läpi kulkevan lyhimmän polun rakentamiseksi.
- Algoritmi kulkee kuvaajan pienimmässä määrin iteraatioita ja mahdollisimman lyhyessä ajassa.
- BFS valitsee yhden solmun (alku- tai lähdekohdan) kaaviosta ja vierailee sitten kaikki valitun solmun vieressä olevat solmut. BFS käyttää näitä solmuja yksitellen.
- BFS sijoittaa vieraat ja merkityt tiedot jonoon. Jono toimii ensin ensin ulos -periaatteella. Siksi kaavioon ensin sijoitettu elementti poistetaan ensin ja tulostetaan sen seurauksena.
- BFS-algoritmi ei voi koskaan tarttua loputtomaan silmukkaan.
- Suuren tarkkuuden ja kestävän toteutuksen ansiosta BFS: ää käytetään useissa tosielämän ratkaisuissa, kuten P2P-verkoissa, Web-indeksoijissa ja verkkolähetyksissä.