Syvyyssuuntainen läpikäynti

Wikipedia

Tietojenkäsittelytieteessä syvyyssuuntainen läpikäynti eli syvyysetsintä (engl. depth-first search, DFS) on graafialgoritmi, joka etsii kaikki solmusta saavutettavat solmut. Sen avulla saadaan tietoa graafin rakenteesta; polunhakua varten parempi algoritmi on yleensä leveyssuuntainen läpikäynti.

[muokkaa] 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.

aika: globaali muuttuja, joka kertoo montako kertaa yhteensä ollaan 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

[muokkaa] Lähteet

• Thomas Cormen, Charles Leiserson, Ronald Rivest ja Clifford Stein: 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. Viitattu 5. huhtikuuta 2007.