Entrée/sortie de la première en largeur par rapport à la première en profondeur

Question

Ma question ne concerne pas vraiment le mécanisme de l'un ou l'autre type de recherche. Je pense que c'est beaucoup plus banal que cela - je ne comprends pas l'entrée et la sortie de l'un ou l'autre. Plus spécifiquement, dans CLRS, BFS prend en entrée un graphe et un noeud source, mais DFS ne prend qu'un graphe. Est-ce que DFS ne se soucie pas de l'endroit où vous effectuez la recherche?

Donc c'est la confusion d'entrée. La confusion de sortie est que dans DFS, lorsque vous avez terminé, vous avez une structure semblable à une table qui enregistre la découverte et l'heure de fin de chaque nœud, n'est-ce pas? Comment extraire une solution, c'est-à-dire un chemin de la source aux nœuds de destination, à partir de cela?

J'espère que j'ai du sens. Merci! Editer: Voici ce que je veux dire par DFS ne prenant pas un nœud source. C'est le pseudo-code DFS de CLRS. Je ne le vois pas prendre un nœud source nulle part. Tout ce que je vois faire, c'est passer par tous les nœuds du graphique.

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 confusion d'entrée:

La DFS particulière donnée par CLRS ne se soucie pas de savoir où vous effectuez une recherche à partir. Le résultat exact de la recherche dépendra de l'ordre des nœuds dans V[G]. Normalement, je pense de la DSV à partir d'un noeud, par exemple:

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 version de CLRS produit une forêt (un arbre pour chaque composant du graphique) au lieu d'un seul arbre, qui sans doute adapté leur but meilleur.

La confusion de sortie:

Les chemins sont enregistrés non pas par les horodateurs, mais par les pointeurs parents π. Par exemple, étant donné un nœud v, vous pouvez imprimer le chemin d'accès à son nœud racine comme ceci:

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

Answer 2

BFS et DFS prennent en entrée un noeud source. Lorsque vous effectuez une recherche de chemin avec DFS, vous arrêtez simplement lorsque vous trouvez votre nœud, puis vous chargez la pile jusqu'au nœud d'origine pour trouver le chemin.