Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Parcours en profondeur


Sujet :

Algorithmes et structures de données

  1. #1
    Membre à l'essai
    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 :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

  2. #2
    Expert éminent sénior
    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 ?"
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  3. #3
    Membre à l'essai
    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.