Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 17-03-2020 15:38:23

bbsebb
Membre
Inscription : 01-03-2020
Messages : 14

Algorithmique

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 démarque 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

Hors ligne

#2 18-03-2020 13:31:01

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : Algorithmique

Bonjour,

  Je ne comprends pas bien cet algorithme. Tu as une référence plus précise (ou peux-tu en faire une copie)?
Parce que si on démarque les arcs qu'on vient de marquer, je ne vois pas l'intérêt...

F.

Hors ligne

#3 18-03-2020 19:09:54

bbsebb
Membre
Inscription : 01-03-2020
Messages : 14

Re : Algorithmique

Je ne vois pas non plus l'intérêt, c'est pour cela je pose cette question. Pour moi c'est un algorithme sans fin. Je met le paragraphe du cours en entier :
Parcours en profondeur, marquage des arcs non définitif

Si on souhaite avoir une énumération exhaustive de tous les chemins issus de 1, on peut imaginer de marquer, non plus les sommets, mais les arcs. Lorsqu’un sommet ne conduit plus à de nouveaux chemins, c’est que tous les arcs qui en partent ont été visités. Mais ces arcs doivent pouvoir être revisités, si on revient à ce même sommet en ayant emprunté un autre chemin. Il faut donc, lorsqu’on dépile un sommet, démarquer tous les arcs qui en partent. Par contre, avant d’empiler un sommet, il faut lors s’assurer que celui-ci ne figure pas déjà dans la pile (c’est à dire ne figure pas dans le chemin qu’on est en train d’énumérer), car alors il y aurait risque de bouclage, en cas de circuit dans le graphe.


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 au sommet 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

La simulation de cet algorithme sur le graphe étudié précédemment est laissé à titre d’exercice (en utilisant le même tableau que précédemment, la colonne ″sommets marqués″ étant remplacée par ″arcs marqués″). On voit en particulier lors de cette simulation que, pour tout chemin élémentaire, il existe une étape de l’algorithme telle que la pile contient, lors de cette étape, le chemin.

Hors ligne

Pied de page des forums