Kas yra giluminis paieška (DFS)?

Question

Accepted Answer

**DFS** tyrinėja grafą einant kuo giliau kiekviena šaka, kol grįžtama atgal. Jis naudoja **steką** (dažnai rekursijos steką) ir aplanko visą kelią prieš tyrinėdamas alternatyvas.

## Idėja

Iš mazgo rekursyviai eina į neaplankytą kaimyną ir tęsia gilumoje; kai застревает, grįžta atgal ir bando kitą šaką.

## Pavyzdys

```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 ir DFS palyginimas

| | BFS | DFS |
|---|-----|-----|
| Struktūra | eilė | stekas / rekursija |
| Randa | trumpiausias (nesusvorio) | bet kokį kelią |
| Atmintis | O(V) frontas | O(gylis) |
| Tinka | trumpiausi keliai, lygiai | ciklai, topologinis rūšiavimas, komponentai |

## Sudėtingumas

- **Laikas:** O(V + E). **Atmintis:** O(V) (rekursijos gylis + aplankyti).

## Spąstai

Gilūs grafai gali perpildyti rekursijos steką — naudokite eksplicitinį steką. Sekite `visited`, kad tvarkyti ciklus.

## Kodėl tai svarbu

DFS yra ciklo aptikimo, topologinio rūšiavimo, sujungtų komponentų ir dėdės/kelio generavimo pagrindas.

Jo rekursyvinis elegancingumas daro medžio ir grafo kodą glustą.

Žinojimas, kada giluminis paieška nugali platumės paiešką, yra esminė grafo algoritmų žinojimas.

	BFS	DFS
Struktūra	eilė	stekas / rekursija
Randa	trumpiausias (nesusvorio)	bet kokį kelią
Atmintis	O(V) frontas	O(gylis)
Tinka	trumpiausi keliai, lygiai	ciklai, topologinis rūšiavimas, komponentai