Syvyyssuuntainen läpikäynti

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