Discussion :

[hanadi_09]

bonjour
Pourquoi les algorithmes de recherche en profondeur (depth_first_search) et en largeur (breadth_first_search) bloquent dans les cas des graphes cycliques(graphe avec boucles) sachant qu’on n’exploite pas un nœud exploité auparavant? SVP si vous avez un exemple illustrant ce blocage vous me le donnez

[Dakeyras Khan]

euh, ils ne sont pas sensés bloquer ...
tu t'es peut-être trompé en codant ...

[hanadi_09]

j'ai pas implémenté les algorithmes mais en vérité vs avez raison ces algorithmes posent un pb d'incomplétude qd on mémorise pas les états visités
en tt cas merci

[Invité]

Bonjour,

Le mémorisation des états visités fait partie de l'algorihtme. C'est normal que l'algorithme ne fonctionne pas si on ne l'applique pas en entier.

Pour ce qui est de la question initiale, les deux algorithmes de parcours de graphe cités ne provoquent pas de blocage, même s'ils sont utilisés sur des graphes cycliques (avec des boucles).

Wikipédia parle de ces algorithmes : Parcours de graphe.

[Matthieu Brucher]

Le mémorisation des états visités fait partie de l'algorihtme. C'est normal que l'algorithme ne fonctionne pas si on ne l'applique pas en entier.

Faux. Dans le cas de parcours d'arbres, il n'y a pas de mémorisation des états visités, et quand on explique ces algos, c'est généralement sur des arbres.

[hanadi_09]

alors ces algorithme bloquent dans les graphes avec cycles c'est bien ça