Djup-först-sökning

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2023-12) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

Djup-först-sökning (dfs) är en strategi för att traversera ett träd (en hierarkisk datastruktur där varje nod kan ha noll eller flera underordnade noder) där man följer varje gren i trädet till dess yttersta nod (dess löv) innan man backar upp i hierarkin och väljer nästa gren att undersöka.

I vilken ordning grenarna i trädet genomsöks definieras av implementationen. I bilden till höger kommer man med djup-först sökning från roten (nod 8) att i tur och ordning undersöka noderna enligt någon av följande ordningar:

• 8, 3, 1, 6, 4, 7, 10, 14, 13;
• 8, 10, 14, 13, 3, 1, 6, 4, 7;
• 8, 3, 6, 4, 7, 1, 10, 14, 13;
• osv

Strategin kan vara värdefull i många sammanhang och anledningen att välja den beror naturligtvis på vilken data som trädet organiserar. I till exempel ett beslutsträd (ett träd som spänner upp tänkbara konsekvenser av en serie beslut, t.ex. drag i ett schackparti eller en serie strategiska affärsbeslut) utforskar man med denna strategi den yttersta konsekvensen av en viss serie beslut innan man tittar på alternativa beslut. Med djup först sökning går det alltid att hitta ett per definition framgångsrikt resultat (till exempel vinst i ett schackparti) om ett sådant finns i trädet, men det finns ingen garanti för att hitta en optimal väg till detta resultat.

• Bredd-först sökning