Hvad er dybde-først-søgning (DFS)?

Question

Accepted Answer

**DFS** udforsker en graf ved at gå så dybt som muligt langs hver gren, før den går tilbage. Den bruger en **stak** (ofte kaldestakken via rekursion) og besøger en fuld sti, før den udforsker alternativer.

## Grundidéen

Fra en knude, rekursivt ind i en ubesøgt nabo, og fortsæt dybt; når du er fast, gå tilbage og prøv en anden gren.

## Eksempel

```python
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    order = [node]
    for nbr in graph[node]:
        if nbr not in visited:
            order += dfs(graph, nbr, visited)  # go deeper first
    return order

graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
dfs(graph, 'A')                        # -> ['A', 'B', 'D', 'C']
```

## BFS vs DFS

| | BFS | DFS |
|---|-----|-----|
| Struktur | kø | stak / rekursion |
| Finder | korteste (uvægtet) | vilkårlig sti |
| Hukommelse | O(V) grænse | O(dybde) |
| Egnet til | korteste stier, niveauer | cyklusser, topologisk sortering, komponenter |

## Kompleksitet

- **Tid:** O(V + E). **Plads:** O(V) (rekursionsdybde + besøgt).

## Faldgruber

Dybe grafer kan forårsage stakoverflow i rekursion — brug en eksplicit stak. Spor `visited` for at håndtere cyklusser.

## Hvorfor det betyder noget

DFS ligger til grund for cyklusdetektion, topologisk sortering, forbundne komponenter og labyrinth-/stivejgenerering.

Its rekursive elegance gør træ- og grafkode kortfattet.

At vide, hvornår dybde-først slår bredde-først, er kernekompetence inden for grafalgoritmer.

	BFS	DFS
Struktur	kø	stak / rekursion
Finder	korteste (uvægtet)	vilkårlig sti
Hukommelse	O(V) grænse	O(dybde)
Egnet til	korteste stier, niveauer	cyklusser, topologisk sortering, komponenter