Syvyyssuuntainen läpikäynti
Wikipedia
Tietojenkäsittelytieteessä syvyyssuuntainen läpikäynti eli syvyysetsintä (engl. depth-first search, DFS) on verkkoalgoritmi, joka etsii kaikki solmusta saavutettavat solmut. Sen avulla saadaan tietoa verkon 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 (2001): Introduction to Algorithms – 2nd ed., s. 540–547. MIT Press ja McGraw-Hill. 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. Luettu 5. huhtikuuta 2007.
