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.
- O(V + E)
- tila O(V)
- pino
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.
Pino: viimeisenä sisään, ensimmäisenä ulos. DFS jatkaa aina solmusta, johon se pääsi viimeksi.
Muut tämän sivun käsitteet
- 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ä.
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ä.