Discussion :

[bbsebb]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Flodelarab]

Bonjour

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).

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 ?"

[bbsebb]

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.