Leveyshaku (BFS)

Käy graafin läpi kerros kerrallaan. Jono päättää, mikä solmu on seuraavana, joten lähimmissä solmuissa käydään aina ensin.

aika O(V + E)
tila O(V)
käyttää jonoa

Mitä nämä tarkoittavat?

Solmu: graafin piste, tässä piirretty ympyränä, jossa on kirjain.
Kaari: viiva, joka yhdistää kaksi solmua. Tässä sitä pitkin voi kulkea kumpaankin suuntaan.
Naapurit: solmut, jotka on yhdistetty solmuun kaarella. Niitä tarkastellaan aakkosjärjestyksessä.
Jono: ensimmäisenä sisään, ensimmäisenä ulos. BFS ottaa aina solmun, joka on odottanut pisimpään.
Pino: viimeisenä sisään, ensimmäisenä ulos. DFS jatkaa aina solmusta, johon se pääsi viimeksi.
V ja E: solmujen (vertices) ja kaarten (edges) määrä. O(V + E) tarkoittaa, että jokainen solmu ja jokainen kaari käsitellään kiinteän määrän kertoja.

0 / 60 askelta

jonossa
nykyinen
valmis
hakupuun kaari
ohitettu kaari

Nopeus 8 askelta/s

Välilyönti: toisto tai tauko. Nuolinäppäimet: askel. Home ja End: alkuun tai loppuun.

Kokeile tätä: Valitse graafi, jossa on kaksi osaa. Solmuihin, joita ei ole yhdistetty aloitussolmuun, ei päästä koskaan.

Miten se toimii

Leveyshaku laittaa aloitussolmun jonoon. Sitten se ottaa yhä uudelleen jonon ensimmäisen solmun ja lisää sen uudet naapurit jonon loppuun. Jono palvelee saapumisjärjestyksessä, joten kaikki yhden kaaren päässä olevat solmut ovat valmiita ennen kuin yhdenkään kahden kaaren päässä olevan solmun vuoro tulee. Solmun vieressä oleva luku on sen etäisyys aloitussolmusta: pienin määrä kaaria, joita pitkin sinne pääsee.

Milloin se on hyvä valinta

Käytä leveyshakua, kun tarvitset lyhimmän reitin askelina: vähiten siirtoja pulmassa, vähiten hyppyjä verkossa, ihmiset kahden tuttavuuden päässä sinusta. Suuressa graafissa jono voi kasvaa pitkäksi, koska siinä on kokonainen kerros kerralla.