Kaj je iskanje v globino (DFS)?

Question

Accepted Answer

**DFS** raziskuje graf z gibanjem čim dlje po vsakem razvejanju, preden se vrne. Uporablja **sklad** (pogosto klic sklada prek rekurzije) in obišče polno pot pred raziskovanjem alternativ.

## Ideja

Iz vozlišča se rekurzivno potopi v neobiskanega soseda in nadaljuje globoko; ko je obtičan, se vrne in poskuša drugo vejo.

## Primer

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

| | BFS | DFS |
|---|-----|-----|
| Struktura | vrsta | sklad / rekurzija |
| Najde | najkrajšo (neuteženo) | katero koli pot |
| Pomnilnik | O(V) frontier | O(globina) |
| Dobro za | najkrajše poti, ravni | cikli, topo sort, komponente |

## Kompleksnost

- **Čas:** O(V + E). **Prostor:** O(V) (globina rekurzije + obiskano).

## Pasti

Gluboki grafi lahko prekoračijo sklad rekurzije — uporabi ekspliciten sklad. Spremljaj `visited` za obravnavo ciklov.

## Zakaj je to pomembno

DFS je osnova za detekcijo ciklov, topološko sortiranje, povezane komponente in generiranje labirintov/poti.

Njegova rekurzivna eleganca naredi kodo drevesa in grafa jedrnato.

Znati, kdaj je globina-prvo boljša od širina-prvo, je jedro znanja o grafnih algoritmih.

	BFS	DFS
Struktura	vrsta	sklad / rekurzija
Najde	najkrajšo (neuteženo)	katero koli pot
Pomnilnik	O(V) frontier	O(globina)
Dobro za	najkrajše poti, ravni	cikli, topo sort, komponente