Dybdeførstsøk

Dybdeførstsøk, ofte betegnet som dybde-først-søgning, er en algoritme til traversal af træer og grafer. Den undersøger så dybt som muligt langs hver gren, før den tilbagegår til forrige knudepunkt. Algoritmen kan implementeres rekursivt eller med en eksplicit stak.

Fra en startknude markeres denne som besøgt, og naboer besøges i en forhåndsbestemt orden. For hver nabo, der ikke er besøgt, fortsættes rekursivt eller ved at skubbe naboen på stakken. I grafmiljøer med cyklusser kræves en besøgsregistrering for at undgå uendelige løkker. I urettede grafer undgår man typisk at vende tilbage til den forrige knude ved at holde styr på besøgte knuder.

Kompleksitet og bemærkninger: Den kører i tidsmæssig kompleksitet O(V+E) og har pladsforbrug på O(V) i værste fald, eftersom stakken/rekurskallene kan indeholde alle knuderne. Den rekursive version kan føre til stackoverflow i meget dybe grafer; ofte anvendes en eksplicit stak i stedet.

Varianter og anvendelser: Varianter inkluderer dybdebegrænset DFS, der begrænser søgningen til en given dybde, og iterativ dybdeførst søgning (IDDFS), som kombinerer fordelene ved DFS og BFS ved at udføre flere DFS-lag med stigende dybde. DFS bruges til topologisk sortering i DAG’er og som grundlag for algoritmer til at finde stærkt koblede komponenter (såsom Tarjans algoritme). Den er også nyttig til sti- og forbindelsesundersøgelser, cyklusdetektion og udforskning af grafer i AI, spil og compiler-design.

Sammenlignet med breadth-first search finder DFS ofte hurtigt ud af dybere grene uden at garantere korteste sti, og kræver normalt mindre hukommelse i bestemte grafstrukturer, men kan i værste fald udvikle dybde, der kræver stor stak eller stak-lager.