Hva er dybde-først søk (DFS)?

Question

Accepted Answer

**DFS** utforsker en graf ved å gå så dypt som mulig langs hver gren før du går tilbake. Den bruker en **stack** (ofte call stack via rekursjon) og besøker en full sti før den utforsker alternativer.

## Ideen

Fra en node, rekurser inn i en ubesøkt nabo, og hold deg dypt; når du sitter fast, gå tilbake og prøv en annen 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 versus DFS

| | BFS | DFS |
|---|-----|-----|
| Struktur | queue | stack / rekursjon |
| Finner | korteste (uvektet) | hvilken som helst sti |
| Minne | O(V) grense | O(dybde) |
| Bra for | korteste stier, nivåer | sykler, topo sort, komponenter |

## Kompleksitet

- **Tid:** O(V + E). **Plass:** O(V) (rekursjonsdybde + besøkt).

## Fallgruver

Dype grafer kan forårsake rekursjonsstabel-overflyt — bruk en eksplisitt stack. Spor `visited` for å håndtere sykler.

## Hvorfor det er viktig

DFS underbygger syklusdeteksjon, topologisk sortering, tilkoblede komponenter og labyrint-/veiGenerering.

Its rekursive eleganse gjør tre- og grafkode konsise.

Å vite når dybde-først slår bredde-først er kjernekompetanse i grafalgoritmer.

	BFS	DFS
Struktur	queue	stack / rekursjon
Finner	korteste (uvektet)	hvilken som helst sti
Minne	O(V) grense	O(dybde)
Bra for	korteste stier, nivåer	sykler, topo sort, komponenter