Demander le programme !

BO sd5

Notion de parcours

Exemple introductif

Vous voici dans un lieu inconnu, un véritable dédale ! Vous voulez explorer complètement le lieu.
Par chance, vous disposez du plan suivant :

labyrinthe

Vous comprenez que vous êtes au niveau du coin inférieur gauche de ce plan.

Afin de faciliter les explorations, vous décider de donner un nom, réduit à une lettre, à chaque intersection et cul-de-sac.

Vous obtenez donc le plan suivant, en sachant que vous êtes en $A$ initialement.

labyrinthe avec lettres

Plutôt que de voir le lieu comme un plan avec des lettres, on peut le modéliser par un graphe où :

Le lieu est donc modéliser par le graphe suivant :

graphe modélisant le labyrinthe

Explorer complètement le lieu, revient à passer par chaque sommet du graphe en visitant toutes les arêtes du graphes.

  1. À quelle notion déjà vue vous fait penser ce graphe ?

  2. En quoi ce graphe diffère de cette notion déjà vue ?

Code de déblocage de la correction :

Notion de parcours

Voici ci-dessous une première définition :

Parcourir un graphe consiste à :

  • visiter chaque sommet du graphe une seule fois,

  • appliquer un même traitement en chaque sommet.

Considèrons le labyrinthe d'introduction où l'entrée est en $A$.

labyrinthe avec lettres

Appliquons comme traitement constant le fait de toujours avancer en longeant les murs en faisant en sorte que la main droite reste collée à un mur.

Si on liste les sommets atteints successivement pour la première fois, on obtient : ['A', 'B', 'E', 'C', 'F', 'I', 'J', 'G', 'H', 'D'].

On a ainsi obtenu un parcours du graphe de racine 'A' :

graphe modélisant le labyrinthe
  1. Trouver un autre lieu de départ dans le labyrinthe tel qu'en se déplaçant en longeant les murs de sorte que la main droite reste collée à un mur, seule une partie du labyrinthe soit parcourue.

  2. Comment modifier le labyrinthe pour qu'en partant du sommet 'A' avec un déplacement par une main droite posée contre un mur vous ne parcouriez plus qu'une partie du labyrinthe ?

  3. Critiquer la définition écrite dans l'exemple précédent.

Code de déblocage de la correction :

Obtenons désormais une définition plus précise :

Un parcours de racine $r$ est une liste $L$ de sommets telle que :

Bien comprendre que le but d'un parcours est d'obtenir la liste de tous les sommets une seule fois.

On reprend le labyrinthe et son graphe :

labyrinthe avec lettres graphe modélisant le labyrinthe
  1. Voici deux listes de sommets :

    • ['A', 'B', 'E', 'I', 'J' ,'F', 'G', 'H', 'D', 'C'],

    • ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'].

    Quelles listes parmi celles ci-dessus correspondent à un parcours du graphe ?

  2. Proposer un autre parcours du graphe.

Code de déblocage de la correction :

On peut retrouver le parcours obtenu à l'exemple 1 directement avec le graphe déjà obtenu :

graphe modélisant le labyrinthe

Méthode : Descendre le plus profondément possible dans le graphe.
Une fois atteint un sommet sans arête menant à un sommet non encore visité (comme par exemple l'équivalent d'une feuille d'un arbre), remonter au sommet le plus proche où il existe une arête menant à un sommet non encore exploré.

Voici la succession des sommets obtenus en parcourant suivant cette méthode le graphe en partant du sommet $A$ :

  1. Suivre l'arête menant à $B$ :

    Étape 1 On obtient aussi le début parcours suivant : ['A', 'B'].
  2. Suivre l'arête menant à $E$ (on pourrait aussi aller vers $C$):

    Étape 2 On obtient aussi le début parcours suivant : ['A', 'B', 'E'].
  3. On ne peut aller plus profondément à partir de $E$ car toutes les arêtes y menant on déjà été parcourues.
    Remonter au sommet précédent $E$ : $B$.
    Comme il reste encore une arête reliant $B$ à un sommet non encore parcouru, suivre l'arête reliant $B$ à $C$ :

    Étape 3 On obtient aussi le début parcours suivant : ['A', 'B', 'E', 'C'].
  4. Suivre l'arête menant à $F$ (on pourrait aussi aller vers $D$):

    Étape 4 On obtient aussi le début parcours suivant : ['A', 'B', 'E', 'C', 'F'].
  5. Suivre l'arête menant à $I$ (on pourrait aussi aller vers $G$):

    Étape 5 On obtient aussi le début parcours suivant : ['A', 'B', 'E', 'C', 'F', 'I'].
  6. Suivre l'arête menant à $J$ (on pourrait aussi aller vers $G$) :

    Étape 6 On obtient aussi le début parcours suivant : ['A', 'B', 'E', 'C', 'F', 'I', 'J'].
  7. On ne peut aller plus profondément à partir de $J$ car toutes les arêtes y menant on déjà été parcourues.
    Remonter au sommet précédant $J$ : $I$.
    Comme il reste encore une arête reliant $I$ à un sommet non encore parcouru, suivre l'arête reliant $I$ à $G$ :

    Étape 7 On obtient aussi le début parcours suivant : ['A', 'B', 'E', 'C', 'F', 'I', 'J', 'G'].
  8. Suivre l'arête menant à $H$ (on ne prend pas l'arête vers $F$ car on est déjà passé par $F$):

    Étape 8 On obtient aussi le début parcours suivant : ['A', 'B', 'E', 'C', 'F', 'I', 'J', 'G', 'H'].
  9. On ne peut aller plus profondément à partir de $H$ car toutes les arêtes y menant on déjà été parcourues.
    Remonter au sommet précédant $H$ : $G$ ; cependant aucune arête liée à ce sommet ne permet d'atteindre un sommet non encore parcouru ($F$ a déjà été parcouru).
    Remonter au sommet précédant $G$ : $I$ ; cependant aucune arête liée à ce sommet ne permet d'atteindre un sommet non encore parcouru.
    Remonter au sommet précédant $I$ : $F$ ; cependant aucune arête liée à ce sommet ne permet d'atteindre un sommet non encore parcouru.
    Remonter au sommet précédant $F$ : $C$.
    Comme il reste encore une arête reliant $C$ à un sommet non encore parcouru, suivre l'arête reliant $C$ à $D$ :

    Étape 9 On obtient aussi le parcours suivant : ['A', 'B', 'E', 'C', 'F', 'I', 'J', 'G', 'H', 'D'].
  10. On ne peut aller plus profondément à partir de $D$ car toutes les arêtes y menant ont déjà été parcourues.
    Remonter au sommet précédant $D$ : $C$ ; cependant aucune arête liée à ce sommet ne permet d'atteindre un sommet non encore parcouru.
    En remontant ainsi, aucun sommet atteint n'est relié à un sommet non encore parcouru : il ne reste plus de sommets à découvrir. on a donc fini de parcourir le graphe.
    On obtient aussi aboutit au parcours suivant : ['A', 'B', 'E', 'C', 'F', 'I', 'J', 'G', 'H', 'D'].

Il est possible de modéliser le labyrinthe par un autre graphe. On obtiendrait ainsi un autre parcours ; les sommets seraient identiques mais leur ordre d'apparition diffèrerait.

Un parcours de graphe n'est pas unique.

graphe modélisant le labyrinthe

Refaire le parcours à partir de ce graphe en choisissant de partir vers le sommet de "droite" à chaque "intersection".

Code de déblocage de la correction :

Voici ci-dessous un graphe orienté.

  1. Proposer un dictionnaire en Python qui permet d'implémenter la liste d'adjacence du graphe orienté ci-dessus.

  2. Proposer un script qui récupère tous les sommets du graphe orienté précédent sans doublon. Le tester sur le graphe précédent.

  3. Est-ce que le script précédent qui renvoie l'ensemble des sommets une unique fois renvoie toujours un parcours ?

Code de déblocage de la correction :

Attention à ne pas confondre liste de tous sommets apparaissant une seule fois et parcours !

Un parcours doit aussi vérifier la condition : tout sommet, sauf la racine , doit être adjacent à au moins un sommet placé devant lui dans la liste définissant le parcours.

Parcours en profondeur

Vision naïve

Le parcours en profondeur revient à ce que vous feriez si un jour vous vous retrouviez perdu.e.s dans un lieu inconnu que vous désirez découvrir (un désir vraiment très profond !) :

Le parcours en profondeur correspond à la stratégie de parcours de graphe suivante :
en visitant un voisin $v$ d'un sommet $u$, on visite d'abord les voisins de $v$ avant de visiter les autres voisins de $u$.

