Dybde-først søgning

Til gennemløb af samtlige forgreningspunkter og blade i en datastruktur, formet som et træ, kan anvendes flere metoder. En søgning, der har til formål at findes et blad (målet), som opfylder visse kriterier, starter altid i træets rod. Søgningen standser, når det første blad nås, som er anvendeligt (der kunne være flere blade, som tilfredsstiller kriterierne). Hvis bladet ikke tilfredsstiller kriterierne, skal man tilbage til det sidste forgreningspunkt (back-tracking) og fortsætte søgningen ad en anden gren.

Besøges knudepunkterne, således at en bestemt gren følges til sit yderste blad, før den næste forgrening besøges, kaldes metoden dybde-først. Denne søgeteknik anvendes bl.a. i ekspertsystemer. Den anden metode, bredde-først søgeteknikken, undersøger træet niveau efter niveau, til et brugbart blad er fundet. Denne teknik er mere fleksibel, men kan kræve megen lagerplads. De to teknikker kan kombineres.

Fordelen ved dybde-først er, at altid kun én serie af forgreningspunkter skal huskes, dvs. metoden sparer lager i forhold til bredde-først søgetekniken. Ulempen ved dybde-først søgetekniken er, at man kan fortabe sig i en ørkesløs søgning i en meget lang gren i søgetræet, selvom målet kunne nås ad en kort nabogren.

Metoderne finder også anvendelse på grafer (en generalisering af træer). Her er problemet, at cykler i grafen kan bevirke at søgningen aldrig stopper, men kører uendeligt i ring.