Τι είναι η αναζήτηση κατά βάθος (DFS);

Question

Accepted Answer

**DFS** εξερευνά ένα γράφημα πηγαίνοντας όσο πιο βαθιά γίνεται σε κάθε κλάδο πριν οπισθοχωρήσει. Χρησιμοποιεί μια **stack** (συχνά την stack κλήσης μέσω αναδρομής) και επισκέπτεται μια πλήρη διαδρομή πριν εξερευνήσει εναλλακτικές λύσεις.

## Η ιδέα

Από έναν κόμβο, κάνε αναδρομή σε έναν ανεπίσκεπτο γείτονα και συνέχισε να πηγαίνεις βαθιά· όταν κολλήσεις, οπισθοχώρησε και δοκίμασε έναν άλλο κλάδο.

## Παράδειγμα

```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 |
|---|-----|-----|
| Structure | queue | stack / recursion |
| Finds | shortest (unweighted) | any path |
| Memory | O(V) frontier | O(depth) |
| Good for | shortest paths, levels | cycles, topo sort, components |

## Πολυπλοκότητα

- **Χρόνος:** O(V + E). **Χώρος:** O(V) (βάθος αναδρομής + επισκέψεις).

## Παγίδες

Τα βαθιά γραφήματα μπορούν να υπερχειλίσουν την stack αναδρομής — χρησιμοποίησε μια ρητή stack. Παρακολούθησε το `visited` για να χειριστείς τους κύκλους.

## Γιατί έχει σημασία

Το DFS είναι η βάση της ανίχνευσης κύκλων, της τοπολογικής ταξινόμησης, των συνδεδεμένων συνιστωσών και της δημιουργίας λαβυρίνθων/διαδρομών.

Η αναδρομική του κομψότητα κάνει τον κώδικα δέντρων και γραφημάτων συνοπτικό.

Το να γνωρίζεις πότε η depth-first είναι καλύτερη από την breadth-first είναι βασική γραμματεία αλγορίθμων γραφημάτων.

	BFS	DFS
Structure	queue	stack / recursion
Finds	shortest (unweighted)	any path
Memory	O(V) frontier	O(depth)
Good for	shortest paths, levels	cycles, topo sort, components