Syvyyssuuntainen läpikäynti

Tietojenkäsittelytieteessä syvyyssuuntainen läpikäynti eli syvyyshaku (engl. depth-first search, 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

Syvyyssuuntaisen läpikäynnin järjestys puumaisessa graafissa

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

• Thomas Cormen, Charles Leiserson, Ronald Rivest ja Clifford Stein: ”22.3 Depth-first search”, Introduction to Algorithms – 2nd ed. s. 540–547. MIT Press ja McGraw-Hill, 2001. ISBN 0-262-03293-7
• Matti Luukkainen ja Matti Nykänen: 58131: Tietorakenteet: ”7.3.2 Syvyyssuuntainen läpikäynti” 8. tammikuuta 2007. Helsingin yliopisto. Arkistoitu 13.6.2007. Viitattu 5. huhtikuuta 2007.

Kirjallisuutta

• Ruohonen, Keijo: Graafiteoria. (Opintomoniste 136) Tampere: TTKK, 1990. ISBN 951-721-530-4