Breadth First Search (BFS) -algoritmi ja EXAMPLE

Mikä on BFS-algoritmi (Breadth-First Search)?

Breadth-first search (BFS) on algoritmi, jota käytetään datan kuvaamiseen tai puuhakuun tai rakenteiden läpikulkuun. BFS:n täysi muoto on Breadth-first-haku.

Algoritmi vierailee ja merkitsee tehokkaasti kaikki graafin avainsolmut tarkasti leveyssuunnassa. Tämä algoritmi valitsee yhden solmun (alku- tai lähdepisteen) kaaviosta ja vierailee sitten kaikissa valitun solmun vieressä olevissa solmuissa. Muista, että BFS käyttää näitä solmuja yksitellen.

Kun algoritmi vierailee ja merkitsee aloitussolmun, se siirtyy kohti lähimpiä vierailemattomia solmuja ja analysoi ne. Kun olet käynyt, kaikki solmut on merkitty. Nämä iteraatiot jatkuvat, kunnes kaikki kaavion solmut on käyty ja merkitty onnistuneesti.

Mikä on graafin läpikulku?

Graafin läpikulku on yleisesti käytetty menetelmä graafin kärjen sijainnin paikantamiseksi. Se on edistynyt hakualgoritmi, joka voi analysoida kuvaajaa nopeasti ja tarkasti sekä merkitä vierailtujen kärkien sekvenssin. Tämän prosessin avulla voit vierailla nopeasti kaavion jokaisessa solmussa ilman, että olet lukittuna äärettömään silmukkaan.

BFS-algoritmin arkkitehtuuri

1. Tietojen eri tasoilla voit merkitä minkä tahansa solmun aloitussolmuksi tai aloitussolmuksi siirtymisen aloittamiseksi. BFS vierailee solmussa ja merkitsee sen vierailluksi ja sijoittaa sen jonoon.
2. Nyt BFS vierailee lähimmissä ja vierailemattomissa solmuissa ja merkitsee ne. Nämä arvot lisätään myös jonoon. Jono toimii FIFO malli.
3. Samalla tavalla kaavion jäljellä olevat lähimmät ja vierailemattomat solmut analysoidaan merkittyinä ja lisätään jonoon. Nämä kohteet poistetaan jonosta vastaanotettaessa ja tulostetaan tuloksena.

Miksi tarvitsemme BFS-algoritmia?

On monia syitä käyttää BFS-algoritmia tietojoukon etsimiseen. Jotkut tärkeimmistä seikoista, jotka tekevät tästä algoritmista ensimmäisen valintasi, ovat:

• BFS on hyödyllinen graafin solmujen analysoinnissa ja lyhimmän reitin muodostamisessa niiden läpi kulkemiseen.
• BFS voi kulkea kuvaajan läpi pienimmällä määrällä iteraatioita.
• BFS-algoritmin arkkitehtuuri on yksinkertainen ja vankka.
• BFS-algoritmin tuloksella on korkea tarkkuustaso muihin algoritmeihin verrattuna.
• BFS-iteraatiot ovat saumattomia, eikä ole mahdollista, että tämä algoritmi joutuisi äärettömän silmukan ongelmaan.

Kuinka BFS-algoritmi toimii?

Graafin läpikulku edellyttää, että algoritmi vierailee, tarkastaa ja/tai päivittää jokaisen yksittäisen solmun, jossa ei ole käynyt puumaisessa rakenteessa. Kaavion läpikäymiset luokitellaan sen järjestyksen mukaan, jossa ne käyvät kaavion solmuissa.

BFS-algoritmi aloittaa toiminnan graafin ensimmäisestä eli aloitussolmusta ja kulkee sen läpi perusteellisesti. Kun se kulkee onnistuneesti alkuperäisen solmun läpi, graafin seuraava ei-kuljettu kärkipiste käydään ja merkitään.

Tästä syystä voidaan sanoa, että kaikissa nykyisen kärjen viereisissä solmuissa käydään ja ne kuljetetaan ensimmäisessä iteraatiossa. BFS-algoritmin toiminnan toteuttamiseen käytetään yksinkertaista jonometodologiaa, joka koostuu seuraavista vaiheista:

Vaihe 1)

Jokainen graafin kärki tai solmu tunnetaan. Voit esimerkiksi merkitä solmun V:ksi.

Vaihe 2)

Jos kärkeen V ei päästä, lisää kärki V BFS-jonoon

Vaihe 3)

Aloita BFS-haku ja sen jälkeen merkitse kärkipiste V käydyksi.

Vaihe 4)

