Input/output di larghezza-prima vs. prima ricerca

Question

La mia domanda non riguarda davvero il meccanismo di entrambi i tipi di ricerca. Sento che è molto più banale di così: non capisco l'ingresso e l'output di nessuno dei due. Più specificamente, in CLRS, BFS prende come ingresso un grafico e un nodo di origine, ma DFS prende solo un grafico. DFS non si preoccupa da dove cerchi?

Quindi questa è la confusione input. La confusione di output è che in DFS, quando hai finito, hai una struttura simile a una tabella che registra la scoperta e il tempo di fine di ogni nodo, giusto? Come si estrae una soluzione, cioè un percorso dai nodi di origine a destinazione, da quello?

Spero di avere senso. Grazie!

EDIT: ecco cosa intendo per DFS non prendendo un nodo di origine. Questo è lo pseudocodice DFS di CLRS. Non lo vedo prendere un nodo di origine da nessuna parte. Tutto quello che vedo fare è passare attraverso tutti i nodi nel grafico.

DFS(G)
1 for each vertex u ∈ V[G]
2 do color[u] ← WHITE
3 π[u]← NIL
4 time ← 0
5 for each vertex u ∈ V[G]
6 do if color[u] = WHITE
7 then DFS-VISIT(u)

DFS-VISIT(u)
1 color[u] ← GRAY ✄ White vertex u has just been discovered.
2 time ← time+1
3 d[u] ← time
4 for each v ∈ Adj[u] ✄ Explore edge (u,v).
5 do if color[v] = WHITE
6 then π[v] ← u
7 DFS-VISIT(v)
8 color[u] ← BLACK ✄ Blacken u;it is finished.
9 f [u] ← time ← time+1

Answer 1

La confusione input:

Il particolare DFS fornito da CLRS non si preoccupa di dove si cerca. Il risultato esatto della ricerca dipenderà dall'ordinamento dei nodi in V[G]. Normalmente penserei a DFS come a partire da un nodo, ad esempio:

DFS-Simple(G, s)
1 for each vertex u ∈ V[G]
2   do color[u] ← WHITE
3 π[u]← NIL
4 time ← 0
5 DFS-VISIT(s)

La versione di CLRS produce una foresta (un albero per ogni componente del grafico) anziché un solo albero, che presumibilmente si adattava meglio al loro scopo.

La confusione di output:

I percorsi non sono registrati dai tempi, ma dai suggerimenti dei genitori π. Ad esempio, dato un nodo v, puoi stampare il percorso al suo nodo radice in questo modo:

Print-Path-To-Root(v)
1 while v ≠ Nil
2   do print v
3      v ← π[v]

Answer 2

Sia BFS che DFS prendono come inserimento di un nodo di origine.

Quando si esegue il pathfind con DFS, ti fermi semplicemente quando trovi il tuo nodo e quindi elimina lo stack fino al nodo originale per trovare il percorso.