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

[Matthieu Brucher]

Si tu prends la version simple faite pour les arbres, oui.

[hanadi_09]

il y a une chose que je veux comprendre . ces algorithmes sont spécifiques à la recherche dans les graphes ou dans les arbres ou les deux?

[Matthieu Brucher]

Dans leur formulation simple, c'est une recherche dans un arbre. Dans leur formulation plus complexe avec mémoire des noeuds visités, c'est pour les graphes.

[hanadi_09]

alors si j'ai bien saisi, en étant dans le cas de recherche dans des graphes d'état et en utilisant leur formulation complexe qui inclut une mémorisation des états visités , le problème des cycles ne se pose pas et l'algorithme ne boucle pas dans un cycle et par conséquent ne bloque pas dans un graphe cyclique est ce que c'est bien ça ??

[Matthieu Brucher]

Exactement.

[hanadi_09]

merci beaucoup

[SpiceGuid]

alors si j'ai bien saisi, en étant dans le cas de recherche dans des graphes d'état et en utilisant leur formulation complexe qui inclut une mémorisation des états visités , le problème des cycles ne se pose pas et l'algorithme ne boucle pas dans un cycle et par conséquent ne bloque pas dans un graphe cyclique est ce que c'est bien ça ??

Il faut prendre garde à adapter ta stratégie de mémorisation à ta stratégie de parcours.

Il y a 3 possibilités :

1. Tu ne parcours le graphe qu'une seule fois. Dans ce cas il suffit d'ajouter un bool sur chaque noeud. Initialement il est à false et il passe à true quand tu atteins le noeud.
2. Tu parcours le graphe plusieurs fois. Dans ce cas il suffit d'avoir une horloge globale que tu incrémentes à chaque parcours et une heure locale sur chaque noeud. Lorsque tu visites un noeud tu le remets à l'heure globale. Un noeud en retard sur l'horloge globale est un noeud nouvellement visité pour ce parcours (mais qui a éventuellement déjà été visité lors des parcours précédents).
3. Tu parcours le graphe de façon réentrante, c'est-à-dire que tu veux pouvoir invoquer un parcours du graphe lors d'un parcours du même graphe. Dans ce cas la mémorisation doit être locale au parcours au lieu d'être locale aux noeuds.

Deux références incontournables (ou encore deux sujets passionnants pour un candidat-rédacteur dvp) :

• On the Linearization of Graphs and Writing Symbol Files
• Inductive Graphs and Functional Graph Algorithms