BFS-jono ei vieläkään ole tyhjä, joten poista graafin kärki V jonosta.

Vaihe 5)

Hae kaikki jäljellä olevat graafin kärjet, jotka ovat kärjen V vieressä

Vaihe 6)

Oletetaan jokaiselle viereiselle kärjelle V1, jos siinä ei ole vielä vieraillut, lisää V1 BFS-jonoon

Vaihe 7)

BFS vierailee V1:ssä ja merkitsee sen vierailluksi ja poistaa sen jonosta.

Esimerkki BFS-algoritmista

Vaihe 1)

Sinulla on kaavio, jossa on seitsemän numeroa välillä 0–6.

Vaihe 2)

0 tai nolla on merkitty juurisolmuksi.

Vaihe 3)

0 käy, merkitään ja lisätään jonotietorakenteeseen.

Vaihe 4)

Loput 0 vierekkäistä ja vierailematonta solmua käydään, merkitään ja lisätään jonoon.

Vaihe 5)

Ajoiteraatioita toistetaan, kunnes kaikki solmut on käyty.

BFS-algoritmin säännöt

Tässä on tärkeitä BFS-algoritmin käyttöä koskevia sääntöjä:

• Jono (FIFO-First in First Out) tietorakenne on BFS:n käytössä.
• Merkitset minkä tahansa kaavion solmun juuriksi ja alat kulkea siitä dataa.
• BFS kulkee kaavion kaikkien solmujen läpi ja pudottaa ne aina valmiina.
• BFS vierailee viereisessä vierailemattomassa solmussa, merkitsee sen valmiiksi ja lisää sen jonoon.
• Poistaa edellisen kärjen jonosta, jos viereistä kärkeä ei löydy.
• BFS-algoritmi iteroi, kunnes kaikki graafin kärjet on kulkenut onnistuneesti ja merkitty valmiiksi.
• BFS ei aiheuta silmukoita datan kulkiessa mistään solmusta.

BFS-algoritmin sovellukset

Katsotaanpa joitain tosielämän sovelluksia, joissa BFS-algoritmin toteutus voi olla erittäin tehokas.

• Painottamattomat kaaviot: BFS-algoritmi voi helposti luoda lyhimmän polun ja vähimmäisvirittävän puun vieraillakseen graafin kaikissa pisteissä mahdollisimman lyhyessä ajassa suurella tarkkuudella.
• P2P-verkot: BFS voidaan toteuttaa paikantamaan kaikki lähimmät tai viereiset solmut vertaisverkossa. Tämä löytää tarvittavat tiedot nopeammin.
• Verkkoindeksointirobotit: Hakukoneet tai indeksointirobotit voivat helposti rakentaa useita indeksitasoja käyttämällä BFS:ää. BFS-toteutus alkaa lähteestä, joka on verkkosivu, ja sitten se vierailee kaikissa linkeissä kyseisestä lähteestä.
• Navigointijärjestelmät: BFS voi auttaa löytämään kaikki naapuripaikat pää- tai lähdesijainnista.
• Verkkolähetys: BFS-algoritmi ohjaa lähetettyä pakettia etsimään ja saavuttamaan kaikki solmut, joille sillä on osoite.

Yhteenveto

• Kuvaajan läpikäynti on ainutlaatuinen prosessi, joka vaatii algoritmin käymään, tarkistamaan ja/tai päivittämään jokaisessa puumaisen rakenteen solmussa, jossa ei ole käyty. BFS-algoritmi toimii samalla periaatteella.
• Algoritmi on hyödyllinen graafin solmujen analysointiin ja lyhimmän polun rakentamiseen niiden läpi kulkemiseen.
• Algoritmi kulkee kuvaajan läpi mahdollisimman pienessä määrässä iteraatioita ja mahdollisimman lyhyessä ajassa.
• BFS valitsee yhden solmun (alkupisteen tai lähdepisteen) kaaviosta ja vierailee sitten kaikissa valitun solmun vieressä olevissa solmuissa. BFS käyttää näitä solmuja yksitellen.
• Vierailtu ja merkityt tiedot asetetaan jonoon BFS:llä. Jono toimii ensin ensimmäiseksi ulos -periaatteella. Tästä syystä kaavioon ensin sijoitettu elementti poistetaan ensin ja tulostetaan sen seurauksena.
• BFS-algoritmi ei voi koskaan jäädä äärettömään silmukkaan.
• Suuren tarkkuuden ja vankan toteutuksen ansiosta BFS:ää käytetään useissa tosielämän ratkaisuissa, kuten P2P-verkoissa, Web-indeksointiroboteissa ja verkkolähetyksessä.