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

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

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.

On reprend le labyrinthe et son graphe :

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.

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

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 ?

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

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 :

1. Pourquoi est-ce bien une procédure récursive ?

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

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 :

• utiliser un graphe implémenté comme dictionnaire avec la liste des successeurs, représentant les pays frontaliers d'Amérique du Sud,

• programmer un parcours en profondeur,

• l'appliquer au voyage de votre rêve !

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

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

Code de déblocage de la correction :

2. 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'

Code de déblocage de la correction :

3. É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.

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

   

5. 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 :

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

Code de déblocage de la correction :

2. 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 ?

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

Code de déblocage de la correction :

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

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

Code de déblocage de la correction :

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

2. 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"]
              

   Code de déblocage de la correction :

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

      

   3. 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 ?

      

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

   5. 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é.

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

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 :

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 :

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

Quelle différence remarquez-vous ?

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

Code de déblocage de la correction :

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

     

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

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']
           }

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

Code de déblocage de la correction :

3. 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 ?

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

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

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

Code de déblocage de la correction :

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 ?

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.

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 ?

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

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 ?

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

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