Dybde-først-søk (DFS) er en søkealgoritme for grafer som prioriterer å gå nedover i grafen så langt råden er før den prøver andre stier. Når en kommer til en løvnode eller det ikke finns flere etterkommere å prøve, går en tilbake til forrige node for å prøve og finne neste etterkommere. Dette gjentas til løsningen er nådd eller når det er ingen flere stier å prøve.
Virkemåte Søkefronten (frontier) er en liste av alle stier. I et dybde-først-søk, fungerer søkefronten som en LIFO (last-in first-out) stabel (stack) av stier. I en stabel blir elementene lagt til og fjernet fra toppen av stabelen.
Egenskaper Algoritmen spesifiserer ikke rekkefølgen av stiene til naboene som legges til i Frontier. Ofte finner ikke optimale løsningen. Trenger minne proporsjonalt med lengde på stien en holde på å undersøke. Trenger tid proporsjonalt med tall på noder i søkerommet.
Referanser
Kategori:Søkealgoritmer