Cad é an cuardach domhain-tosaigh (DFS)?

Question

Accepted Answer

**DFS** a dhéanann iniúchadh ar ghraf trí dul chomh domhain is féidir ar feadh gach brainse sula ndéantar filleadh. Úsáideann sé **stack** (go minic an call stack trí athchúrsáil) agus cuairt ar fhull-chonair a bhaint amach sula ndeirtear naisc eile.

## An smaoineamh

Ó nód, athchúrsaigh i gcomharsanach neamhthaidhsithe, agus coinnigh ag dul domhain; nuair a bhíonn tú i bhfolach, téigh ar ais agus bain triail as brainse eile.

## Sampla

```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 i gcoinne DFS

| | BFS | DFS |
|---|-----|-----|
| Struchtúr | queue | stack / recursion |
| Aimsíonn | is gearr (gan bhreith) | aon chonair |
| Cuimhne | O(V) frontier | O(depth) |
| Dea do | cosáin is giorra, leibhéil | timthriallta, sórt topo, comhpháirteanna |

## Castacht

- **Am:** O(V + E). **Spás:** O(V) (doimhneacht athchúrsáil + cuairte).

## Gealadh

Is féidir le ghraif dhomhain an stack athchúrsáil a shéideadh — úsáid stack follasach. Rianúil a dhéanamh ar `visited` chun timthriallta a láimhseáil.

## Cén fáth a bhfuil sé tábhachtach

Tá DFS mar bhunús do bhrath timthriallta, sórt topo, comhpháirteanna fhoscailte, agus giniúint dhúnmharc/chosáin.

A ghealadh athchúrsála a dhéanann cód crainn agus ghraf geal.

A bheith ar eolas nuair a bhíonn doimhneacht-tosaigh níos fearr ná leithead-tosaigh ná scil bhunúsach i algartam ghraf.

	BFS	DFS
Struchtúr	queue	stack / recursion
Aimsíonn	is gearr (gan bhreith)	aon chonair
Cuimhne	O(V) frontier	O(depth)
Dea do	cosáin is giorra, leibhéil	timthriallta, sórt topo, comhpháirteanna