Syvyyssuuntainen läpikäynti

Wikipedia
Loikkaa: valikkoon, hakuun

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.

Algoritmi[muokkaa | muokkaa wikitekstiä]

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

Lähteet[muokkaa | muokkaa wikitekstiä]

  • 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.