Comment l'implémenter ?

Sans chercher à comprendre pour l'instant tous les détails, lors de l'exploration :

On retrouve bien le principe dernier lieu rajouté, premier lieu retiré : c'est le principe d'une pile.

L'implémentation d'un parcours en profondeur se fait à l'aide d'une pile.

Pour se souvenir de ce qui a déjà été exploré du reste, il est important de "marquer" tout endroit exploré afin de ne pas les visiter à nouveau. En pratique, dans un labyrinthe, si on a la chance d'avoir une craie, on peut écrire une marque ou colorier en partie un endroit.

Cette exploration pour tout découvrir du lieu peut s'écrire sous forme d'algorithme en langage naturel :

A. Chercher un endroit non encore visité B. Puis marquer cet endroit nouvellement visité C. Ensuite étudier les lieux voisins de cet endroit ; trois possibilités : cas 1 : si le lieu voisin a déjà été exploré (car marqué), on l'ignore, cas 2 : si le lieu voisin n'a pas encore été visité, je le visite : on recommence alors le B. cas 3 : lorsque tous les voisins ont été visités : cet endroit n'a plus d'intérêt : on revient à l'endroit précédant celui actuel et on recommence le C. D. On continue ainsi tant qu'il reste des lieux à visiter.

Quelle(s) partie(s) de l'algorithme permet(tent) d'obtenir possiblement plusieurs parcours différents à partir du même sommet ?

Code de déblocage de la correction :

Quatre animations ci-dessous représentent 4 parcours différents sur le même graphe à partir du sommet 'A'.

  1. Répérer le parcours qui correspond bien à un parcours en profondeur du graphe à partir du sommet 'A'.

  2. Expliquer pourquoi les autres parcours ne sont pas un parcours en profondeur du graphe à partir du sommet 'A'.

Parcours 1 :

Parcours 2 :

Parcours 3 :

Parcours 4 :

Code de déblocage de la correction :

Plusieurs algorithmes sont construits sur ce principe de parcours en profondeur.

Algorithme en récursif

Nous allons maintenant réécrire la vision naïve précédente sous forme d'une procédure récursive en pseudo-code en utilisant le vocabulaire des graphes à la place de celui de lieux comme un labyrinthe :

parcourir_profondeur(graphe, sommet) : Marquer le sommet comme visité et l'afficher Pour chaque voisin du sommet passé en paramètre Si le voisin n'est pas marqué visité parcourir_profondeur(graphe, voisin)
  1. Pourquoi est-ce bien une procédure récursive ?

  2. Pourquoi est-on certain que cette procédure s'arrête à un moment ?

Code de déblocage de la correction :

Attention ! On ne marque un sommet (pour ne plus chercher à aller le visiter) non parce qu'il a déjà été rencontré comme voisin mais lorsqu'on le visite réellement : il ne faut alors chercher à le (re)visiter.

On sait qu'il est possible d'implémenter un graphe en prenant un dictionnaire pour définir sa liste d'adjacence.

Devant tant d'efforts pour comprendre les parcours, vous rêvez de partir en voyage sur le continent sud-américiain. Mais quel parcours effectuer pour visiter tous les pays de l'Amérique du Sud ?

Vous allez dans cet exercice :

Voici la carte des pays du continent sud-américain :

cartedes Etats

On considère le dictionnaire suivant qui permet d'associer à chaque pays d'Amérique du Sud la liste des pays partageant une frontière terrestre.

G = {} #ou dict() mais plus coûteux
G["France"] = ["Bresil", "Suriname"]
G["Argentine"] = ["Bolivie", "Bresil", "Chili", "Paraguay", "Uruguay"]
G["Bolivie"] = ["Argentine", "Bresil", "Chili", "Paraguay", "Perou", "Uruguay"]
G["Bresil"] = ["Argentine", "Bolivie", "Colombie", "France", "Guyana", "Paraguay", "Perou", "Suriname", "Uruguay", "Venezuela"]
G["Chili"]=["Argentine", "Bolivie", "Perou"]
G["Colombie"] = ["Bresil", "Equateur", "Perou", "Venezuela"]
G["Equateur"] = ["Colombie", "Perou"]
G["Guyana"] = ["Bresil", "Suriname", "Venezuela"]
G["Paraguay"] = ["Argentine", "Bolivie", "Bresil"]
G["Perou"] = ["Bolivie", "Bresil", "Chili", "Colombie", "Equateur"]
G["Suriname"] = ["Bresil", "France", "Guyana"]
G["Uruguay"] = ["Argentine", "Bolivie", "Bresil"]
G["Venezuela"] = ["Bresil", "Colombie", "Guyana"]
        

Pour savoir quels sommets ont déjà été visités ou non, vous allez utiliser un dictionnaire dont les clés seront les sommets du graphe et les valeurs associées seront les chaînes de caractères soit "inconnu", soit "visite"

  1. Créer une fonction initialiser qui prend comme paramètre un graphe et renvoie un dictionnaire dont les clés sont les sommets du graphe et la valeur est toujours "inconnu".

  2. Code de déblocage de la correction :

  3. Créer une fonction visiter qui prend comme paramètre le dictionnaire associant à chaque sommet son état de connaissance et un sommet du graphe, fonction qui renvoie le dictionnaire de connaissance où la valeur associée au sommet entré est mise à 'visite'

  4. Code de déblocage de la correction :

  5. Écrire en langage Python la procédure récursive parcours_longueur_rec correspondant à un parcours en profondeur en faisant aussi en sorte que chaque sommet qui vient d'être marqué soit affiché.
    Cette procédure prend trois arguments : un graphe, un sommet de ce graphe, sommet servant de point de départ au parcours et un dictionnaire associant à chaque sommet du graphe sont état ('inconnu' ou 'visite')
    Gérer l'affichage à l'aide de l'instruction print.

  6. Vérifier que votre procédure parcours_longueur_rec appliquée au sommet "Bolivie" conduit au parcours visualisable avec l'animation ci-dessous :

  7. Appliquer cette procédure au graphe modélisant les pays d'Amérique du Sud en prenant comme racine, c'est-à-dire sommet de départ la France (pour la Guyane Française). À la lecture de tous les pays que vous allez visiter, vous allez être profondément heureux.ses.

  8. Code de déblocage de la correction :

Les dictionnaires Python sont ordonnés depuis la version 3.7 pour garantir justement que les parcours s'effectuent dans le même ordre sur toutes les machines. Si vous travaillez avec une version plus ancienne, téléchargez une version récente.

La complexité en temps d'un parcours en profondeur est en $O(n+m)$, où $m$ désigne le nombre d'arètes du graphes et $n$ le nombre de sommets.

En effet, chacun des $n$ sommets sera traité une seule fois. Mais à partir de chaque sommet, on itère sur les voisins donc $O(n)$ ne suffit pas : il faut prendre aussi en compte le nombre $m$ d'arêtes.

Nous allons désormais dans cet exercice travailler dans le cas d'un graphe orienté. Considérons, par exemple le graphe suivant :

  1. Proposer un parcours en profondeur de graphe à partir du sommet 'A'.

  2. Code de déblocage de la correction :

  3. Voici ci-dessous le dictionnaire permettant de définir le graphe :

    graphe_or = {'A': ['B', 'G'],
               'B': ['C', 'E'],
               'D': ['F','G'],
               'E': ['A', 'D', 'H'],
               'F': ['B','C'],
               'H': ['F']
               }
            

    Utiliser le script obtenu dans l'exercice précédent sur ce graphe. Que remarquez-vous ?

  4. Expliquer la raison de ce que vous venez de remarquer.

  5. Code de déblocage de la correction :

  6. Proposer une correction du script incluant les fonctions initialiser et parcours_longueur_rec afin de le rendre fonctionnel avec un graphe orienté ayant au moins un sommet n'ayant aucun successeur.

  7. Tester le script modifié pour obtenir un parcours en profondeur du graphe à partir du sommet 'A'.

  8. Code de déblocage de la correction :

On peut obtenir un résultat similaire en utilisant un module dédié aux graphes : networkx. C'est le but de l'exercice suivant :

Vous allez dans cet exercice :

Voici la carte des pays du continent sud-américain :

