Syvyyshaku (DFS)

Käy graafin läpi seuraamalla yhtä polkua niin syvälle kuin pääsee ja palaamalla sitten viimeisimpään haarautumaan. Näytön pino on juuri tämä polku.

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

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

pinossa
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 syklinen graafi. Jokainen katkoviivalla piirretty kaari johtaa takaisin solmuun, joka on jo pinossa tai valmis: se kaari sulkee syklin.

Miten se toimii

Syvyyshaku kutsuu itseään ensimmäiselle naapurille, jota se ei ole vielä nähnyt, sitten tämän ensimmäiselle uudelle naapurille ja niin edelleen. Kun solmulla ei ole enää uusia naapureita, sen kutsu päättyy, ja haku palaa askeleen taaksepäin kokeilemaan siellä seuraavaa naapuria. Avoimet kutsut muodostavat pinon, joka on aina polku aloitussolmusta nykyiseen solmuun. Solmun vieressä oleva luku kertoo, monentenako solmussa käytiin.

Milloin se on hyvä valinta

Käytä syvyyshakua, kun haluat selvittää, mihin ylipäätään pääsee, löytää syklejä, kulkea sokkelon läpi tai panna toisistaan riippuvat tehtävät järjestykseen. Lyhintä reittiä se ei löydä.