Vad är djupet-först-sökning (DFS)?

Question

Accepted Answer

**DFS** utforskar en graf genom att gå så långt som möjligt längs varje gren innan du backtrackar. Den använder en **stack** (ofta call-stacken via rekursion) och besöker en full väg innan den utforskar alternativ.

## Idén

Från en nod, rekursera in i en obesökt granne, och fortsätt djupt; när du är fast, backa upp och prova en annan gren.

## Exempel

```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 mot DFS

| | BFS | DFS |
|---|-----|-----|
| Struktur | kö | stack / rekursion |
| Hittar | kortaste (oviktat) | vilken väg som helst |
| Minne | O(V) frontier | O(djup) |
| Bra för | kortaste vägar, nivåer | cykler, topo sort, komponenter |

## Komplexitet

- **Tid:** O(V + E). **Rum:** O(V) (rekursionsdjup + besökt).

## Fallgropar

Djupa grafer kan överskrida rekursionsstacken — använd en explicit stack. Spåra `visited` för att hantera cykler.

## Varför det spelar roll

DFS ligger till grund för cykeldetektering, topologisk sortering, sammanhängande komponenter och labyrint-/väggenerering.

Dess rekursiva elegans gör kod för träd och grafer koncis.

Att veta när djupet-först slår breddets-först är kärnkompetens i grafalgoritmer.

	BFS	DFS
Struktur	kö	stack / rekursion
Hittar	kortaste (oviktat)	vilken väg som helst
Minne	O(V) frontier	O(djup)
Bra för	kortaste vägar, nivåer	cykler, topo sort, komponenter