cartedes Etats
  1. Télécharger le programme en langage Python. Le graphe non-orienté modélisant la carte a :

    • pour sommets les États,

    • pour arêtes toute frontière commune entre deux États.

  2. Le module networkx permet d'implémenter d'une autre manière le graphe.
    Voici quelques indications sur des méthodes de networkx en considérant un graphe nommé graphe et un sommet nommmé s :

    • La méthode nodes() renvoie sous forme d'un itérable l'ensemble des sommets du graphe graphe.
      sommets = graphe.nodes() stocke dans une variable sommets l'ensemble des sommets du graphe graphe.

    • Avec networkx, il est possible d'associer à tout sommet d'un graphe un dictionnaire d'attributs.
      attributs_sommet = graphe.nodes[s] stocke dans une variable attributs_sommet le dictionnaire des attributs du sommet s appartenant au graphe graphe.

    • attributs_sommet (défini comme ci-dessus) étant un dictionnaire, vous pouvez alors ajouter toute nouvelle association à celui-ci en utilisant les méthodes vues sur les ductionnaires :
      attributs_sommet["new_attribut"] = new_val permet de rajouter à l'objet sommet nommé sommet du graphe l'attribut nommé ici new_attribut en spécifiant sa valeur associée, ici new_val.

    Aidez-vous des deux indications précédentes afin de créer une procédure marquer qui :

    • prend comme argument un graphe graphe implémenté sous networkx et un sommet s (que l'on admet être de ce graphe),

    • créé dans le dictionnaire des attributs en lien avec le sommet s un attribut nommé "visite" associé à la valeur True.

    Code de déblocage de la correction :

  3. Voici une nouvelle méthode de networkx s'appliquant sur un objet graphe nommé ici graphe et qui prend comme paramètre un sommet nommmé s :
    graphe.neighbors(s) renvoie un ensemble itérable contenant tous les sommets voisins du sommet s du graphe graphe.

    Écrire en langage Python à l'aide du module netxorkx la procédure récursive correspondant à un parcours en profondeur en faisant aussi en sorte que chaque sommet qui vient d'être marqué soit affiché.

    Gérer l'affichage à l'aide de l'instruction print.

  4. Appliquer cette procédure au graphe modélisant les pays d'Amérique du Sud en prenant comme racine, c'est-à-dire sommet de départ la France (pour la Guyane Française). À la lecture de tous les pays que vous allez visiter, vous allez être profondément heureux.ses.

    Code de déblocage de la correction :

Voici désormais une variante colorée de l'algorithme précédent :

Le changement avec la version précédente réside surtout dans le marquage des sommets.
Au lieu d'avoir deux états marqués visite ou non visite, on considère trois états :

Voici cette variante de l'algorithme de parcours en profondeur en langage naturel :

// Fonction principale parcourir_profondeur(graphe G) : // coloration initale des sommets du graphe pour chaque sommet s du graphe G faire mettre la couleur du sommet s en blanc // coloration liée au parcours pour chaque sommet s du graphe G faire si la couleur du sommet s est en blanc alors visiter les voisins en profondeur de s par appel à la fonction visiter_profondeur(graphe G, sommet s) // fonction utilisée pour visiter les voisins en profondeurs d'un sommet visiter_profondeur(graphe G, sommet s) : mettre la couleur du sommet s en gris afficher le sommet s pour chaque voisin v du sommet s faire // cas de l'existence d'un voisin non encore visité si la couleur du voisin v est blanc alors visiter les voisins en profondeur de v par appel à la fonction visiter_profondeur(graphe G, sommet v) // une fois tous les successeurs visités mettre la couleur du sommet s en noir

En quoi l'algorithme écrit ci-dessus en langage courant est-il un algorithme récursif ?

Code de déblocage de la correction :

Dans tout cet exercice, vous travaillerez avec le graphe G défini par le dictionnaire suivant :

G = {}
G["France"] = ["Bresil", "Suriname"]
G["Argentine"] = ["Bolivie", "Bresil", "Chili", "Paraguay", "Uruguay"]
G["Bolivie"] = ["Argentine", "Bresil", "Chili", "Paraguay", "Perou", "Uruguay"]
G["Bresil"] = ["Argentine", "Bolivie", "Colombie", "France", "Guyana", "Paraguay", "Perou", "Suriname", "Uruguay", "Venezuela"]
G["Chili"]=["Argentine", "Bolivie", "Perou"]
G["Colombie"] = ["Bresil", "Equateur", "Perou", "Venezuela"]
G["Equateur"] = ["Colombie", "Perou"]
G["Guyana"] = ["Bresil", "Suriname", "Venezuela"]
G["Paraguay"] = ["Argentine", "Bolivie", "Bresil"]
G["Perou"] = ["Bolivie", "Bresil", "Chili", "Colombie", "Equateur"]
G["Suriname"] = ["Bresil", "France", "Guyana"]
G["Uruguay"] = ["Argentine", "Bolivie", "Bresil"]
G["Venezuela"] = ["Bresil", "Colombie", "Guyana"]
  1. En modifiant la procédure marquer faite dans le précédent exerice sur où l'implémentation était un dictionnaire, créer une fonction colorier qui a quatre paramètres :

    • graphe un graphe (que l'on considèrera comme un dictionnaire),

    • s un sommet du graphe graphe,

    • coul une chaîne de caractères valant soit "blanc", "gris" ou "noir

    • couleur un dictionnaire associant à chaque sommet du graphe une couleur.

    Cette procédure renvoie un dictionnaire qui associe à chaque sommet une "couleur" pouvant être : "blanc", "gris" ou "noir.

    Code de déblocage de la correction :

  2. Créer une procédure parcourir_profondeur qui prend en paramètres un graphe, nommé graphe implémenté par un dictionnaire.
    Cette procédure fera appel à la procédure visiter_profondeur que vous construirez à la question suivante.

    Code de déblocage de la correction :

  3. Créer une procédure visiter_profondeur qui prend en paramètres un graphe, nommé graphe, implémenté par un dictionnaire, un sommet de ce graphe nommé sommet et un dictionnaire couleur qui associe

    Code de déblocage de la correction :

  4. Tester cet algorithme de parcours en profondeur avec trois colorations en prenant le graphe sur les pays d'Amérique du Sud.

    Comparer les affichages obtenus avec les deux versions du parcours en profondeur en version récursive vues dans cette partie.

  5. Code de déblocage de la correction :

  1. En modifiant la procédure marquer faite dans le précédent exerice sur networkx, créer une procédure colorier qui a trois paramètres :

    • graphe un graphe (que l'on considèrera comme obejt de la classe Graph() du module netwokx),

    • s un sommet du graphe graphe,

    • coul une chaîne de caractères valant soit "blanc", "gris" ou "noir

    Les sommets se voient avec cette procédure rajouter un attribut nommé "couleur" pouvant prendre, outre None, trois valeurs : "blanc", "gris" ou "noir.

    sommet["attribut"] = valeur                     

    On peut rajouter à l'objet sommet nommé sommet du graphe n'importe quel attribut nommé ici attribut et spécifier la valeur de cette attribut.

    Code de déblocage de la correction :

  2. Créer une procédure parcourir_profondeur qui prend en paramètres un graphe, nommé graphe.
    Cette procédure fera appel à la procédure visiter_profondeur que vous construirez à la question suivante.

    Comme lors de l'exercice de programmation précédent, vous pouvez utiliser les méthodes suivantes :

    Voici quelques indications sur des méthodes de networkx en considérant un graphe nommé graphe et un sommet nommmé s :

    • liste_sommets = graphe.nodes()                      

      La méthode nodes() renvoie sous forme de liste l'ensemble des sommets du graphe graphe.

    • attributs_sommet = graphe.nodes[s]                      

      graphe.nodes[s] renvoie, sous forme de dictionnaire, les attributs du sommet s du graphe graphe.

    • attributs_sommet.get("attribut")                      

      permet d'obtenir (d'accéder) à la valeur de l'attribut "attribut"" du dictionnaire nommé attributs_sommet.

      La méthode get permet d'obtenir la valeur associée à la clé donnée comme argument ; plus précisément dico.get(cle) :

      • si la clé cle existe dans le dictionnaire dico alors il y a renvoi de la valeur associée (comme le ferait dico[cle]).

      • Si cette clé cle n'existe pas dans le dictionnaire, une nouvelle association cle: None est ajoutée au dictionnaire (sans lever une exception du type KeyError),

      • Il est possible de rajouter un deuxième paramètre qui sera la valeur par défaut de la clé cle lors du rajout de la nouvelle association de clé cle.

    Code de déblocage de la correction :

  3. Créer une procédure visiter_profondeur qui prend en paramètres un graphe, nommé graphe et un sommet de ce graphe nommé sommet.

    graphe.neighbors(s)                       

    renvoie la liste de tous les sommets voisins du sommet s du graphe graphe.

    Code de déblocage de la correction :

  4. Tester cet algorithme de parcours en profondeur avec trois colorations en prenant le graphe sur les pays d'Amérique du Sud.

    Comparer les affichages obtenus avec les deux versions du parcours en profondeur en version récursive vues dans cette partie.

  5. Code de déblocage de la correction :

Algorithme en itératif

L'algorithme en récursif d'un parcours en profondeur risque un débordement de la pile d'appel si cet algorithme est employé sur un graphe avec de nombreux sommets. Afin d'éviter cela, il peut être utile de programmer directement en itératif.

Nous avons déjà vu au 3.1. que "naturellement" l'implémentation d'un algorithme de parcours en profondeur se fait à l'aide d'une pile. Cette pile servira à remplacer la pile d'appel de la version récursive.

Dans cette pile seront stockés temporairement l'ensemble des sommets non encore visités.

Voici en langage naturel, une fonction donnant un parcours en profondeur en itératif :

fonction parcours_profondeur_iteratif(Graphe G, sommet s)
    Créer la liste visites des sommets déjà visités, liste réduite pour l'instant au sommet s
    Créer reste_a_voir une pile vide 
    Ajouter les voisins du sommet s à la pile reste_a_voir (=empiler)
    Tant que la pile reste_a_voir n'est pas vide faire :
        dépiler la tête de la pile reste_a_voir et la stocker dans une variable u 
        si u ne fait pas partie de la liste des sommets déjà visités faire :
            Rajouter u à la liste visite des sommets déjà visités
            Pour tout sommet voisin v du sommet u faire :
                si v ne fait pas partie de la liste des sommets déjà visités faire :
                    Ajouter le sommet v à la pile reste_a_voir 
    renvoyer la liste visites des sommets visités 
              
  1. Proposer un script en langage Python qui implémente la fonction parcours_profondeur_iteratif où graphe est défini par un dictionnaire donnant la liste d'adjacence.

    Pour l'instant, on suppose le graphe non-orienté.

    • Penser à utiliser liste[-1] pour obtenir le dernier élément de la liste liste.

    • Penser à utiliser la méthode pop pour supprimer un élément d'une liste dont la position est connue tout en renvoyant l'élément supprimé.

    1. Tester la fonction précédente avec le graphe suivant :

      G = {}
      G["France"] = ["Bresil", "Suriname"]
      G["Argentine"] = ["Bolivie", "Bresil", "Chili", "Paraguay", "Uruguay"]
      G["Bolivie"] = ["Argentine", "Bresil", "Chili", "Paraguay", "Perou", "Uruguay"]
      G["Bresil"] = ["Argentine", "Bolivie", "Colombie", "France", "Guyana", "Paraguay", "Perou", "Suriname", "Uruguay", "Venezuela"]
      G["Chili"]=["Argentine", "Bolivie", "Perou"]
      G["Colombie"] = ["Bresil", "Equateur", "Perou", "Venezuela"]
      G["Equateur"] = ["Colombie", "Perou"]
      G["Guyana"] = ["Bresil", "Suriname", "Venezuela"]
      G["Paraguay"] = ["Argentine", "Bolivie", "Bresil"]
      G["Perou"] = ["Bolivie", "Bresil", "Chili", "Colombie", "Equateur"]
      G["Suriname"] = ["Bresil", "France", "Guyana"]
      G["Uruguay"] = ["Argentine", "Bolivie", "Bresil"]
      G["Venezuela"] = ["Bresil", "Colombie", "Guyana"]
              
    2. Code de déblocage de la correction :

    3. Utiliser la représentation du graphe ci-dessous pour savoir si la liste renvoyée dans le cas où l'on prend comme sommet initial "Bolivie" correspond bien à un parcours en profondeur.

    4. Est-ce que le parcours en profondeur obtenu avec cet algorithme itératif dans le cas où l'on prend comme sommet initial "Bolivie" correspond bien au parcours en profondeur obtenu dans le cas récursif et qui est représenté dans le gif ci-dessous ?

    5. Comment pouvez-vous expliquer cette différence en comparant les deux algorithmes récursifs et itératifs ?

    6. Corriger le script précédent afin que le parcours renvoyé par la fonction parcours_profondeur_iteratif soit identique à celui en récursif.

    Code de déblocage de la correction :

Modifier la fonction parcours_profondeur_iteratif obtenue dans l'exercice précédent dans le cas où le graphe peut être orienté.

Vous pouvez tester votre script an utilisant ce graphe orienté :

graphe_or = {'A': ['B', 'G'],
           'B': ['C', 'E'],
           'D': ['F', 'G'],
           'E': ['A', 'D', 'H'],
           'F': ['B', 'C'],
           'H': ['F']
           }
        

Code de déblocage de la correction :

  1. En s'inspirant de vos travaux effectués ici, modifier la fonction parcours_profondeur_iteratif obtenue dans l'exercice précédent en utilisant un dictionnaire qui associe à chaque sommet une valeur 'inconnu' ou 'visite'.

    Code de déblocage de la correction :

  2. En comparant la complexité de la fonction parcours_profondeur_iteratif utilisant une liste des sommets déjà visités celle ci-dessus utilisant un dictionnaire qui associe à chaque sommet une valeur 'inconnu' ou 'visite', quelle implémentation semble préférable ?

    Code de déblocage de la correction :

Dans cet exercice, vous pouvez reprendre des éléments déjà obtenus à l'exercice de la première version récursive du parcours en profondeur comme ceux-ci :

  1. Écrire en langage Python une fonction parcours_profondeur_iteratif qui correspond à la fonction vue ci-dessus en langage naturel.

    • Penser à utiliser liste[-1] pour obtenir le dernier élément de la liste liste.

    • Penser à utiliser la méthode pop pour supprimer un élément d'une liste dont la position est connue tout en renvoyant l'élément supprimé.

  2. Tester cet algorithme de parcours en profondeur en prenant le graphe sur les pays d'Amérique du Sud.

  3. En vous aidant de la carte de l'Amerique du Sud ci-dessous, vérifier que la liste renvoyée correspond bien à un parcours en profondeur.

Code de déblocage de la correction :

L'implémentation à préférer pour un graphe sur lequel on veut appliquer un parcours en profondeur est la liste d'adjacence.

En effet, les voisins de chaque sommet sont systématiquement visités : il y a une itération sur les voisins du sommet.

Parcours en largeur

Exemple introductif

Revenons au labyrinthe de l'exemple introductif sur les parcours.

labyrinthe avec lettres

Plutôt que de suivre un chemin le plus loin possible pour revenir sur ses pas une fois un "cas-de-sac" atteint, nous allons plus "prudemment" parcourir le labyrinthe. L'idée est de visiter d'abord tout ce qui est très proche, puis tout ce qui est un peu plus loin, puis tout ce qui est un peu plus éloigné, ... en gagnant en confiance ainsi, nous atteidrons même les lieux les plus reculés. Plus précisément :

Un parcours en largeur d'un graphe revient à parcourir un graphe en explorant d'abord un sommet, puis ses sommets voisins, puis les voisins non encore explorés de ces voisins, et ainsi de suite jusqu'à ce que l'on ne découvre plus aucun sommet non encore exploré.

Quelle différence entre les deux parcours en profondeur et en largeur ?

En cas de "cul-de-sac", on repart de l'intersection pouvant nous apporter une information :

On peut visualiser comment fonctionne ce parcours en largeur en l'appliquant sur le graphe modélisant le labyrinthe :

Voici la succession des sommets obtenus en parcourant suivant cette méthode le graphe en partant du sommet $A$ :

  1. Suivre l'arête menant à $B$ :

    Étape 1 On obtient aussi le début parcours suivant : ['A', 'B'].
  2. On a fini de visiter les voisins direct de $A$ (ici un seul).
    On cherche maintenant les voisins de second niveau de $A$, ceux voisins de $B$.
    Il y a deux sommets vosins de $B$.
    Suivre l'arête menant à $E$ (on pourrait aussi aller vers $C$):

    Étape 2 On obtient aussi le début parcours suivant : ['A', 'B', 'E'].
  3. Sans chercher à savoir si l'on peut aller plus loin que $E$, visiter l'autre sommet voisin de $B$ possible : le sommet $C$.

    Étape 3 On obtient aussi le début parcours suivant : ['A', 'B', 'E', 'C'].
  4. Comme il ne reste plus de voisins de $B$ non visités, on poursuis le parcours en partant désormais des voisins trouvés de $B$, c'est-à-dire de $E$ et de $C$. En d'autres termes, on cherche maintenant les voisins de troisième niveau de $A$
    Comme $E$ est le sommet le plus anciennement trouvé, on cherche s'il existe de nouveaux sommets accessibles depuis $E$.
    Comme il n'y en a pas, on poursuit avec le second sommet successeur de $B$ trouvé : $C$. $C$ permet d'accéder à deux nouveaux sommets $F$ et $D$. On suppose que $F$ est le premier sommet visité, on a donc :

    Étape 4 On obtient aussi le début parcours suivant : ['A', 'B', 'E', 'C', 'F'].
  5. Sans chercher à savoir si l'on peut aller plus loin que $F$, visiter l'autre sommet voisin de $C$ possible : le sommet $D$.

    Étape 5 On obtient aussi le début parcours suivant : ['A', 'B', 'E', 'C', 'F', 'D'].
  6. Comme il ne reste plus de voisins de $C$ non visités, on poursuis le parcours en partant désormais des voisins trouvés de $C$, c'est-à-dire de $F$ et de $D$. En d'autres termes, on cherche maintenant les voisins de quatrième niveau de $A$
    Comme $F$ est le sommet le plus anciennement trouvé, on cherche s'il existe de nouveaux sommets accessibles depuis $F$.
    $F$ permet d'accéder à deux nouveaux sommets $I$ et $G$. On suppose que $I$ est le premier sommet visité, on a donc :

    Étape 6 On obtient aussi le début parcours suivant : ['A', 'B', 'E', 'C', 'F', 'D', 'I'].
  7. Sans chercher à savoir si l'on peut aller plus loin que $I$, visiter l'autre sommet voisin de $F$ possible : le sommet $G$.

    Étape 7 On obtient aussi le début parcours suivant : ['A', 'B', 'E', 'C', 'F', 'D', 'I', 'G'].
  8. Comme on a fini avec les voisins de $F$, on cherche maintenant les voisins du sommet $D$ trouvé au même niveau dque $F$.
    Comme $D$ ne permet pas d'accéder à de nouveau sommet, on a fini de visiter les voisins des voisisn de $C$. On cherche maintenant les voisins de cinquième niveau de $A$, ceux donc de $I$ et de $G$.
    Comme $I$ a été visité le plus anciennement, on commence par étudié ses nouveaux voisins.
    $I$ a trois voisins : $F$, $G$ et $J$. $J$ est le seul sommet non encore découvert.

    Étape 8 On obtient aussi le début parcours suivant : ['A', 'B', 'E', 'C', 'F', 'D', 'I', 'G', 'J'].
  9. Sans chercher à savoir si l'on peut aller plus loin que $J$, visiter les voisins de l'autre sommet de même niveau que $I$ : $G$. $G$ a trois voisins : $F$, $I$ et $H$. $H$ est le seul sommet non encore découvert.

    Étape 9 On obtient aussi le parcours suivant : ['A', 'B', 'E', 'C', 'F', 'D', 'I', 'G', 'J', 'H'].
  10. Maintenant que l'on a terminé l'exploration du cinquième niveau (les sommets pour lesquels il faut au minimum passer par 4 sommets intermédiaires pour y accéder en partant du sommet initial $A$, cherchons s'il y a un sixième niveau.
    Comme il n'existe pas de nouveau sommet à partir des sommets $J$ et $H$ du cinquième niveau, il n'y a pas de sixième niveau : l'exploration du graphe est terminée.
    On obtient aussi aboutit au parcours suivant : ['A', 'B', 'E', 'C', 'F', 'D', 'I', 'G', 'J', 'H'].

Pour un même graphe, les parcours en largeur et en profondeur conduisent à des parcours différents. Nous avions trouvé :

Vision naïve

Le parcours en largeur correspond à la stratégie de parcours de graphe suivante :
Si $v$ est un sommet voisin découvert d'un sommet $u$, on visite d'abord les voisins de $u$ avant de visiter les autres voisins de $v$.

Lors de l'exploration, on cherche à toujours élargir la connaissance des sommets sans s'éloigner trop du sommet de départ. Chaque étape revient à partir des sommets se trouvant à une certaine distance du sommet initiale et à chercher tous les sommets, non encore visités, qui se trouvent à une distance augmentée de 1.
À chaque étape, on repart donc des sommets découverts à l'étape précédente, en commençant par le sommet le plus ancien.

On retrouve bien le principe premier lieu rajouté, premier lieu retiré (car étudié) : c'est le principe d'une file.

L'implémentation d'un parcours en largeur se fait à l'aide d'une file.

Pour se souvenir de ce qui a déjà été exploré du reste, il est important de "marquer" tout endroit exploré afin de ne pas les visiter à nouveau. En pratique, dans un labyrinthe, si on a la chance d'avoir une craie, on peut écrire une marque ou colorier en partie un endroit.

Cette exploration pour tout découvrir du lieu peut s'écrire sous forme d'algorithme en langage naturel :

1. Partir du lieu le plus anciennement découvert (le plus ancien de la file d'attente). 2. Puis étudier tous les lieux voisins de cet endroit ; trois possibilités : cas 1 : si le lieu voisin a déjà été exploré (car marqué), on l'ignore, cas 2 : si le lieu voisin n'a pas encore été visité : on le rajoute à la liste d'attente et on recommence le 2. cas 3 : lorsque tous les voisins ont été visités : cet endroit n'a plus d'intérêt : on l'enlève de la liste d'attente. On recommence le 1. 3. On continue ainsi tant qu'il reste des lieux à étudier dans la file d'attente.

Quatre animations ci-dessous représentent 4 parcours différents sur le même graphe à partir du sommet 'A'.

  1. Répérer le parcours qui correspond bien à un parcours en largeur du graphe à partir du sommet 'A'.

  2. Expliquer pourquoi les autres parcours ne sont pas un parcours en largeur du graphe à partir du sommet 'A'.

Parcours 1 :

Parcours 2 :

Parcours 3 :

Parcours 4 :

Code de déblocage de la correction :

Version itérative

Nous avons déjà vu ci-dessus que "naturellement" l'implémentation d'un algorithme de parcours en largeur se fait à l'aide d'une file.

Dans cette file sera stocké temporairement l'ensemble des sommets non encore "étudiés", c'est-à-dire dont il reste à visiter les sommets voisins.

Voici en langage naturel, une fonction donnant un parcours en largeur en itératif :

fonction parcours_largeur(Graphe G, sommet s)
    Créer la liste visites des sommets déjà visités, liste réduite pour l'instant au sommet s
    Créer reste_a_voir une file vide 
    Ajouter les voisins du sommet s à la file reste_a_voir (=enfiler)
    Tant que la file reste_a_voir n'est pas vide faire :
        défiler la tête de la file reste_a_voir et la stocker dans une variable u 
        si u ne fait pas partie de la liste des sommets déjà visités faire :
            rajouter u à la liste visites des sommets déjà visités
            Pour tout sommet voisin v du sommet u faire :
                si v ne fait pas partie de la liste des sommets déjà visités faire :
                    Ajouter le sommet v à la file reste_a_voir
    renvoyer la liste visites des sommets visités 
              

Comparer la fonction parcours_profondeur_iteratif en langage naturel avec la fonction parcours_largeur ci-dessus.

Quelle différence remarquez-vous ?

Code de déblocage de la correction :

Comme vu lors de la première implémentation du parcours en profondeur itératif, on peut écrire l'algorithme de parcours en largeur en utilisant un graphe G défini par un dictionnaire donnant la liste d'adjacence en partant d'un sommet s comme vu dans l'exercice suivant :

  1. Reprendre le programme proposé à l'exercice implémentant d'une seconde manière le parcours en longueur itératif et le modifier pour obtenir une implémentation d'un parcours en largeur.

  2. Voici de nouveau une implémentation du graphe introductif du chapitre sur les graphes que l'on pouvait construire un graphe à partir d'un dictionnaire :

    graphe = {}    # création d'un dictionnaire vide 
    graphe["A"] = ["B", "C", "E", "F", "H"] # liens de A vers les sommets listés
    graphe["B"] = ["A", "D", "H"]
    graphe["C"] = ["A", "F",  "G", "H"]
    graphe["D"] = ["B", "H"]
    graphe["E"] = ["A", "H"]
    graphe["F"] = ["A", "C"]
    graphe["G"] = ["C", "H"]
    graphe["H"] = ["A", "B", "C", "D", "E", "G"]
                    

    Tester la fonction parcourir_largeur avec ce graphe.

  3. Décrire le parcours en largeur obtenu en partant du sommet "D".

  4. Code de déblocage de la correction :

    • Vérifier ce parcours grâce à la représentation ci-dessous de ce graphe.

      schéma du réseau social
    • où grâce à ce gif :

  5. Vérifier si le programme fonctionne encore si un sommet n'est plus une clé du dictionnaire graphe, par exemple avec ce graphe orienté :

    graphe = {}     
    graphe["A"] = ["B", "C", "E", "F", "H"] 
    graphe["B"] = ["A", "D", "H"]
    graphe["C"] = ["A", "F",  "G", "H"]
    graphe["D"] = ["B", "H"]
    graphe["E"] = ["A", "H"]
    graphe["F"] = ["A", "C"]
    graphe["G"] = ["C", "H"]
    
  6. Modifier la fonction parcourir_largeur de sorte qu'elle fonctionne encore avec des graphes orientés.

  7. Code de déblocage de la correction :

Comme pour le parcours en longueur, il est intéressant pour ces raisons de coût en temps de remplacer le test sur l'appartenance à une liste visites par un test sur un marquage géré par dictionnaire

En s'inspirant de vos travaux effectués précédemment, modifier la fonction parcourir_largeur obtenue dans l'exercice précédent en utilisant un dictionnaire qui associe à chaque sommet une valeur 'inconnu' ou 'visite'.

Vous pourrez tester votre programme par exemple avec ce graphe orienté : dont voici ci-dessous un dictionnaire le définissant le graphe :

graphe_or = {'A': ['B', 'G'],
           'B': ['C', 'E'],
           'D': ['F', 'G'],
           'E': ['A', 'D', 'H'],
           'F': ['B', 'C'],
           'H': ['F']
           }

Code de déblocage de la correction :

Comme vu pour le parcours en longueur, il est possible d'utiliser le module networkx pour implémenter des grpahes.

Dans cet exercice, vous pouvez vous aider du prgramme déjà obtenu à l'exercice sur le parcours en profondeur en itératif en utilisant la bibliothèque networkx :

  1. Écrire en langage Python une fonction parcours_largeur qui correspond à la fonction vue ci-dessus en langage naturel.

    • Penser à utiliser liste[0] pour obtenir le premier élément de la liste liste.

    • Penser à utiliser la méthode pop pour supprimer un élément d'une liste dont la position est connue tout en renvoyant l'élément supprimé.

  2. Tester cet algorithme de parcours en profondeur en prenant le graphe sur les pays d'Amérique du Sud.

  3. En vous aidant de la carte de l'Amerique du Sud ci-dessous, vérifier que la liste renvoyée correspond bien à un parcours en largeur.

Code de déblocage de la correction :

L'algorithme de parcours en profondeur nécessite une pile ; l'algorithme de parcours en largeur nécessite une file. Pour les implémenter nous avons utiliser dans des listes.

Pour supprimer des éléments de cette liste (pour dépiler et pour défiler), la méthode pop a été utilisée.

Cependant la complexité de cette méthode dans le cas où on défile est d'ordre linéaire. En effet, on supprime le premier élément de la liste et on doit décaler chacun des autres éléments.

Il existe d'autres structures de données en Python plus adaptée que les listes pour implémenter une file (ou une pile) :

  1. Utiliser l'objet deque du module collections afin d'implémentation la file du parcours en profondeur.
    Utiliser la méthode popleft() sur cet objet afin de défiler la tête de la file.
    La méthode append est une méthode existant aussi pour ce type d'objet et fonctionne comme pour les listes.

    Essayer d'utiliser aussi un dictionnaire pour marquer les sommets visités et faire en sorte que le script soit fonctionnel aussi pour des graphes orientés.

  2. En utilisant la documentation officielle, comparer le coût en temps de liste.pop(0) et de deque.popleft().

Code de déblocage de la correction :

Détection de cycles

Démarche

Vous avez vu dans les cours la notion d'arbres et de graphes et vous avez vu des algorithmes assez proches sur ces notions. Comme un arbre est un graphe n'ayant pas de cycle, il est intéressant d'avoir un algorithme qui permet de détecter la présence ou non de cycles dans un graphe.

Rappel :

Un cycle est une chaîne fermée dont les arêtes sont distinctes.

Si besoin, vous pourrez revoir les définitions sur les graphes accessibles ici.

On peut identifier la présence d'un cycle en retombant lors d'un parcours sur un sommet déjà visité.

Comme nous avions vu que l'on pouvait écrire l'algorithme de parcours en profondeur en récursif et en itératif, il est possible d'écrire un algorithme de recherche de cycles à la fois en récursif et en itératif.

Version itérative de la recherche de cycle :

L'idée est de reprendre une version itérative du parcours en profondeur comme par exemple la version déjà obtenue l'exercice accessible ici rappelée ci-dessous :

def parcourir_profondeur(G, s) :
    decouverte = {}
    for v in G:
        decouverte[v] = 'inconnu'
        for w in G[v]:
            if w not in G:
                decouverte[w] = 'inconnu'
    visites = [s]
    G[s].reverse()
    reste_a_voir = G[s]
    decouverte[s] = 'visite'
    while len(reste_a_voir) > 0 :
        u = reste_a_voir.pop(-1)
        if decouverte[u] == 'inconnu':
            decouverte[u] = 'visite'
            visites.append(u)
            if u in G.keys():
                for v in reversed(G[u]):
                    if decouverte[v] == 'inconnu':
                        reste_a_voir.append(v)
    return visites
  1. Écrire une fonction existe_cycle_iter qui prend deux paramètres :

    • G un graphe du type dictionnaire

    • s un sommet de ce graphe G.

    et qui renvoie un booléen suivant que le graphe G possède ou non un cycle lors d'un parcours en profondeur partant du sommet s.

  2. Tester cette fonction avec chacun des graphes de type dictionnaire donnés par les codes suivants :

    graphe1 = {}
    graphe1["A"] = ["B"]
    graphe1["B"] = ["D", "H"]
    graphe1["C"] = ["A", "F",  "G"]
    graphe1["D"] = ["E"]
    graphe1["E"] = ["A"]
    graphe1["G"] = ["H", "C"]
    graphe1["H"] = ["G"]
    
    graphe2 = {}
    graphe2["A"] = ["B", "C"]
    graphe2["B"] = ["D", "E"]
    graphe2["C"] = ["G", "H"]
    graphe2["E"] = ["F"]
                        
  3. Code de déblocage de la correction :

  4. On considère désormais le graphe orienté de type dictionnaire donné par le code suivant :

    graphe3 = {}
    graphe3["A"] = ["D", "E"]
    graphe3["B"] = ["A", "C"]
    graphe3["C"] = ["F", "G"]
    graphe3["F"] = ["C", "G"]
    graphe3["G"] = ["C", "F"]
                        

    Représenter à la main ce graphe orienté. Possède-t-il un cycle ?

  5. Que renvoie existe_cycle_iter(graphe3, 'A') ?

  6. Que renvoie existe_cycle_iter(graphe3, 'B') ?

  7. Comment utiliser la fonction existe_cycle_iter afin de s'assurer de l'existence ou non d'un cycle dans un graphe donné quelconque ?

  8. Code de déblocage de la correction :

Version récursive de la recherche de cycle :

Voici une version récursive du parcours en profondeur d'un graphe où celui-ci serait implémentée sous forme d'un dictionnaire :

def parcours_profondeur_recursif(graphe, sommet, visites):
    visites.append(sommet)
    if sommet in graphe.keys():
        for voisin in graphe[sommet]:
            if voisin not in visites:
                visites = parcours_profondeur_recursif(graphe, voisin, visites)
    return visites
  1. Modifier le fonction parcours_profondeur_recursif ci-dessus afin de créer une fonction existe_cycle qui :

    • prend en paramètres un graphe de type dictionnaire, un sommet du graphe, une liste visites et un booléen bool ;
      ce booléen bool vaudra False si aucun cycle n'est détecté et True sinon.

    • renvoie un tuple contenant une liste et un booléen.

  2. Tester la fonction existe_cycle en partant du sommet $A$ avec le graphe orienté donné ci-dessous :

    graphe1 = {}
    graphe1["A"] = ["B"]
    graphe1["B"] = ["D", "H"]
    graphe1["C"] = ["A", "F",  "G"]
    graphe1["D"] = ["E"]
    graphe1["E"] = ["A"]
    graphe1["G"] = ["H", "C"]
    graphe1["H"] = ["G"]
    
  3. Tester la fonction existe_cycle en partant du sommet $A$ avec le graphe orienté donné ci-dessous :

    graphe2 = {}
    graphe2["A"] = ["B", "C"]
    graphe2["B"] = ["D", "E"]
    graphe2["C"] = ["G", "H"]
    graphe2["E"] = ["F"]
    

Code de déblocage de la correction :

Chemin dans un graphe

Recherche d'un chemin en récursif

Trouver un chemin dans un graphe entre deux sommets donnés peut aussi être résolu grâce à des algorithmes.

Ce problème peut sembler compliqué dans le cas général.

Par contre, il est évident dans le cas où les deux sommets sont identiques.

De plus, on peut découper un grand chemin par une étape intermédiaire en utilisant un prédécesseur ou un successeur d'un des deux sommets connus.

Ces deux idées :

peuvent faire penser à utiliser la récursivité comme déjà vu dans ce cours. Ces idées pourraient donner l'idée à l'algorithme écrit ci-dessous en langage naturel ci-dessous :

fonction chemin_recursif(graphe G, sommet initial dep, sommet final arr) si les sommets initial et final sont égaux faire : renvoyer la liste réduite à un de ces sommets sinon: pour tous les sommets int voisins du sommet initial dep faire renvoyer la liste de premier terme dep est augmentée de chemin_recursif(graphe G, sommet int, sommet final arr)
  1. Commencer à exécuter à la main cet algorithme avec :

    • un graphe G défini par le dictionnaire suivant : G = {'A':['B', 'C'], 'B':['A']}.

    • pour trouver un chemin entre les sommets 'A' et 'C'.

  2. Quel problème constatez-vous ?

Code de déblocage de la correction :

Voici une version récursive améliorée :

fonction chemin_recursif(graphe G, sommet initial dep, sommet final arr, chemin initialement vide, liste des sommets interdit initialement vide) rajouter au chemin le sommet dep si les sommets initial et final sont égaux faire : renvoyer le chemin sinon: pour tous les sommets int voisins du sommet initial dep faire si int n'appartient pas au chemin : nouveau_chemin est le renvoi de chemin_recursif(graphe G, sommet int, sommet final arr, chemin, interdit) si nouveau_chemin n'est pas rien : renvoyer nouveau_chemin sinon : ajouter le sommet int aux sommets interdits enlever à chemin les sommets conduisant à une impasse par appel à epurer(liste, dep) renvoyer chemin_recursif(graphe G, sommet dep, sommet final arr, chemin, interdit) renvoyer rien

La fonction epurerutilisée dans l'algorithme précédent pour enlever les sommets correspondant à une impasse est définie ainsi :

fonction epurer(liste, sommet) tant que le dernier élément de la liste n'est pas sommet supprimer le dernier élément de la liste supprimer le dernier élément de la liste
  1. Écrire en langage Python la fonction epurer.

  2. Code de déblocage de la correction :

  3. Écrire en langage Python cette fonction chemin_recursif.

    Rien en langage Python s'écrit None.

  4. Tester cet algorithme avec le graphe suivant s'il existe un chemin entre les sommets 'A' et 'D' :

    graphe0 = {}
    graphe0["A"] = ["B", "C"]
    graphe0["B"] = ["A", "D"]
    graphe0["C"] = ["A", "D"]
    graphe0["D"] = ["B", "C"]
                        
  5. Tester cet algorithme avec le graphe suivant s'il existe un chemin entre les sommets 'B' et 'C' :

    graphe1 = {}
    graphe1["A"] = ["B"]
    graphe1["B"] = ["D", "H"]
    graphe1["C"] = ["A", "F",  "G"]
    graphe1["D"] = ["E"]
    graphe1["G"] = ["H", "C"]
    graphe1["H"] = ["G"]
                        
  6. Tester cet algorithme avec le graphe suivant s'il existe un chemin entre les sommets 'B' et 'C' :

    graphe2 = {}
    graphe2["A"] = ["B", "C"]
    graphe2["B"] = ["D", "E"]
    graphe2["C"] = ["G", "H"]
    graphe2["E"] = ["F"]
                        
  7. Code de déblocage de la correction :

  1. Créer une fonction existe_chemin de paramètres un graphe G de type dictionnaire et dep et arr deux sommets de ce graphe qui renvoie un booléen : True s'il existe un chemin dans le graphe reliant dep à arr, False sinon.

  2. Utiliser des graphes issus de l'exercice précédent pour tester la fonction existe_chemin.

  3. Code de déblocage de la correction :

  1. Sur quel parcours est formé l'algorithme récusif de recherche de chemin ?

  2. Que pensez-vous quant à la pertinence de ce type de parcours ?

Code de déblocage de la correction :

Recherche d'un chemin en itératif

On devine qu'un algorithme récursif risque de rapidement conduire à un dépassement de pile sous peu que le graphe possède un nombre assez conséquent de sommets.

De plus, il est peut sembler préférable de trouver aussi parmi tous les chemins qui existent celui le plus court, ici au sens du nombre de sommets intermédiaires entre les deux extrémités données.

Comme le parcours en largeur permet de savoir le nombre de sommets minimal nécessaire pour rejoindre un sommet quelconque au sommet initial, il est intéressant de partir de l'algorithme de parcours en largeur pour déterminer ce chemin de distance minimale. D'où :

On peut créer un algorithme de recherche de chemin entre un sommet de départ et un d'arrrivée en utilisant :

Pour rappel, un script parcours en largeur a été obtenu à cet exerciceG est un graphe de type dictionnaire.

Voici ci-dessous un script

def parcourir(G, depart, arrivee) :
    """
    G est un graphe implémenté par un dictionnaire
    depart est un sommet de ce graphe G, celui de départ
    arrivee est un sommet de ce graphe G, celui d'arrivée
    """
    predecesseur = {depart: None} # predecesseur est un dictionnaire associant à chaque sommet du graphe un sommet permettant de l\'atteindre directement
    reste_a_voir = [depart]                              
    while len(reste_a_voir)>0 :
        u = reste_a_voir.pop(0)                     
        if u == arrivee:                               
            return True                             
        if u in G.keys():                           
            for v in G[u]:                          
                if v not in predecesseur.keys():    
                    predecesseur[v] = u
                    reste_a_voir.append(v)               
    return False                  
                
  1. Commenter chaque ligne de ce script.

  2. À quel type de parcours correspond ce script ? Justifier.

  3. Tester ce script en cherchant l'existence d'un chemin entre les sommets "C" et "E" pour chacun des graphes suivants :

    graphe1 = {}
    graphe1["A"] = ["B"]
    graphe1["B"] = ["D", "H"]
    graphe1["C"] = ["A", "F",  "G"]
    graphe1["D"] = ["E"]
    graphe1["G"] = ["H", "C"]
    graphe1["H"] = ["G"]
                        

    puis :

    graphe2 = {}
    graphe2["A"] = ["B", "C"]
    graphe2["B"] = ["D", "E"]
    graphe2["C"] = ["G", "H"]
    graphe2["E"] = ["F"]
                        

Code de déblocage de la correction :

Le script précédent ne renvoie pas le chemin possible reliant deux sommets dans le cas où un tel chemin existe.
Le but de ce exercice est de compléter le script précédent afin d'obtenir un tel chemin. en utilisant le dictionnaire predecesseur modifié lors de l'utilisation de la fonction parcourir de l'exercice précédent.

  1. Modifier la fonction parcourir de l'exercice précédent pour qu'elle renvoie le booléen donnant l'existence d'un chemin mais aussi le dictionnaire predecesseur construit lors du parcours.

    Créer une fonction rechercher_chemin qui :

    • prend en paramètre un graphe (de type dictionnaire) (possiblement orienté) et deux sommets de celui-ci,

    • fait appel à la fonction parcourir de l'exercice précédent pour savoir si un tel chemin existe et pour connaître le dictionnaire predecesseur,

    • part du sommet d'arrivée et utilise le dictionnaire predecesseur pour aboutir au départ.

    • renvoie le chemin permettant de relier les deux sommets en cas d'existence sous forme d'une liste de sommets successifs.

    • renvoie une liste vide en cas d'absence de chemin possible.

  2. Tester ce script en cherchant l'existence d'un chemin entre les sommets "C" et "E" pour chacun des graphes suivants :

    graphe1 = {}
    graphe1["A"] = ["B"]
    graphe1["B"] = ["D", "H"]
    graphe1["C"] = ["A", "F", "G"]
    graphe1["D"] = ["E"]
    graphe1["G"] = ["H", "C"]
    graphe1["H"] = ["G"]
                        

    puis :

    graphe2 = {}
    graphe2["A"] = ["B", "C"]
    graphe2["B"] = ["D", "E"]
    graphe2["C"] = ["G", "H"]
    graphe2["E"] = ["F"]
                        

    représentant les graphes suivants : et

Code de déblocage de la correction :

L'algorithme obtenu précédemment, pour obtenir un chemin reliant deux sommets dans le cas où celui existe, n'est pas optimal en terme de coût. Comme vu dans certains exercices du chapitre, il est préférable d'utiliser un objet deque du module collections pour implémenter une file.

Exercices

Parcours

Voici ci-dessous la représentation d'un graphe non-orienté $G$ :

  1. Est-ce que la liste $[5, 6, 7, 4, 3, 1, 8, 2]$ est un parcours de ce graphe $G$ ? Pourquoi ?

  2. Est-ce que la liste $[5, 6, 3, 4, 7, 8, 1, 2]$ est un parcours de ce graphe $G$ ? Pourquoi ?

  3. Proposer un parcours en profondeur possible de ce graphe en partant de la racine 5. Est-il unique ? Pourquoi ?

  4. Est-ce que la liste $[5, 7, 8, 2, 1, 3, 4, 6]$ est un parcours en profondeur de ce graphe $G$ ? Pourquoi ?

  5. Est-ce que la liste $[5, 7, 6, 8, 4, 2, 1, 3]$ est un parcours en profondeur de ce graphe $G$ ? Pourquoi ?

  6. Proposer un parcours en largeur possible de ce graphe de racine 5. Est-il unique ? Pourquoi ?

  7. Est-ce que la liste $[1, 2, 3, 4, 5, 6, 7, 8]$ est un parcours en largeur de ce graphe $G$ ? Pourquoi ?

  8. Est-ce que la liste $[5, 6, 7, 2, 4, 8, 3, 1]$ est un parcours en largeur de ce graphe $G$ ? Pourquoi ?

Code de déblocage de la correction :

exercice de renforcement

Voici un graphe orienté.

source : Marie-José Huguet de l'INSA de Toulouse

  1. Suivre pas à pas l'algorithme de parcours en profondeur itératif avec trois couleurs travaillé dans cet exercice en partant du sommet $A$ pour appliquer l'effet progressif sur chacun des sommets de ce graphe.

    À chaque étape, montrer aussi comment évolue la pile.

  2. Déterminer le parcours en profondeur de ce graphe lorsque l'on part du sommet $A$.

Code de déblocage de la correction :

Voici un graphe orienté.

source : Marie-José Huguet de l'INSA de Toulouse

Pour rappel, voici une écriture possible en langage Puython du parcours en largeur ; écriture obtenu lors de cet exercice.

def parcourir_largeur(G, s) :
    couleur = {}
    for v in G:
        couleur[v] = 'blanc'
        for w in G[v]:
            if w not in G:
                couleur[w] = 'blanc'

    predecesseur = {}
    predecesseur[s] = None
    couleur[s] = 'gris'
    file = [s]
    while len(file) > 0 :
        u = file[0]
        succes = []
        if u in G:
            for v in G[u]:
                if couleur[v] == 'blanc':
                    succes.append(v)
        if len(succes) > 0 :
            v = succes[0]
            couleur[v] = 'gris'
            predecesseur[v] = u
            file.append(v)
        else :
            file.pop(0)
            couleur[u] = 'noir'
    return predecesseur
  1. Suivre pas à pas l'algorithme de parcours en largeur avec trois couleurs ci-dessus en partant du sommet $A$ pour appliquer l'effet progressif sur chacun des sommets de ce graphe.

    À chaque étape, montrer aussi comment évolue la file.

  2. Déterminer le parcours en largeur de ce graphe lorsque l'on part du sommet $A$.

Code de déblocage de la correction :

Exercice qui reprend la plupart des notions vues dans ce chapitre.

Vous êtes Ariane, fille de Minos, roi de Cnossos en Crète, et vous désirez aider Thésée ce grand héros à trouver le Minotaure enfermé dans le Labyrinthe construit par l'ingénieux Dédale puis a pouvoir en ressortir une fois le monstre tué.

Vous aviez comme première idée de lui donner une longue pelote de laine, qu'il déviderait tout au long de sa progression initiale afin que votre héros puisse à l'issu du combat retrouver la sortie. Mais un fil est si fragile ... Le sentiment que le vie de Thésée ne tienne qu'à un fil vous est insupportable alors vous imaginez un autre stratagème.

Vous expliquez à Thésée comment parcourir complétement le labyrinthe pour l'explorer, découvrir le monstre et enfin pouvoir ressortir, mais si Thésée est un héros courageux et vaillant, il ne brille pas par son intelligence. Plus d'autre choix : vous l'accompagnerez et vous gérerez l'exploration complète du labyrinthe tandis que Thésée gérera le monstre.

  1. Citez deux méthodes que vous connaissez pour explorer complètement le labyrinthe.

  2. Voici ci-dessous le plan que Dédale a suivi pourla construction du labyrinthe : chaque salle s'est vue attribuée une lettre et les deux carrefours un numéro.

    image d'un labyrinthe Source : Sylvie Borne

    Créer le graphe représentant le labyrinthe en l'implémentant à l'aide d'un dictionnaire dont les entrées seront les lettres des salles et les numéros de carrefours.

    Contrainte imposée : vous commencerez par les carrefours puis par les pièces en respectant l'ordre alphabétique.

  3. Implémenter la méthode qui permet de progresser le plus prudemment dans ce labyrinthe sous forme d'une fonction qui prend en paramètre un graphe implémenté comme à la question précédente et en sortie renvoie le parcours obtenu.

    Pour le parcours renvoyé, vous choisirez ce qui vous paraît le plus pertinent pour ressortir comme implémentation entre la liste des sommets visités ou un dictionnaire où à chaque salle ou numéro de carrefour est associé à la salle ou carrefour le précédent dans le parcours.

  4. Vous avez trouvé le Minotaure dans la salle M. Thésée a été formidable : le monstre est tué ; désormais la jeunesse d'Athènes ne sera plus en partie dévorée par cette abomination. Il vous reste à sortir Thésée et vous.

    Utilisez votre fonction précédente pour proposer un chemin qui vous ramenera à la salle A, seule issue possible de ce labyrinthe. Expliquez comment vous procédez.

  5. Vous sortez avec Thésée du labyrinthe. Vous proposez à Thésée d'en faire votre demeure : nul ne viendrez vous y importuner. Cependant, Thésée trouve qu'il n'est pas simple pour lui de trouver rapidement un chemin lui permettant d'aller profondément dans le labyrinthe. Pour le convaincre, vous lui expliquez le parcours en profondeur et proposez de l'appliquer ensemble.

    Implémenter le parcours en profondeur sous forme d'une fonction qui prend en paramètre un graphe implémenté comme à la première question et en sortie renvoie le parcours obtenu.

    Pour le parcours renvoyé, vous choisirez ce qui vous paraît le plus pertinent pour ressortir comme implémentation entre la liste des sommets visités ou un dictionnaire où à chaque salle ou numéro de carrefour est associé à la salle ou carrefour le précédant dans le parcours.

  6. Thésée vous demande de tester votre programme pour faire l'aller-retour entre les salles A et I.

  7. Thésée trouve que le chemin obtenu avec le parcours en profondeur est parfois long, comme celui menant de "A" à "L" : ["A", "B", "C", "I", "H", "K", "J", "M", "2", "L"] ; Thésée se lasse vite...

    Pouvez-vous proposer une fonction nommée chemin qui prend en paramètre un graphe implémenté comme lors de la première question, deux sommets correspondant respectivement au départ et à l'arrivée, fonction qui renvoie le chemin à suivre pour aller directement du sommet de départ au sommet d'arrivée ?

    Réalisez une telle fonction car sinon Thésée risque d'abandonner votre projet.

Code de déblocage de la correction :

Savoirs et savoirs-faire

  1. savoir la notion de parcours sur un graphe,

  2. savoir la notion de cycle sur un graphe,

  3. savoir la notion de chemin sur un graphe,

  1. savoir appliquer le parcours en profondeur sur un graphe donné,

  2. savoir appliquer le parcours en largeur sur un graphe donné,

  3. savoir écrire en langage Python un parcours en profondeur (itératif ou récursif),

  4. savoir écrire en langage Python un parcours en largeur,

  5. modéliser un labyrinthe par un graphe,

  6. savoir utiliser le module networkx pour implémenter et étudier un graphe.

  7. savoir utiliser les dictionnaire pour implémenter et étudier un graphe.

Sitographie

Voici quelques liens:

Licence Creative Commons
Les différents auteurs mettent l'ensemble du site à disposition selon les termes de la licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International