dybdeførstsøgning

Dybdeførstsøgning, ofte kendt som depth-first search (DFS), er en graf- og trætraverseringsalgoritme, der udforsker så langt som muligt langs en gren, før den backtracker. Algoritmen kan anvendes på både træer og generelle grafer og undersøger ruten ved at gå dybt i en retning, indtil der ikke er flere naboer at udforske.

I praksis bruges typisk rekursion eller en eksplicit stak til at holde styr på ruten. Ved hvert besøg af en node gennemgås dens naboer i vilkårlig rækkefølge, og allerede besøgte noder markeres for at undgå gentagelse. For en fuld traversal i en graf skal algoritmen køres fra hver uafhængig komponent.

Kompleksitet: Tid O(V+E) ved brug af en adjacensliste; plads O(V) i det værste tilfælde. DFS bruges til topologisk sortering, cyklusdetektion i rettede grafer, og til at finde stærkt sammenkoblede komponenter ved hjælp af Kosarajus eller Tarjanns algoritmer. Den er også central i forskellige søge- og analyseopgaver som labyrintløsning og visse pathfinding-tilgange.

Fordele og ulemper: DFS kræver ikke nødvendigvis de korteste ruter og kan være mere hukommelseskrævende i dybt forgrenede grafer. Rekursiv implementering kan føre til stack-overflow på meget dybe træer eller grafer; iterative versioner med en stak kan afhjælpe dette.

Historie: Dybdeførstsøgning er en grundlæggende graftraversalgoritme og har spillet en central rolle i grafteori og computer science siden midten af det 20. århundrede.