Çfarë është kërkimi në thellësi (DFS)?

Question

Accepted Answer

**DFS** eksploron një graf duke shkuar sa më thellë që mundëson përgjatë secilës degë përpara se të tërhiqet. Përdor një **stack** (shpesh stack-un e thirrjeve përmes rekursionit) dhe vizitues një rrugë të plotë përpara se të eksplorojë alternativat.

## Ideja

Nga një nyje, recursi në një fqinj të pavizituar, dhe vazhdo thellë; kur je bllokuar, tërhiqu dhe provo një degë tjetër.

## Shembull

```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 kundër DFS

| | BFS | DFS |
|---|-----|-----|
| Struktura | queue | stack / rekursion |
| Gjen | më të shkurtër (pa peshë) | çdo rrugë |
| Kujtesa | O(V) frontier | O(thellësi) |
| E mirë për | rrugë më të shkurtëra, nivele | cikle, topo sort, komponente |

## Kompleksiteti

- **Koha:** O(V + E). **Hapësira:** O(V) (thellësia rekursionit + vizituar).

## Grackët

Grafet e thellë mund të tejkalojnë stack-un e rekursionit — përdor një stack të qartë. Ndjek `visited` për të trajtuar ciklet.

## Pse është i rëndësishëm

DFS qëndron në themel të zbulimit të cikleve, renditjes topologjike, komponenteve të lidhura, dhe gjenerimit të labirinteve/rrugëve.

Eleganca e tij rekursive bën kodin e pemëve dhe grafeve të hollë.

Të dish kur thellësia-e-parë përfundimisht e kalon gjerësinë-e-parë është fluence bazë në algoritmet e grafeve.

	BFS	DFS
Struktura	queue	stack / rekursion
Gjen	më të shkurtër (pa peshë)	çdo rrugë
Kujtesa	O(V) frontier	O(thellësi)
E mirë për	rrugë më të shkurtëra, nivele	cikle, topo sort, komponente