Breadth First Search (BFS) -algoritmi ja EXAMPLE

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

Leveyshaku (BFS) on algoritmi, jota käytetään datan graafiseen piirtämiseen, puun etsimiseen tai rakenteiden läpikäymiseen. BFS:n täydellinen muoto on leveyshaku.

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. Datan eri tasoilla voit merkitä minkä tahansa solmun aloitus- tai alkusolmuksi läpikulun aloittamiseksi. BFS vierailee solmussa, merkitsee sen vierailluksi ja asettaa sen jonoon.
2. Nyt BFS käy lähimmissä ja vierailemattomissa solmuissa ja merkitsee ne. Nämä arvot lisätään myös jonoon. Jono toimii FIFO malli.
3. Samalla tavalla graafin jäljellä olevat lähimmät ja vierailemattomat solmut analysoidaan, merkitään ja lisätään jonoon. Nämä kohteet poistetaan jonosta sitä mukaa, kun ne vastaanotetaan ja tulostetaan tuloksena.

Miksi tarvitsemme BFS-algoritmia?

BFS-algoritmin käyttöön datajoukon hakemiseen on useita syitä. Joitakin tärkeimpiä tekijöitä, jotka tekevät tästä algoritmista ensisijaisen 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.

Voidaan siis sanoa, että kaikki nykyisen kärjen vieressä olevat solmut käydään läpi ja niiden läpi ensimmäisessä iteraatiossa. BFS-algoritmin toiminnan toteuttamiseen käytetään yksinkertaista jonomenetelmää, ja se koostuu seuraavista vaiheista:

Vaihe 1)

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

Vaihe 2)

Jos solmua V ei käytetä, lisää solmu V BFS-jonoon.

Vaihe 3)

Aloita BFS-haku ja merkitse sen valmistuttua piste V vierailluksi.

Vaihe 4)

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

Vaihe 5)

Hae graafista kaikki jäljellä olevat solmut, jotka ovat solmun V vieressä.

Vaihe 6)

Jokaiselle vierekkäiselle solmulle, sanotaan V1, jos sitä ei ole vielä vierailtu, lisätään V1 BFS-jonoon.

Vaihe 7)

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

Esimerkki BFS-algoritmista

Vaihe 1)

Sinulla on seitsemän luvun kuvaaja väliltä 0-6.

Vaihe 2)

0 tai nolla on merkitty juurisolmuksi.

Vaihe 3)

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

Vaihe 4)

Jäljelle jäävät 0:n vierekkäiset ja vierailemattomat solmut vieraillaan, 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ä sääntöjä BFS-algoritmin käyttöön:

• Jono (FIFO – First In First Out) tietorakenne on BFS:n käytössä.
• Merkitset minkä tahansa graafin solmun juureksi ja alat käydä läpi dataa siitä.
• BFS käy läpi kaikki graafin solmut ja pitää pudotuksenping ne valmiiksi tehtyinä.
• BFS vierailee viereisessä vierailemattomassa solmussa, merkitsee sen valmiiksi ja lisää sen jonoon.
• Se poistaa edellisen kärkipisteen jonosta, jos viereistä kärkipistettä ei löydy.
• BFS-algoritmi iteroi, kunnes kaikki graafin kärkipisteet on käyty läpi onnistuneesti ja merkitty suoritetuiksi.
• 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 pienimmän virittäväpuun käydäkseen kaikissa graafin kärjissä mahdollisimman lyhyessä ajassa ja suurella tarkkuudella.
• P2P-verkot: BFS voidaan toteuttaa paikantamaan kaikki lähimmät tai naapurisolmut 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.

UKK