რა არის სიღრმის ძიება (DFS)?

Question

Accepted Answer

**DFS** გამოიკვლევს გრაფს თითოეული ტოტის გასწვრივ რაც შეიძლება ღრმად წასვლით, სანამ უკან დაბრუნდება. ის იყენებს **სტეკს** (ხშირად ზარის სტეკს რეკურსიის მეშვეობით) და ეწვევა სრულ ბილიკს სანამ ალტერნატივებს შეისწავლის.

## იდეა

კვანძიდან რეკურსიით შემოდგომილი მეზობელში შესვლა, და ღრმად წასვლის გაგრძელება; როდესაც გარბილია, უკან დაბრუნება და სხვა ტოტის ცდა.

## მაგალითი

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

| | BFS | DFS |
|---|-----|-----|
| სტრუქტურა | რიგი | სტეკი / რეკურსია |
| პოულობს | უმოკლეს (წონითი) | ნებისმიერი ბილიკი |
| მეხსიერება | O(V) საზღვარი | O(სიღრმე) |
| კარგია | უმოკლეს ბილიკებისთვის, დონეებისთვის | ციკლებისთვის, ტოპო დალაგებისთვის, კომპონენტებისთვის |

## სირთულე

- **დრო:** O(V + E). **მეხსიერება:** O(V) (რეკურსიის სიღრმე + ნახული).

## ხარვეზები

ღრმა გრაფები შეიძლება გადაჭიმოს რეკურსიის სტეკს — გამოიყენეთ აშკარა სტეკი. თვალი ადევნეთ `visited`-ს ციკლების დასამუშავებლად.

## რატომ მნიშვნელოვანია

DFS ემყარება ციკლის დეტექციას, ტოპოლოგიურ დალაგებას, დაკავშირებული კომპონენტებს, და ლაბირინთის/ბილიკის გენერირებას.

მისი რეკურსიული ელეგანტურობა ხეების და გრაფების კოდს მოკლებულს ხდის.

ის ცოდნა, როდის აჯობებს სიღრმის ძიება სიბრტყის ძიებას, გრაფიკული ალგორითმის სიცოცხლის ქვაკვა.

	BFS	DFS
სტრუქტურა	რიგი	სტეკი / რეკურსია
პოულობს	უმოკლეს (წონითი)	ნებისმიერი ბილიკი
მეხსიერება	O(V) საზღვარი	O(სიღრმე)
კარგია	უმოკლეს ბილიკებისთვის, დონეებისთვის	ციკლებისთვის, ტოპო დალაგებისთვის, კომპონენტებისთვის