Dans un graphe non pondéré, le parcours en largeur permet de trouver un chemin de distance optimale entre votre sommet de départ et tous les autres sommets du graphe. Cet algorithme utilise une File.
Nous allons voir aujourd'hui le parcours en profondeur qui va nous permettre lui d'obtenir d'autres informations sur la structure du graphe. On pourra trouver tous les chemins pour aller d'un sommet à un autre. Cet algorithme utilise une Pile (soit une Pile implémentée, soit la Pile des appels récursifs)
Attention :cette activité est en deux parties. Aujourd'hui, on découvre l'algorithme et son déroulement. Mais vous aurez du mal à voir à quoi il sert car il est incomplet. Nous verrons juste qu'il permet de détecter la présence de cycle dans un graphe.
Logiciel nécessaire pour l'activité : -
Prérequis :
Algo : Parcours en largeur d'un Graphe
Algo : Implémentation Python du parcours en largeur
Vous allez voir que ce parcours illustre très bien ce qu'on pourrait faire en étant enfermé dans un labyrinthe. On place une marque dans la pièce où on se trouve. Dès qu'on rentre dans une nouvelle salle, on la marque. Si on arrive dans une salle déjà visitée que faire ? Simplement retourner en arrière jusqu'à trouver une arête non utilisée.
Vous allez pouvoir visualiser le principe sur le labyrinthe suivant : on suit un chemin et lorsqu'on atteint un cul de sac ou une case qu'on a déjà exploré, on revient au plus récent embranchement non visité.
Vidéo réalisée par le contributeur Purpy Pupple et tirée de l'article Wikipedia suivant parours en profondeur
Si on avait utilisé un parcours en largeur, nous aurions découvert le labyrinthe sur un rayon de plus en plus grand autour du point de départ.
2.1 Principe du parcours en profondeur dans un graphe
On commence par ordonner les sommets entre eux : nous allons devoir lancer un parcours en prenant tour à tour chacun des sommets comme point de départ. Pour info, avec le parcours en largeur, on ne part que d'un sommet unique.
On commence par un sommet choisi (S5:[S1-S9] pour la liste d'adjacence).
On choisit S1 car il est non visité. On continue avec S1:[S2-S3-S5].
On choisit S2 car il est non visité. On continue avec S2:[S1-S3-S4-S6].
On ne gère pas pas S1 déjà connu mais S3 car il est non visité. On continue avec S3:[S1-S2-S4]...
CLIQUER SUR L'IMAGE pour ANIMER ou STOPPER
Pour gèrer informatiquement le parcours, nous allons utiliser les attributs suivants :
un attribut couleur pour préciser l'état du sommet lors de l'exploration :
BLANC : le sommet est non découvert.
GRIS : le sommet a été découvert
NOIR : le sommet a été traité (on a exploré toutes ses arêtes).
un attribut parent qui contient le sommet depuis lequel on a découvert ce sommet. VIDE au départ de l'exploration. Seul le sommet de départ gardera cette valeur puisqu'il est le premier.
Algorithme de parcours_en_profondeur
Voici l'algorithme en français du parcours_en_profondeur :
INITIALISER : Pour chaque sommet u appartenant à l'ensemble S des sommets :
on place BLANC dans couleur et
on place VIDE dans parent
PARCOURIR : Pour chaque sommet u appartenant à l'ensemble S des sommets :
Si u est BLANC
On appelle visiter_en_profondeur() sur ce sommet u
Remarque : on ne choisit pas vraiment un sommet de départ comme avec le parcours en largeur. On va lancer le parcours en profondeur sur chaque des sommets comme s'il était le point de départ.
Algorithme de visiter_en_profondeur (version récursive)
Voici l'algorithme de la fonction visiter_en_profondeur sur ce sommet u :
On modifie l'attribut couleur de u à GRIS car on va commencer son traitement
Pour chaque sommet v appartenant à la liste d'adjacence de u :
Si v est BLANC
On signale que le parent de v est u
On appelle visiter_en_profondeur sur ce sommet v
On modifie l'attribut couleur de u à NOIR puisqu'on a testé toutes ses arêtes ou arcs
2.2 Exemple de déroulement de l'algorithme de parcours en profondeur
On considère le graphe suivant en prenant le sommet 5 comme point de départ : on considéra par l'exemple que les sommets du graphe sont stockés dans la liste suivante :
S5 → S6 → S7 → S8 → S9 → S1 → S2 → S3 → S4
Etape initiale
On place tous les parents à VIDE et tous les noeuds en BLANC.
D'après notre liste des sommets, le premier sommet u sera S5.
Les listes d'adjacence sont placées à proximité des sommets pour plus de facilité de lecture.
Appel de visiter_en_profondeur(S5)
S5 est BLANC, on commence son parcours : appel à visiter_en_profondeur(S5).
On le peint en GRIS.
On prend le premier sommet blanc de la liste d'adjacence : S1.
on impose S1.parent = S5(on commence ainsi à tracer un arbre de parcours)
On lance l'appel récursif à visiter_en_profondeur(S1).
On voit à droite la création d'un Arbre de parcours.
La pile des appels donne :
Appel de visiter_en_profondeur(S5)
Appel de visiter_en_profondeur(S1)
Appel de visiter_en_profondeur(S1)
On peint S1 en GRIS.
On prend le premier sommet blanc de la liste d'adjacence : S2.
on impose S2.parent = S1 : voir l'arbre ci-dessous.
On lance l'appel récursif de visiter_en_profondeur(S2).
On voit à droite l'Arbre de parcours. La pile des appels donne :
Appel de visiter_en_profondeur(S5)
Appel de visiter_en_profondeur(S1)
Appel de visiter_en_profondeur(S2)
Appel de visiter_en_profondeur(S2)
On peint S2 en GRIS.
S1 n'est pas blanc : on ne fait rien.
S3 est BLANC.
on impose S3.parent = S2 : voir l'arbre ci-dessous.
On lance l'appel récursif visiter_en_profondeur(S3).
On voit à droite l'Arbre de parcours. La pile des appels donne :
Appel de visiter_en_profondeur(S5)
Appel de visiter_en_profondeur(S1)
Appel de visiter_en_profondeur(S2)
Appel de visiter_en_profondeur(S3)
Appel de visiter_en_profondeur(S3)
On peint S3 en GRIS.
On teste les premiers sommets mais ils sont GRIS.
S4 est BLANC, on le traite.
on impose S4.parent = S3 : voir l'arbre ci-dessous.
On lance l'appel récursif visiter_en_profondeur(S4).
On voit à droite l'Arbre de parcours. La pile des appels donne :
Appel de visiter_en_profondeur(S5)
Appel de visiter_en_profondeur(S1)
Appel de visiter_en_profondeur(S2)
Appel de visiter_en_profondeur(S3)
Appel de visiter_en_profondeur(S4)
Appel de visiter_en_profondeur(S4)
On peint S4 en GRIS.
Les premiers sommets de la liste d'adjacence ne sont pas BLANC, on ne fait rien !
S7 est BLANC, on commence son traitement.
on impose S7.parent = S4 : voir l'arbre ci-dessous.
On lance l'appel récursif visiter_en_profondeur(S7).
On voit à droite l'Arbre de parcours. La pile des appels donne :
Appel de visiter_en_profondeur(S5)
Appel de visiter_en_profondeur(S1)
Appel de visiter_en_profondeur(S2)
Appel de visiter_en_profondeur(S3)
Appel de visiter_en_profondeur(S4)
Appel de visiter_en_profondeur(S7)
Appel de visiter_en_profondeur(S7)
On peint S7 en GRIS.
S4 est GRIS, on ne fait rien !
S6 est BLANC, on commence son traitement :
on impose S6.parent = S7 : voir l'arbre ci-dessous.
On lance l'appel récursif visiter_en_profondeur(S6).
On voit à droite l'Arbre de parcours. La pile des appels donne :
Appel de visiter_en_profondeur(S5)
Appel de visiter_en_profondeur(S1)
Appel de visiter_en_profondeur(S2)
Appel de visiter_en_profondeur(S3)
Appel de visiter_en_profondeur(S4)
Appel de visiter_en_profondeur(S7)
Appel de visiter_en_profondeur(S6)
Appel de visiter_en_profondeur(S6)
On peint S6 en GRIS.
Les premiers sommets de la liste d'adjacence sont GRIS, on ne fait rien !
S8 est BLANC, on commence son traitement :
on impose S8.parent = S6 : voir l'arbre ci-dessous.
On lance l'appel récursif visiter_en_profondeur(S8).
On voit à droite l'Arbre de parcours. La pile des appels donne :
Appel de visiter_en_profondeur(S5)
Appel de visiter_en_profondeur(S1)
Appel de visiter_en_profondeur(S2)
Appel de visiter_en_profondeur(S3)
Appel de visiter_en_profondeur(S4)
Appel de visiter_en_profondeur(S7)
Appel de visiter_en_profondeur(S6)
Appel de visiter_en_profondeur(S8)
Appel de visiter_en_profondeur(S8)
On peint S8 en GRIS.
S6 est GRIS, on ne fait rien !
S9 est BLANC, on commence son traitement :
on impose S9.parent = S8 : voir l'arbre ci-dessous.
On lance l'appel récursif visiter_en_profondeur(S9).
On voit à droite l'Arbre de parcours. La pile des appels donne :
Appel de visiter_en_profondeur(S5)
Appel de visiter_en_profondeur(S1)
Appel de visiter_en_profondeur(S2)
Appel de visiter_en_profondeur(S3)
Appel de visiter_en_profondeur(S4)
Appel de visiter_en_profondeur(S7)
Appel de visiter_en_profondeur(S6)
Appel de visiter_en_profondeur(S8)
Appel de visiter_en_profondeur(S9)
Appel de visiter_en_profondeur(S9)
On peint S9 en GRIS.
Tous les sommets de la liste d'adjacence sont GRIS, on ne fait rien !
Nous avons fini toutes les itérations sur la liste d'adjacence du sommet S9.
On peint S9 en NOIR.
L'appel à visiter_en_profondeur(S9) est terminé et elle renvoie None.
On dépile donc et on revient à l'appel précédent : visiter_en_profondeur(S8)
On voit à droite l'Arbre de parcours. La pile des appels donne :
Appel de visiter_en_profondeur(S5)
Appel de visiter_en_profondeur(S1)
Appel de visiter_en_profondeur(S2)
Appel de visiter_en_profondeur(S3)
Appel de visiter_en_profondeur(S4)
Appel de visiter_en_profondeur(S7)
Appel de visiter_en_profondeur(S6)
Appel de visiter_en_profondeur(S8)
Retour à visiter_en_profondeur(S8)
La liste d'adjacence de S8 est traitée.
On peint S8 en NOIR.
L'appel à visiter_en_profondeur(S8) est terminé et elle renvoie None.
On dépile donc et on revient à l'appel précédente : visiter_en_profondeur(S6)
Appel de visiter_en_profondeur(S5)
Appel de visiter_en_profondeur(S1)
Appel de visiter_en_profondeur(S2)
Appel de visiter_en_profondeur(S3)
Appel de visiter_en_profondeur(S4)
Appel de visiter_en_profondeur(S7)
Appel de visiter_en_profondeur(S6)
Retour à visiter_en_profondeur(S6)
La liste d'adjacence de S6 est traitée.
On peint S6 en NOIR.
L'appel à visiter_en_profondeur(S6) est terminé et elle renvoie None.
On dépile donc et on revient à l'appel précédente : visiter_en_profondeur(S7)
Appel de visiter_en_profondeur(S5)
Appel de visiter_en_profondeur(S1)
Appel de visiter_en_profondeur(S2)
Appel de visiter_en_profondeur(S3)
Appel de visiter_en_profondeur(S4)
Appel de visiter_en_profondeur(S7)
Retour à visiter_en_profondeur(S7)
La liste d'adjacence de S7 est terminée.
On peint S7 en NOIR.
L'appel à visiter_en_profondeur(S7) est terminé et elle renvoie None.
On dépile donc et on revient à l'appel précédente : visiter_en_profondeur(S4)
Appel de visiter_en_profondeur(S5)
Appel de visiter_en_profondeur(S1)
Appel de visiter_en_profondeur(S2)
Appel de visiter_en_profondeur(S3)
Appel de visiter_en_profondeur(S4)
Retour à visiter_en_profondeur(S4)
La liste d'adjacence de S4 est terminée.
On peint S4 en NOIR.
L'appel à visiter_en_profondeur(S4) est terminé et elle renvoie None.
On dépile donc et on revient à l'appel précédente : visiter_en_profondeur(S3)
Appel de visiter_en_profondeur(S5)
Appel de visiter_en_profondeur(S1)
Appel de visiter_en_profondeur(S2)
Retour à visiter_en_profondeur(S3)
La liste d'adjacence de S3 est terminée.
On peint S3 en NOIR.
L'appel à visiter_en_profondeur(S3) est terminé et elle renvoie None.
On dépile donc et on revient à l'appel précédente : visiter_en_profondeur(S2)
Appel de visiter_en_profondeur(S5)
Appel de visiter_en_profondeur(S1)
Appel de visiter_en_profondeur(S2)
Retour à l'appel de visiter_en_profondeur(S2)
On reprend la liste d'adjacence avec S4, puisqu'il est NOIR, on ne fait rien !
S6 est NOIR, on ne fait rien !
Nous avons fini toutes les itérations sur la liste d'adjacence du sommet S2.
On peint S2 en NOIR.
L'appel à visiter_en_profondeur(S2) est terminé et elle renvoie None.
On dépile donc et on revient à l'appel précédente : visiter_en_profondeur(S1)
On voit à droite l'Arbre de parcours. La pile des appels donne :
Appel de visiter_en_profondeur(S5)
Appel de visiter_en_profondeur(S1)
Retour à l'appel de visiter_en_profondeur(S1)
La liste d'adjacence continue avec S3 qui est NOIR, on ne fait rien !
S5 est GRIS, on ne fait rien !
Nous avons fini toutes les itérations sur la liste d'adjacence du sommet S1.
On peint S1 en NOIR.
L'appel à visiter_en_profondeur(S1) est terminé et elle renvoie None.
On dépile donc et on revient à l'appel précédente : visiter_en_profondeur(S5)
On voit à droite l'Arbre de parcours. La pile des appels donne :
Appel de visiter_en_profondeur(S5)
Retour à l'appel de visiter_en_profondeur(S5)
La liste d'adjacence fournit S9qui est NOIR, on ne fait rien !
Nous avons fini toutes les itérations sur la liste d'adjacence du sommet S5.
On peint S5 en NOIR.
L'appel à visiter_en_profondeur(S5) est terminé et elle renvoie None.
On dépile donc et on revient à la boucle sur les sommets du graphes.
Nous avons traité le sommet S5
On passe au même traitement pour S6 mais tous les sommets de sa liste d'adjacence sont NOIR. Du coup, ça va plus vite : on ne fait rien. Comme tous les sommets sont déjà NOIR sur cet exemple, on va donc devoir itérer sommet par sommet, même si ici on sait qu'on ne fera plus rien. Mais nous verrons plus bas d'autres exemples où cela sera utile.
CLIQUER SUR L'IMAGE pour ANIMER ou STOPPER
A partir de là, toutes les arêtes ont été explorées. Nous avons donc parcouru l'intégralité du graphe.
On obtient au final :
Un Arbre si le graphe est connexe ou plusieurs Arbres si le graphe n'est pas connexe (on parle alors de forêt).
Notre Arbre est d'ailleurs filiforme ici et permettrait de partir du sommet S5 et d'y revenir en passant une seule fois par tous les autres sommets du graphe. On parle donc de cycle hamiltonien (on passe une seule fois par chaque sommet).
3.3 Questions de compréhension
✎ 01° Sur l'Arbre de parcours obtenu, quel est l'enchaînement de sommets obtenu pour aller du sommet S5 au sommet S6 ?
✎ 02° S'agit-il d'un chemin minimum en terme de nombre d'arêtes comme avec le parcours en largeur ?
✎ 03° Regardons si l'ordre des sommets dans les listes d'adjacence a une importante. Réaliser le parcours en profondeur sur ce "nouveau" graphe. Comparer votre Arbre de parcours à l'ancien Arbre.
...CORRECTION...
04° On utilise une fois chaque sommet comme centre de recherches. Combien de fois utilise-t-on les arêtes ?
On utilise une fois chaque arête
On utilise deux fois chaque arête
On utilise trois fois chaque arête
J'aime ni les arêtes, ni le poisson
...CORRECTION...
On utilise les arêtes dans les deux sens. Donc deux fois.
05° Nous allons chercher la complexité de cet algorithme en prenant comme référence le nombre de fois où on teste si un sommet est BLANC. Notons a le nombre d'arêtes. La complexité de cet algorithme est :
Logarithmique en fonction de a ?
Linéaire en fonction de a ?
Quadratique en fonction de a ?
Exponentielle en fonction de a ?
...CORRECTION...
Puisqu'on utilise deux fois les arêtes, on peut noter Θ(2a). Comme on ne s'intéresse pas au facteur multiplicatif, on obtient donc Θ(a). La bonne réponse est donc linéaire.
Le coût total d'exécution dépend en réalité du nombre de sommets et du nombre d'arêtes. A cause de la boucle initiale sur les sommets, l'algorithme assure qu'on explore chaque sommet même en cas de graphe non connexe.
On peut donc écrire 𝞗(s+a)
On rappele que pour l'algorithme de parcours en largeur, on écrit simplement 𝞞(s+a) car si le graphe est non connexe, on ne passe pas forcément par tous les sommets et toutes les arêtes.
06° D'autres listes d'adjacences : vous devriez voir qu'on peut avoir un arbre non filiforme même avec un graphe connexe.
...CORRECTION...
07° Est-ce qu'on peut trouver le plus court chemin (en nombre d'arêtes) avec cet algorithme ? A quoi peut-il servir ?
...CORRECTION...
Non : le parcours en profondeur ne permet pas de trouver le plus court chemin en terme d'arêtes ou d'arcs.
Nous allons voir qu'il permet par contre d'apprendre beaucoup de choses sur la forme et la topologie du graphe.
08° Quelle va être la forme de la forêt obtenue avec ce graphe ? (la seule différence vient du fait que les sommets 4 et 7 sont isolés des autres)
...CORRECTION...
Bien entendu avec des graphes non orientés, la seule possibilité d'obtenir un graphe non connexe est que certains sommets soient isolés des autres. C'est donc visible très facilement. Dans les exercices, nous verrons qu'avec les graphes orientés, c'est moins évident à voir sans lancer un parcours en profondeur.
Aucune ici mais on peut facilement modifier l'algorithme pour qu'il renvoie par exemple l'Arbre ou la Forêt du parcours. En réalité ici, on stocke l'arbre directement via les sommets : on leur attribue un parent.
ALGORITHME PARCOURS EN PROFONDEUR
on initialise tous les sommets
POUR chaque sommet u appartenant au graphe g
u.couleur ← BLANC
u.parent ← VIDE
Fin Pour
on lance le traitement des sommets un par un
POUR chaque sommet u appartenant au graphe g
SIu.couleur est BLANC
si on arrive ici, c'est que le sommet n'a pas encore été découvert
visiter_en_profondeur(u)
Fin Si
Fin Pour
RenvoyerVIDE (∅)
ALGORITHME de visiter_en_profondeur(u)
u.couleur ← GRIS
POUR chaque sommet v de la liste d'adjacence du sommet u
SIv.couleur est BLANC
si on arrive ici, c'est que le sommet n'a pas encore été visité
Nous allons maintenant travailler sur des graphes non pondérés mais orientés. Plus de chances d'obtenir une forêt de parcours.
✎ 09° Explorer en profondeur ce graphe orienté pour tracer son arbre ou sa forêt de parcours.
Tiré de Algorithmique, Cormen-Leiserson-Rivest-Stein
...CORRECTION...
✎ 10° Explorer en profondeur ce graphe orienté pour tracer son arbre ou sa forêt de parcours.
Tiré de Algorithmique, Cormen-Leiserson-Rivest-Stein
...CORRECTION...
✎ 11° Compléter le dictionnaire graphe_test pour qu'il représente bien le graphe ci-dessous.
On fournira les clés dans l'ordre voulu par le parcours de façon à profiter de la propriété des dictionnaires Python de lire les clés dans l'ordre de leur insertion. Attention, ce n'est pas le cas avec tous les dictionnaires.
1
2
3
4
5
graphe_test={5:[9, 1],6: ...
...
}
✎ 12° Réaliser une implémentation de cet algorithme en utilisant un graphe représenté comme un dictionnaire dont les clés sont les identifiants des sommets et les valeurs sont les listes d'adjacence.
Attention, comme avec le parcours en largeur, on utilisera un dictionnaire parcours pour stocker les attributs du parcours plutôt que de modifier le graphe.
Votre fonction devra donc renvoyer le dictionnaire contenant ces informations.
# CONSTANTES ======================================================================BLANC=0GRIS=1NOIR=2# FONCTIONS ======================================================================defparcours_profondeur(g:'dict[int, list]')->dict:"""Renvoie les informations (les parents) du parcours en profondeur"""# INITIALISATIONparcours={}# Création du dictionnaire (qui sera un dict de dict)foruing.keys():# Pour chaque sommet du grapheparcours[u]={}# La clé u de parcours a comme valeur associée un dict parcours[u]['couleur']=BLANC# Initialisation de la couleurparcours[u]['parent']=None# Initialisation du parent# PARCOURIRforuing.keys():# Pour chaque sommet du grapheifparcours[u]['couleur']==BLANC:# S'il est encore Non découvertvisiter_profondeur(u,g,parcours)# Visite lereturnparcoursdefvisiter_profondeur(u:int,g:'dict[int, list]',parcours:dict)->None:"""Visite un sommet u en particulier"""parcours[u]['couleur']=GRIS# Signale que u est découvertforving[u]:# Pour chaque sommet v de la liste d'adj de uifparcours[v]['couleur']==BLANC:# Si v est non découvertparcours[v]['parent']=u# u est son parentvisiter_profondeur(v,g,parcours)# on lance la visite de vparcours[u]['couleur']=NOIR# u est totalement explorédefdonner_chemin(sommet_initial,sommet_final,parcours:dict)->list:"""Renvoie une liste des sommets permettant d'aller de initial vers final"""reponse=[]ifsommet_initialinparcours.keys()andsommet_finalinparcours.keys():sommet=sommet_finalwhile(sommetisnotNone)andnot(sommet_initialinreponse):reponse.append(sommet)sommet=parcours[sommet]['parent']inversion=[]ifsommet_initialinreponseandsommet_finalinreponse:whilereponse:inversion.append(reponse.pop())returninversion# PROGRAMME PRINCIPAL =========================================================if__name__=='__main__':graphe={5:[9,1],6:[2,7,8],7:[4,6],8:[6,9],9:[5,8],1:[3,2,5],2:[3,1,4,6],3:[1,2,4],4:[2,3,7]}parcours=parcours_profondeur(graphe)print(parcours)print("9 vers 2 : ",donner_chemin(9,2,parcours))print("9 vers 5 : ",donner_chemin(9,5,parcours))
✎ 13° Idem mais avec un tableau decouverts plutôt que les couleurs.
# FONCTIONS ======================================================================defparcours_profondeur(g:'dict[int, list]')->dict:"""Renvoie les informations (les parents) du parcours en profondeur"""# INITIALISATIONd=[]# Tableau des sommets découvertsparcours={}# Création du dictionnaire (qui sera un dict de dict)foruing.keys():# Pour chaque sommet du grapheparcours[u]={'parent':None}# Association clé u à un nouveau dict# PARCOURIRforuing.keys():# Pour chaque sommet u du grapheifnot(uind):# Si u n'est encore découvertvisiter_profondeur(u,g,parcours,d)# Visite le sommet ureturnparcoursdefvisiter_profondeur(u:int,g:'dict[int, list]',parcours:dict,d:list)->None:"""Visite un sommet u en particulier"""d.append(u)# Signale que u est découvertforving[u]:# Pour chaque sommet v de la liste d'adj de uifnot(vind):# Si v est non découvertparcours[v]['parent']=u# u est son parentvisiter_profondeur(v,g,parcours,d)# on lance la visite de v# u est totalement exploré mais on ne l'implémente pasdefdonner_chemin(sommet_initial,sommet_final,parcours:dict)->list:"""Renvoie une liste des sommets permettant d'aller de initial vers final"""reponse=[]ifsommet_initialinparcours.keys()andsommet_finalinparcours.keys():sommet=sommet_finalwhile(sommetisnotNone)andnot(sommet_initialinreponse):reponse.append(sommet)sommet=parcours[sommet]['parent']inversion=[]ifsommet_initialinreponseandsommet_finalinreponse:whilereponse:inversion.append(reponse.pop())returninversion# PROGRAMME PRINCIPAL =========================================================if__name__=='__main__':graphe={5:[9,1],6:[2,7,8],7:[4,6],8:[6,9],9:[5,8],1:[3,2,5],2:[3,1,4,6],3:[1,2,4],4:[2,3,7]}parcours=parcours_profondeur(graphe)print(parcours)print("9 vers 2 : ",donner_chemin(9,2,parcours))print("9 vers 5 : ",donner_chemin(9,5,parcours))
✎ 14° Simplifier encore l'algorithme : on ne veut pas récupérer les informations sur le parcours mais uniquement le tableau decouverts qui va permettre de savoir dans quel ordre les sommets ont été découverts.
# FONCTIONS ======================================================================defparcours_profondeur(g:'dict[int, list]')->list:"""Renvoie la tableau des sommets découverts lors du parcours en profondeur"""# INITIALISATIONd=[]# Tableau des sommets découverts# PARCOURIRforuing.keys():# Pour chaque sommet u du grapheifnot(uind):# Si u n'est encore découvertvisiter_profondeur(u,g,d)# Visite le sommet ureturnddefvisiter_profondeur(u:int,g:'dict[int, list]',d:list)->None:"""Visite un sommet u en particulier"""d.append(u)# Signale que u est découvertforving[u]:# Pour chaque sommet v de la liste d'adj de uifnot(vind):# Si v est non découvertvisiter_profondeur(v,g,d)# on lance la visite de v# u est totalement exploré mais on ne l'implémente pas# PROGRAMME PRINCIPAL =========================================================if__name__=='__main__':graphe={5:[9,1],6:[2,7,8],7:[4,6],8:[6,9],9:[5,8],1:[3,2,5],2:[3,1,4,6],3:[1,2,4],4:[2,3,7]}decouverts=parcours_profondeur(graphe)print(decouverts)
✎ 15° Exercice Type 2 de l'épreuve pratique. Compléter la fonction pour qu'elle implémente bien un parcours en profondeur en impératif : on utilise une simple list Python pour réaliser la Pile.
# FONCTIONS ======================================================================defparcours_profondeur(g:'dict[int, list]')->list:"""Renvoie le tableau des sommets découverts lors du parcours en profondeur"""# INITIALISATIONd=[]# Tableau des sommets découverts# PARCOURIRforuin ... # Pour chaque sommet u du graphe# On remplace la pile d'appels par une vraie Pilepile= ... # Création d'une Pile vide
... # On empile u# Equivalent impératif de visiter(u)whilepile:# Tant que la pile n'est pas vides= ... # On dépile le sommet s suivantif ...:# Si s est non découvert
... # Signale que s est découvertforvin ...:# Pour chaque sommet v de la liste d'adj de s
... # On empile vreturnd# PROGRAMME PRINCIPAL =========================================================if__name__=='__main__':graphe={5:[1,9],# [9, 1] en récursif6:[8,7,2],# [2, 7, 8] en récursif7:[6,4],# [4, 6] en récursif8:[9,6],# [6, 9] en récursif9:[8,5],# [5, 8] en récursif1:[3,2,5],# [5, 2, 3] en récursif2:[6,4,1,3],# [3, 1, 4, 6] en récursif3:[4,2,1],# [1, 2, 4] en récursif4:[2,3,7]# [7, 3, 2] en récursif}decouverts=parcours_profondeur(graphe)print(decouverts)
# FONCTIONS ======================================================================defparcours_profondeur(g:'dict[int, list]')->list:"""Renvoie le tableau des sommets découverts lors du parcours en profondeur"""# INITIALISATIONd=[]# Tableau des sommets découverts# PARCOURIRforuing.keys():# Pour chaque sommet u du graphe# On remplace la pile d'appels par une vraie Pilepile=[]# Création d'une Pile videpile.append(u)# On empile u# Equivalent impératif de visiter(u)whilepile:# Tant que la pile n'est pas vides=pile.pop()# On dépile le sommet s suivantifnot(sind):# Si s est non découvertd.append(s)# Signale que s est découvertforving[s]:# Pour chaque sommet v de la liste d'adj de spile.append(v)# On empile vreturnd# PROGRAMME PRINCIPAL =========================================================if__name__=='__main__':graphe={5:[1,9],# [9, 1] en récursif6:[8,7,2],# [2, 7, 8] en récursif7:[6,4],# [4, 6] en récursif8:[9,6],# [6, 9] en récursif9:[8,5],# [5, 8] en récursif1:[3,2,5],# [5, 2, 3] en récursif2:[6,4,1,3],# [3, 1, 4, 6] en récursif3:[4,2,1],# [1, 2, 4] en récursif4:[2,3,7]# [7, 3, 2] en récursif}decouverts=parcours_profondeur(graphe)print(decouverts)
