Što je pretraga u dubinu (DFS)?

Question

Accepted Answer

**DFS** istražuje graf ideći što je dublje moguće duž svanog grana prije nego što se vrati unazad. Koristi **stack** (često pozivni stack putem rekurzije) i posjećuje cijelu stazu prije nego što istražuje alternative.

## Ideja

Iz čvora, rekurzirajte u neposjetanu susjednu čvornu, i nastavite duboko; kada se zapnete, vratite se i pokušajte drugu granu.

## Primjer

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

| | BFS | DFS |
|---|-----|-----|
| Struktura | queue | stack / recursion |
| Pronalazi | najkraće (neponderisano) | bilo koju stazu |
| Memorija | O(V) frontier | O(depth) |
| Dobra je za | najkraće staze, nivoe | cikluse, topo sortiranje, komponente |

## Složenost

- **Vrijeme:** O(V + E). **Prostor:** O(V) (dubina rekurzije + posjetano).

## Zamke

Guboke grafe mogu prebrisati stack rekurzije — koristite eksplicitan stack. Pratite `visited` za rukovanje ciklima.

## Zašto je važno

DFS je temelj detekcije ciklusa, topološkog sortiranja, povezanih komponenti i generisanja labirinta/staze.

Njegova rekurzivna elegancija čini kod stabla i grafa sažetim.

Znati kada depth-first nadmašuje breadth-first jest osnovna fluencom u algoritmima grafa.

	BFS	DFS
Struktura	queue	stack / recursion
Pronalazi	najkraće (neponderisano)	bilo koju stazu
Memorija	O(V) frontier	O(depth)
Dobra je za	najkraće staze, nivoe	cikluse, topo sortiranje, komponente