Tietojenkäsittelytieteessä syvyyssuuntainen läpikäynti eli syvyyshaku (, DFS) on graafialgoritmi, joka etsii kaikki tietyn solmun kautta saavutettavat muut solmut. Syvyyssuuntaisella läpikäynnillä saadaan tietoa graafin rakenteesta; polunhakua varten parempi algoritmi on yleensä leveyssuuntainen läpikäynti.
Algoritmi
Syvyyssuuntainen läpikäynti voidaan ilmaista vapaamuotoisesti seuraavasti: Edetään aloitussolmusta lähtien mahdollisimman pitkälle. Peruutetaan, kunnes löytyy haara, jota ei ole käyty läpi. Edetään siitä lähtien mahdollisimman pitkälle... Toistetaan, kunnes kaikki aloitussolmusta saavutettavat solmut ovat käyty läpi. Jos halutaan käydä koko verkko läpi, niin lisäksi: Toistetaan algoritmia asettamalla yhä uudestaan aloitussolmuksi solmu, jota ei ole vielä käyty läpi.
Tietoa saadaan paljon irti seuraavalla toteutustavalla: Värjätään solmuja kolmella vaihtoehtoisella värillä (valkoinen, harmaa tai musta eli koskematon, edetty tai kokonaan läpikäyty). Lyödään solmuihin ”aikaleima”, ennen kuin solmuun edetään tai siitä peruutetaan pois. Tallennetaan polut merkitsemällä jokaiselle solmulle edeltäjä.
Syvyyssuuntainen läpikäynti on helpointa toteuttaa rekursiivisesti: Merkitään käsiteltävä solmu harmaalla värillä ja aikaleimalla. Kasvatetaan aikaa. Toistetaan algoritmi jokaiselle vierussolmulle. Nyt solmu käyty kokonaan läpikäyty. Värjätään käsiteltävä solmu mustaksi ja kasvatetaan aikaa.
Toteutus pseudokoodilla
aika: globaali muuttuja, joka kertoo montako kertaa yhteensä on edetty tai peruutettu
record solmu viereiset: solmusta on yhteys näihin solmuihin väri: VALKOINEN, HARMAA tai MUSTA (koskematon, edetty tai kokonaan läpikäyty) edeltäjä: edellinen solmu edetyllä polulla löydetty: aika, jolloin solmuun edettiin läpikäyty: aika, jolloin solmu oli kokonaan läpikäyty ja siitä peruutettiin pois end record
record verkko solmut: kaikki verkon solmut end record
function dfs(G: verkko) for each v in G.solmut v.väri := VALKOINEN v.edeltäjä := null aika := 0 for each v in G.solmut if v.väri = VALKOINEN vieraile(v)
function vieraile(u: solmu) u.väri := HARMAA aika := aika + 1 u.löydetty := aika for each v in u.viereiset if v.väri = VALKOINEN v.edeltäjä := u vieraile(v) u.väri := MUSTA aika := aika + 1 u.läpikäyty := aika
Lähteet
Kirjallisuutta
Luokka:Algoritmit