Perché si sono garantiti per trovare il risultato, se è nel grafico con BFS, ma non con DFS?

Question

Ho letto da qualche parte che DFS non è garantito per trovare una soluzione, mentre BFS è .. perchè? Io davvero non capisco come questo sia vero .. qualcuno potrebbe dimostrare un caso per me che lo dimostra?

Answer 1

DFS, fin dalla sua una ricerca in profondità, potrebbe rimanere bloccati in un ramo infinito e non raggiungerà mai il vertice che stai cercando. BFS passa attraverso tutti i vertici alla stessa distanza dalla radice ogni iterazione, non importa quale ramo sono su in modo da trovare il vertice desiderato alla fine.
Esempio:

root -> V1 -> v2 -> v3 -> ... va avanti per sempre
 | -.> U

In questo esempio, se DFS inizia alla radice e poi prosegue v1. non potrà mai raggiungere u in quanto il ramo è entrato è infinito. BFS andrà dalla radice a uno v1 ou e poi l'altro.

Answer 2

L'output sia DFS e BFS (sui grafici con un numero finito di vertici) terminare e produrre un percorso (o meglio un albero, ma l'OP solo sembra interessare un percorso di detto albero). Non importa se ci sono cicli nel grafico, poiché entrambe le procedure mantengono traccia delle quali vertici sono già stati visitati e quindi evita visitando stesso vertice più di una volta. Qualsiasi implementazione sano di DFS / BFS fa questo -. Altrimenti sareste costretti a grafi aciclici solo (vedere il pseudocodice data in CLRS)

Come @yurib detto, se il grafico ha un numero infinito di nodi, DFS può prendere per sempre. Dato che ci sono nodi infiniti, non possiamo praticamente tenere traccia di quali vertici sono stati già visitati (che avrebbe preso di memoria potenzialmente infinito) e, anche se abbiamo fatto, là forse essere un percorso infinito che contiene i vertici unici che non contiene il vertice che stiamo cercando .

Tuttavia, questo non è l'unica ragione DFS non trova sempre il percorso più breve. Anche in grafi finiti, DFS potrebbe non riuscire a trovare il percorso più breve.

Il motivo principale è che BFS esplora sempre tutti i nodi ad una distanza x dalla radice prima di passare a quelle distanza x + 1. Pertanto, se un nodo è situato ad una distanza k, possiamo essere che la distanza minima dalla radice a quel nodo è k e non k-1, k-2, ..., 0 (altrimenti avremmo incontrato in precedenza).

DFS, d'altra parte, esplora fondamentalmente nodi lungo un sentiero fino a quando non ci sono più nuovi nodi su questa strada prima di guardare in un percorso diverso. DFS solo esplora ciascuna successore di un nodo per uno, in un ordine sostanzialmente arbitrario. Questo significa che possono trovare un percorso più lungo per il nodo di destinazione solo perché è appena successo per esplorare questa strada prima.

Nell'immagine qui sopra, a BFS avrebbe esplorato B ed E prima, e poi raggiungere D via E - dandoci il percorso di D come root-> E-> D. Un DFS potrebbe avviare la ricerca da B prima, trovando così il percorso root-> B-> C-> D, che chiaramente non è la più breve.

Si noti la decisione cruciale è stato quello di andare per esplorare B prima E. Un DFS potrebbe aver scelto E e arrivato alla risposta corretta. Ma c'è, in generale, modo non sapere quale percorso a scendere prima (se sapevamo che avremmo conoscere il più breve comunque percorso). Per un DFS il percorso che si trova semplicemente dipende dall'ordine in cui esplora i nodi successori, che possono o non possono produrre un percorso più breve.

Answer 3

@yurib è corretta, ma v'è un ulteriore complicazione.

Se il vertice desiderato non è nel grafico, allora né BFS o DFS verrà risolta se c'è un ciclo ... a meno che non si prendano misure per rilevare cicli. E se si stanno prendendo provvedimenti per rilevare cicli, sia BFS e DFS terminerà.