Parcours en profondeur

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

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

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

---

Bonjour :coucou:

D'abord, bien différencier "graphe" et "graphe acyclique". Tu ne peux pas tourner en rond sans cycle. Il doit y avoir dans les hypothèses précédant cet algorithme une restriction aux graphes acycliques.

Ensuite, aucun intérêt de "démarquer". Que le graphe soit acyclique ou non. D'où vient cet algorithme ? Wikipedia ne démarque pas. (ok, la source est douteuse mais c'est un premier élément).

Citation:

---

Si qqn pourrait m'éclairer.

---

Enfin, "si" + imparfait de l'indicatif dans la proposition subordonnée, pour permettre un conditionnel dans la proposition principale. : "Si quelqu'un pouvait m'éclairer, il m'aiderait". Ou alors on sous-entend la subordonnée (si+imparfait), SANS "SI" : "Quelqu'un pourrait-il m'éclairer ?"

Merci pour votre réponse.

Quand je disais sans fin, je parlais plutôt du fait de repasser indéfiniment sur les arcs puisqu'on les démarque à chaque fois et que la condition pour rentrer dans une boucle est d'avoir un arc non marqué.

Les sources sont un cours sur les graphes, mais le professeur ne répondant pas, je préfèrais demander avant de continuer.