Bonjour,

J'ai un souci de compréhension sur un algorithme de parcours de graphe en profondeur qui marque les arcs et non les sommets. En particulier, l'instruction "demarquer tous les arcs issus du sommet en tête de pile". Pour moi, si on demarque tous les arcs à chaque fois, on se retrouve avec un algorithme sans fin. Si qqn pourrait m'éclairer.

Algorithme. Parcours en profondeur

(marquage des arcs non définitif)

Entrée : sommet i, graphe G

Début

La pile est vide

Aucun arc n’est marqué

Empiler i

Tant que la pile n’est pas vide,faire

Tant qu’ il existe un successeur S ausommet SP  en tête de pile tel que l’arc (SP,S) est non marqué SP, faire

(* attention : le sommet en tête de pile change à chaque itération ! *)

Traiter S

Si S n’est pas déjà dans la pile, Empiler S

Marquer l’arc (SP,S)

Fin tant que

Démarquer tous les arcs issus du sommet en tête de pile

Dépiler

Fin tant que

Fin