On a coutume de dire que pour sortir d'un labyrinthe il suffit de toujours suivre le mur situé sur notre droite.
En particulier, on emprunte ainsi toujours la première porte que l'on rencontre sur notre droite et, si on arrive à un cul de sac, cela a pour effet de nous faire faire un demi-tour.
Ceux qui ont un peu réfléchi à cette idée, voire qui ont essayé de la mettre
en pratique, savent plusieurs choses.
D'une part, cette méthode peut échouer
dans certains cas, où on se retrouve à « tourner en rond » autour d'un bloc.
Pour y remédier, ü suffit de marquer au sol les endroits par lesquels on est déjà passé.
Dès lors, quand on revient sur un embranchement qui est marqué, on procède comme s'il s'agissait d'un cul de sac.
D'autre part, on peut tout aussi bien suivre le mur sur la gauche plutôt que sur la droite.
On peut même changer d'avis à chaque nouvelle salle et emprunter à sa guise
n'importe laquelle des portes qui la quittent.
Ces deux idées combinées, à savoir emprunter les embranchernents de façon arbitraire et marquer les endroits par lesquels on est déjà passé, constituent un algorithme fondamental appelé parcours en profondeur. Il s'applique à n'importe quel graphe et permet de déterminer tous les sommets
![\"graphe10.png](\"https://sciencesappliquees.com/images/nsi/graphe9.png\")
| sommet visité | action |
A .B ..C ...E ....B ...E ..C ...F ..C .B A .D ..E .D A | marquer A, emprunter arc A—>B marquer B, emprunter arc B—>C marquer C, emprunter arc C—>E marquer E, emprunter arc E—>B déjà vu, terminé pas d'autre arc, terminé emprunter arc C—>F marquer F, aucun arc, terminé pas d'autre arc, terminé pas d'autre arc, terminé emprunter arc A—>D marquer D, emprunter arc D—>E déjà vu, terminé pas d'autre arc, terminé pas d'autre arc, terminé |
Figure 1 — Parcours en profondeur, à partir du sommet A.
Avant de programmer le parcours en profondeur en Python, illustrons
son fonctionnement en détail sur un exemple. La figure 1 détaille les
différentes étapes du parcours en profondeur du graphe à partir du sommet A.
La première chose que l'on fait est de marquer le sommet A comme déjà vu. En effet, il pourrait y avoir un cycle qui nous ramènerait sur le sommet A (ce n'est pas le cas ici, mais on ne peut pas le
savoir a priori) et avoir marqué le sommet A nous permettra d'interrompre
le parcours et de revenir en arrière.
On considère ensuite les arcs sortants du
sommet A. Il y en a deux, à savoir A—>B et A—>D. Comme on l'a expliqué dans l'introduction, on choisit de façon arbitraire un arc à considérer en premier.
Choisissons par exemple d'emprunter l'arc A—>B. On se retrouve donc maintenant à visiter le sommet B. On commence par le marquer puis on examine ses arcs.
Ici, il n'y en a qu'un seul, à savoir B—>C. On l'emprunte donc et on se retrouve à visiter le sommet C, que l'on commence par marquer.
Il y a 2 arcs sortants du sommet C et là encore on choisit arbitrairement celui qui est considéré en premier.
Ici, on choisit l'arc C—>E, ce qui nous
conduit à marquer E puis à considérer l'unique arc E—>B issu de E.
On se retrouve alors dans une situation nouvelle, où pour la première fois on retombe sur un sommet déjà marqué, à savoir B. On revient donc en arrière, pour se retrouver sur le sommet E.
Comme il n'y avait pas d'autre arc issu
de E, on revient une fois de plus en arrière, pour se retrouver sur le sommet C.
Là, on avait considéré l'arc C—>E mais il y a également l'arc C—>F, que l'on emprunte donc maintenant.
On visite donc le sommet F, que l'on marque.
Comme il n'y a aucun arc sortant du sommet F, on a terminé et on revient
au sommet C.
Cette fois, tous les arcs issus de C ont été examinés, et on a donc terminé la visite de C.
On revient donc au sommet B, donc la visite est également terminée.
On revient donc au sommet A.
Là, il y avait encore l'arc A->D à considérer.
On visite donc le sommet D, que l'on marque avant de considérer l'arc D—>E.
On retombe alors sur le sommet E, déjà visité.
On revient donc en arrière, sur le sommet D, puis encore en arrière, sur le sommet A.
Là, il n'y a plus d'arc à considérer et la visite de A est terminée, ce qui achève notre parcours en profondeur.
Une fois le parcours terminé, tous les sommets atteignables à partir de A
ont été marqués, à savoir A, B, C, D,E et F.
Inversement, le sommet G, qui n'est pas atteignable à partir de A, n'a pas été marqué. C'est là une propriété fondamentale du parcours en profondeur.
Venons-en à la programmation du parcours en profondeur. Le code, ci-dessous repose sur deux ingrédients. Le premier est l'utilisation d'un ensemble pour le marquage des sommets, que l'on appelle vus. Le second ingrédient est l'utilisation d'une fonction récursive pour réaliser le parcours proprement dit.
Cette fonction appelée parcours reçoit en arguments le graphe g, l'ensemble vus et un sommet s à partir duquel réaliser le parcours.
En quatre lignes seulement, elle s'écrit comme elle s'énonce :
«si le sommet s n'est pas dans vus, l'y ajouter et parcourir récursivement tous ses voisins».
Programme — Parcours en profondeur
def parcours(g, vus, s):
\"\"\"parcours en profondeur depuis le sommet s\"\"\"
if s not in vus:
vus.add(s)
for v in g.voisins(s):
parcours(g, vus, v)
def existe_chemin(g, u, v):
\"\"\"existe-t-il un chemin de u à v?\"\"\"
vus = set()
parcours(g, vus, u)
return v in vus
Tester le programme existe_chemin sur le graphe suivant:
#réalisation du graphe
g2 = Graphe2()
g2.ajouter_arc(\"A\",\"B\")
g2.ajouter_arc(\"B\",\"C\")
g2.ajouter_arc(\"A\",\"D\")
g2.ajouter_arc(\"D\",\"E\")
g2.ajouter_arc(\"E\",\"B\")
g2.ajouter_arc(\"C\",\"E\")
g2.ajouter_arc(\"C\",\"F\")
g2.ajouter_arc(\"G\",\"C\")
g2.afficher()
print(\"A->F?\",existe_chemin(g2,\"A\",\"F\"))
print(\"A->G?\",existe_chemin(g2,\"A\",\"G\"))
print(\"D->F?\",existe_chemin(g2,\"D\",\"F\"))
Mettre le résultat ici (code et figure).
Déterminer l'existence d'un chemin entre deux sommets
Une application immédiate du parcours en profondeur consiste à déterminer s'il existe un chemin entre deux sommets u et v. En effet, il suffit de lancer un parcours en profondeur à partir du sommet u puis, une fois qu'il est terminé, de regarder si le sommet v fait partie de l'ensemble des sommets marqués.
Le progrannne contient une fonction existe_chemin qui réalise cette idée.
Elle crée un nouvel ensemble vus, appelle la fonction parcours à partir du sommet u puis vérifie enfin si le sommet v à été visité pendant le parcours.
Bien entendu, on pourrait interrompre le parcours en profondeur dès que le sommet v est atteint. Mais il faudrait modifier pour cela la fonction parcours.
Construire le chemin
Si on veut construire le chemin, il faut se fatiguer un peu plus.
Au lieu d'un ensemble vus, on prend un dictionnaire, qui associe à chaque sommet le sommet qui à permis de l'atteindre (la
première fois) pendant le parcours en profondeur.
Pour le sommet de départ u, on lui associe None dans ce dictionnaire.
Une fois le parcours en profondeur terminé, on ne se contente pas de regarder si le sommet d'arrivée v est dans vus, mais on «remonte» le dictionnaire, en partant de v, jusqu'à arriver à u.
Vous réaliserez ce programme dans les exercices.
Mettre le résultat ici (code et figure).
Utilisation
Illustrons l'utilisation de notre parcours en profondeur sur le graphe des régions de la figure ci-dessous:
On a la variable regions qui contient une représentation de ce graphe.
******
On peut tester la présence de chemins, par exemple comme ceci :
assert existe_chemin(regions, \"Bretagne\", \"Occitanie\")
assert not existe_chemin(regions, \"Bretagne\", \"Mayotte\")
Ici, où vérifie l'existence d'un chemin entre la région Bretagne et la région
Occitanie et l'absence d'un chemin entre la région Bretagne et la région Mayotte.
Mettre le résultat ici (code et figure).
Efficacité
Le parcours en profondeur est un algorithme très efficace, dont
******
pendant ce parcours.
En effet, l'arc u—>v est examiné au plus une fois, à savoir la première fois que la fonction parcours est appelée sur le sommet u.
En effet, si la fonction parcours est rappelée plus tard sur ce même sommet u, alors il sera trouvé dans l'ensemble vus et la fonction se terminera immédiatement, sans rien faire.
Dans le pire des cas, tous les sommets sont atteignables et tout le graphe est donc parcouru.
Le coût est moindre lorsque certains sommets ne sont pas atteignables depuis le sommet de départ.
Le coût en mémoire est celui de l'ensemble vus, qui contient au final tous les sommets atteignables.
Mettre le résultat ici (code et figure).
Limites de la récursion
La fonction parcours étant récursive, il y a un risque de provoquer RecursionError si le graphe contient beaucoup de sommets.
Ainsi, un parcours en profondeur à partir du sommet 1 sur le graphe
1 -> 2 ... <> 2000
va provoquer cette erreur, car on va dépasser le nombre maximal d'appels récursifs imbriqués (1000 par défaut).
Comme expliqué dans la séquence sur les fonctions récursives, on peut modifier cette limite avec la fonction setrecursionlimit.
Une autre solution consiste à réécrire la fonction parcours avec une boucle while.
Pour cela, on utilise une pile dans laquelle on stocke les sommets qu'il faut parcourir.
Le programme ci-dessous donne le code de cette nouvelle fonction parcours.
On n'a pas besoin de savoir ici comment la pile est réalisée.
C'est un exemple de modularité. La fonction existe_chemin reste inchangée.
Programme — Parcours en profondeur avec une pile
from modPile import *
def parcours2(g, vus, s):
\"\"\"parcours en profondeur depuis le sommet s\"\"\"
pile = Pile()
pile.empiler(s)
while not pile.est_vide():
s = pile.depiler()
if s in vus:
continue
vus.add(s)
for v in g.voisins(s):
pile.empiler(v)
def existe_chemin2(g, u, v):
\"\"\"existe-t-il un chemin de u à v?\"\"\"
vus = set()
parcours2(g, vus, u)
return v in vus
Tester avec :
g2 = Graphe2()
g2.ajouter_arc(\"A\",\"B\")
g2.ajouter_arc(\"B\",\"C\")
g2.ajouter_arc(\"A\",\"D\")
g2.ajouter_arc(\"D\",\"E\")
g2.ajouter_arc(\"E\",\"B\")
g2.ajouter_arc(\"C\",\"E\")
g2.ajouter_arc(\"C\",\"F\")
g2.ajouter_arc(\"G\",\"C\")
g2.afficher()
print(\"A->F?\",existe_chemin2(g2,\"A\",\"F\"))
print(\"A->G?\",existe_chemin2(g2,\"A\",\"G\"))
print(\"D->F?\",existe_chemin2(g2,\"D\",\"F\"))
Conclure sur k'avantage de l'utilisation d'une pile par rapport à une fonction récursive.
Mettre le résultat ici (code et figure).
Le parcours en profondeur permet également de détecter la présence d'un
cycle dans un graphe orienté.
En effet, puisque l'on marque les sommets
avant de considérer leurs voisins, pour justement éviter de tourner en rond dans un cycle, alors on doit pouvoir être à même de détecter la présence d'un cycle.
Il y a cependant une petite subtilité, car lorsqu'on retombe sur un sommet déjà marqué, on ne sait pas pour autant si on vient de découvrir un cycle.
Considérons par exemple le parcours en profondeur des deux graphes suivants, à partir du sommet A à chaque fois:
![](\"https://sciencesappliquees.com/images/nsi/graphe10.png\")
Dans le graphe de gauche, on retombe sur le sommet C.
Il n'y a pas de cycle pour autant, mais seulement un chemin parallèle.
Dans le graphe de droite, on retombe sur le sommet B, cette fois à cause d'un cycle.
Tel qu'il est écrit, notre parcours en profondeur ne nous permet pas de distinguer ces deux situations.
Dans les deux cas, on constate que le sommet est déjà dans l'ensemble vus, sans pouvoir en tirer de conclusion quant à l'existence d'un cycle.
Pour y remédier, on va distinguer dans l'ensemble vus deux sortes de sommets:
ceux pour lesquels le parcours en profondeur n'est pas encore terminé et ceux pour lesquels il est au contraire terminé.
On pourrait utiliser pour cela deux ensembles, ou encore un dictionnaire qui associe à chaque sommet déjà rencontré un booléen indiquant si son parcours en profondeur est terminé.
Mais traditionnellement on utilise un marquage à trois couleurs:
- on marque en blane les sommets non encore atteints par le parcours en profondeur,
- en gris les sommets déjà atteints dont le parcours en profondeur est en cours
- et enfin en noir les sommets atteints dont le parcours est terminé.
Dans l'exemple de gauche ci-dessus, le sommet C sera colorié en noir quand on retombera dessus la deuxième fois.
Dans l'exemple de droite, en revanche, il sera encore gris quand on retombera dessus et on en déduira la présence d'un cycle.
Nous adoptons ici cette solution utilisant trois couleurs.
Le parcours en profondeur est modifié de la façon suivante.
Lorsque l'on visite un sommet s, on procède ainsi :
- s'il est gris, c'est qu'on vient de découvrir un cycle;
- s'il est noir, on ne fait rien;
- sinon, c'est qu'il est blanc, et on procède ainsi:
- on colore le sommet s en gris;
- on visite tous ses voisins, récursivement;
- enfin, on colore le sommet s en noir.
Comme on le voit, les voisins du sommet s sont examinés après le moment où s est colorié en gris et avant le moment où s est colorié en noir.
Ainsi, s'il existe un cycle nous ramenant sur s, on le trouvera comme étant gris et
le cycle sera signalé.
Le programme ci-dessous contient une fonction cycle qui réalise cette détection de cycle. Il s'agit 1à d'une modification du parcours en profondeur où un dictionnaire couleur remplace l'ensemble vus.
Programme — Détecter la présence d'un cycle dans un graphe
BLANC, GRIS, NOIR = 1, 2, 3
def parcours_cy(g, couleur, s):
\"\"\"parcours en profondeur depuis le sommet s\"\"\"
if couleur[s] == GRIS:
return True
if couleur[s] == NOIR:
return False
couleur[s] = GRIS
for v in g.voisins(s):
if parcours_cy(g, couleur, v):
return True
couleur[s] = NOIR
return False
def cycle(g):
couleur = {}
for s in g.sommets():
couleur[s] = BLANC
for s in g.sommets():
if parcours_cy(g, couleur, s):
return True
return False
La fonction parcours est toujours une fonction récursive, mais elle renvoie désormais un résultat, à savoir un booléen indiquant la présence d'un cycle.
Enfin, la fonction cycle colorie tous les sommets en blanc puis lance un parcours en profondeur à partir de tous les sommets du graphe.
Si l'un de ces parcours renvoie True, on transmet re résultat. Sinon. on renvoie False.
Dans cette version, on cherche à détecter la présence d'un cycle n'importe où dans le graphe. C'est pourquoi on lance un parcours en profondeur à partir de tous les sommets du graphe,
Pour beauconp de ces sommets, le parcours est passé par là, car ils étaient accessibles depuis des sommets déjà parcourus, et la fonction parcours se termine immédiatement sans rien faire.
Le temps total passé dans la détection de cycle reste proportionnel à la taille du graphe. Si on lance un parcours en profondeur à partir d'un seul sommet s, alors on détecte uniquement la présence d'un cycle atteignable à partir de s.
Tester avec les graphes suivants:
g1 = Graphe2()
g1.ajouter_arc(\"A\",\"B\")
g1.ajouter_arc(\"B\",\"C\")
g1.ajouter_arc(\"A\",\"D\")
g1.ajouter_arc(\"D\",\"C\")
g1.afficher()
print(cycle(g1))
g2 = Graphe2()
g2.ajouter_arc(\"A\",\"B\")
g2.ajouter_arc(\"B\",\"C\")
g2.ajouter_arc(\"D\",\"B\")
g2.ajouter_arc(\"C\",\"D\")
g2.afficher()
print(cycle(g2))
Conclure sur les résultats donnés par la fonction cycle.
Mettre le résultat ici (code et figure).
Le parcours en profondeur nous permet de déterminer l'existence d'un chemin entre deux sommets, et même d'en construire un, mais il ne détermine pas pour autant la distance entre deux sommets, c'est-à-dire la longueur minimale d'un chemin entre ces deux sommets.
![](\"https://sciencesappliquees.com/images/nsi/graphe3.png\")
Si on considère par exemple le graphe des régions et que l'on cherche un chemin entre la région Bretagne et la région Grand Est avec notre parcours en profondeur, alors on trouve le chemin suivant :
Bretagne—>Normandie—>Hauts-de-France—>Île-de-France—>Bourgogne-Franche-Comté —> Grand Est
Ce chemin à la longueur 5, alors qu'il existe un chemin de longueur 3, à savoir
Bretagne—>Normandie—>Île-de-France—>Grand Est
Le fait est que le parcours en profondeur détermine un chemin arbitraire parmi tous les chemins possibles (sans répétitions), car il emprunte les arcs dans un ordre arbitraire.
Si on veut en revanche déterminer la distance entre deux sommets, c'est-à-dire un plus court chemin entre ces deux sommets, alors il faut utiliser un autre algorithme, à savoir le parcours en largeur.
Comme pour le parcours en profondeur, on se donne un sommet de départ, pour initier le parcours. On l'appelle la source.
Et comme pour le parcours en profondeur, on va déterminer peu à peu tous les sommets atteignables à partir de ce sommet de départ.
Ce qui diffère, c'est l'ordre dans lequel ces sommets vont être visités.
Dans le parcours en largeur, on explore le graphe «en cercles concentriques» à partir de la source, c'est-à-dire qu'on visite d'abord tous les sommets à distance 1 de la source, puis tous les sommets à distance 2 de la source, et ainsi de suite, jusqu'à ce que tous les sommets atteignables depuis la source aient été visités.
Mettre le résultat ici (code et figure).
Si on reprend l'exemple du graphe ci-dessus et qu'on effectue un parcours en largeur à partir du sommet A,
- alors on va examiner d'abord les sommets B et D, situés à distance 1 de A,
- puis les sommets C et E, situés à distance 2,
- puis enfin le sommet F, situé à distance 3.
Comme pour le parcours en profondeur, le sommet G n'est pas visité, car il n'est pas atteignable depuis A.
Pour mettre en œuvre le parcours en largeur, et l'idée de cercles concentriques, on peut se servir de deux ensembles.
Le premier, appelé courant, contient des sommets situés à distance d de la source.
C'est notamment dans cet ensemble qu'on pioche le prochain sommet à examiner.
Le second ensemble, appelé suivant, contient des sommets situés à distance d de la source, que l'on examinera après ceux de l'ensemble courant.
À côté de ces deux ensembles, on utilise également un dictionnaire, appelé dist, qui associe à chaque sommet déjà atteint sa distance à la source.
Le parcours en largeur procède ainsi :
- initialement, la source est placée dans l'ensemble courant et sa distance est fixée à D:
- tant que l'ensemble courant n'est pas vide,
(a) on en retire un sommets,
(b) pour chaque voisin v de s qui n'est pas encore dans dist
* on ajoute v à l'ensemble suivant,
* on fixe dist[v] à dist[s]+1
(c) si l'ensemble courant est vide, on l'échange avec l'ensemble
suivant.
Mettre le résultat ici (code et figure).
La figure 2 détaille les différentes étapes de cet algorithme sur l'exemple
du graphe
en partant du sommet A. La figure illustre le contenu des deux ensembles, ainsi que les différentes affectations effectuées dans le dictionnaire dist.
| courant | suivant | action |
| A | initialisation, dist[A]=0 | |
| B,D | on retire le sommet A, dist|B]=1. dist[D]=1 | |
| B,D | l'ensemble suivant est vide => échange | |
| D | C | on retire le sommet B, dist|C]=2 |
| C,E | on retire le sommet D, dist[E]=2 | |
| C,E | l'ensemble suivant est vide => échange | |
| E | on retire le sommet C, dist[F]=3 | |
| F | on retire le sommet E | |
| on retire le sommet F terminé |
Figure 2 — Parcours en largeur, à partir du sommet A.
On prendra le temps de bien comprendre cet algorithme.
Le programme ci-dessous réalise cet algorithme en Python. La fonction parcours_largeur réalise un parcours en largeur en partant du sommet
source, à l'aide d'une boucle while.
Programme — Parcours en largeur
def parcours_largeur(g, source):
\"\"\"parcours en largeur depuis le sommet source\"\"\"
dist = {source: 0}
courant = {source}
suivant = set()
while len(courant) > 0:
s = courant.pop()
for v in g.voisins(s):
if v not in dist:
suivant.add(v)
dist[v] = dist[s] + 1
if len(courant) == 0:
courant, suivant = suivant, set()
return dist
def distance(g, u, v):
\"\"\"distance de u à v (et None si pas de chemin)\"\"\"
dist = parcours_largeur(g, u)
return dist[v] if v in dist else None
Les deux ensembles courant et suivant sont des variables locales à la fonction parcours. Une fois le parcours terminé, la fonction parcours renvoie le dictionnaire dist.
Une seconde fonction distance renvoie la distance entre deux sommets u et v, en lançant un parcours en largeur à partir de u puis en consultant la valeur de dist[v].
Si v n'a pas été atteint, on renvoie None.
Tester le programme avec les instructions suivantes :
g2 = Graphe2()
g2.ajouter_arc(\"A\",\"B\")
g2.ajouter_arc(\"B\",\"C\")
g2.ajouter_arc(\"A\",\"D\")
g2.ajouter_arc(\"D\",\"E\")
g2.ajouter_arc(\"E\",\"B\")
g2.ajouter_arc(\"C\",\"E\")
g2.ajouter_arc(\"C\",\"F\")
g2.ajouter_arc(\"G\",\"C\")
g2.afficher()
print(\"distance A F\",distance(g2,\"A\",\"F\"))
print(\"distance A F\",distance(g2,\"A\",\"G\"))
justifier les résultats.
Mettre le résultat ici (code et figure).
Une file, pour quoi faire une file?
![\"pile_file1.png](\"https://sciencesappliquees.com/images/nsi/pile_file1.png\")
Le parcours en largeur est traditionnellement réalisé avec une file, dans laquelle on ajoute à la fin les nouveaux sommets (ceux que notre code met dans l'ensemble suivant) et dans laquelle on retire au début le prochain sommet à examiner (celui que notre code retire de l'ensemble courant).
Dans cette file, des sommets à la distance d de la source précède des sommets à distance d + 1, ce que l'on peut visualiser ainsi :
![](\"https://sciencesappliquees.com/images/nsi/graphe20.png\")
L'ordre des sommets situés à une même distance de la source important peu, notre solution avec deux ensembles convient tout aussi bien. Mais surtout, elle explicite la raison pour laquelle notre parcours en largeur est correct, ce que ne montre absolument pas la file.
En terme d'efficacité, il n'y à absolument aucune différence.
Utilisation
Illustrons l'utilisation de notre parcours en largeur sur le graphe des régions.
Nous avons la variable regions qui contienne la représentation de ce graphe:
regions = Graphe3() #non orienté
regions.ajouter_sommet(\"Guadeloupe\")
regions.ajouter_sommet(\"Martinique\")
regions.ajouter_sommet(\"Guyane\")
regions.ajouter_sommet(\"Corse\")
regions.ajouter_sommet(\"Mayotte\")
regions.ajouter_sommet(\"La Reunion\")
regions.ajouter_arc(\"Hauts-de-France\",\"Normandie\")
regions.ajouter_arc(\"Hauts-de-France\",\"Ile-de-France\")
regions.ajouter_arc(\"Hauts-de-France\",\"Grand Est\")
regions.ajouter_arc(\"Ile-de-France\",\"Grand Est\")
regions.ajouter_arc(\"Ile-de-France\",\"Hauts-de-France\")
regions.ajouter_arc(\"Pays de la Loire\",\"Bretagne\")
regions.ajouter_arc(\"Normandie\",\"Bretagne\")
regions.ajouter_arc(\"Normandie\",\"Pays de la Loire\")
regions.ajouter_arc(\"Pays de la Loire\",\"Centre-Val de Loire\")
regions.ajouter_arc(\"Centre-Val de Loire\",\"Normandie\")
regions.ajouter_arc(\"Pays de la Loire\",\"Nouvelie-Aquitaine\")
regions.ajouter_arc(\"Nouvelie-Aquitaine\",\"Centre-Val de Loire\")
regions.ajouter_arc(\"Ile-de-France\",\"Centre-Val de Loire\")
regions.ajouter_arc(\"Bourgogne-Franche Comte\",\"Centre-Val de Loire\")
regions.ajouter_arc(\"Bourgogne-Franche Comte\",\"Grand Est\")
regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Centre-Val de Loire\")
regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Bourgogne-Franche Comte\")
regions.ajouter_arc(\"Ile-de-France\",\"Bourgogne-Franche Comte\")
regions.ajouter_arc(\"Ile-de-France\",\"Normandie\")
regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Occitanie\")
regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Provence-Alpes-Cote d'Azur\")
regions.ajouter_arc(\"Occitanie\",\"Provence-Alpes-Cote d'Azur\")
regions.ajouter_arc(\"Occitanie\",\"Nouvelie-Aquitaine\")
regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Nouvelie-Aquitaine\")
On peut vérifier la distance entre des régions:
assert distance(regions, \"Bretagne\", \"Occitanie\") == 3
assert distance(regions, \"Bretagne\", \"Bretagne\") == 0
assert distance(regions, \"Bretagne\", \"Mayotte\") == None
Ici, on vérifie que la distance d'une région a elle-même est bien 0 et que la fonction distance renvoie bien None pour deux régions entre lesquelles il n'existe pas de chemin.
Tester les codes et conclure sur les résultats.
Mettre le résultat ici (code et figure).
Efficacité
Comme pour le parcours en profondeur, le parcours en largeur a un coût directement proportionnel à la taille de la partie du graphe qui a été explorée. En effet, chaque sommet est placé au plus une fois dans l'ensemble suivant, la première fois qu'il est rencontré, c'est-à-dire lorsqu'il n'est pas encore dans le dictionnaire dist.
À ce moment-là, on fixe sa distance, ce qui fait qu'il ne sera pas considéré de nouveau.
De même, chaque arc s —> v est examiné au plus une fois, lorsque le sommet s est retiré de l'ensemble courant.
Le coût en mémoire est celui des deux ensembles et du dictionnaire, au pire proportionnel au nombre total de sommets du graphe.
Mettre le résultat ici (code et figure).
Étant donnés un graphe et un sommet dans ce graphe, le parcours eu profondeur et le parcours en largeur sont deux algorithimes fondamentaux pour explorer le graphe en partant de ce sommet.
Ces deux parcours déterminent l'ensemble des sommets accessibles depuis le sommet de départ.
Le parcours en profondeur permet de détecter la présence d'un cycle dans un graphe orienté.
Le parcours en largeur permet de déterminer la distance entre le sommet de départ et tout sommet accessible, c'est-à-dire le plus petit nombre d'arcs pour
relier ces deux sommets.
Mettre le résultat ici (code et figure).
Dérouler à la main le parcours en profondeur sur le graphe
suivant
![](\"https://sciencesappliquees.com/images/nsi/graphe11.png\")
pour différentes valeurs du sommet de départ.
Donner à chaque fois la valeur finale de l'ensemble vus, c'est-à-dire l'ensemble des sommets atteints par le parcours.
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
sommet | valeur finale
de départ de vus
0 {0,1,3,2}
1 {1,2}
2 C2}
3 {3,1,2}
Dérouler à la main le parcours en largeur sur le graphe suivant
pour différentes valeurs du sommet de départ.
Donner à chaque fois la valeur finale du dictionnaire dist, c'est-à-dire la distance à la source de chaque sommet atteint par le parcours.
Mettre le résultat ici (code et figure).
sommet valeur finale
de départ de dist
0 {0H0,1H1,38m1,2r 2}
1 {1H0,2H 1}
2 {25 0}
3 {3-0,1H1,2r 2}
On peut se servir d'un parcours en profondeur pour déterminer si un graphe non orienté est connexe, c'est-à-dire si tous ses sommets sont reliés entre eux par des chemins.
Pour cela, il suffit de faire un parcours en profondeur à partir d'un sommet quelconque, puis de vérifier que tous les sommets ont été atteints par ce parcours.
Écrire une fonction est_connexe() qui réalise cet algorithme.
On pourra se servir de la méthode sommets() de la classe Graphe et de la fonction parcours.
Tester avec les 2 graphes suivants :
g1 :
![](\"https://sciencesappliquees.com/images/nsi/graphe13.png\")
g2:
![](\"https://sciencesappliquees.com/images/nsi/graphe12.png\")
print(\"g1 connexe?\",est_connexe(g1))
print(\"g2 connexe?\",est_connexe(g2))
Résultat :
True
False
Mettre le résultat ici (code et figure).
g1 = Graphe3()
g1.ajouter_arc(\"A\",\"B\")
g1.ajouter_arc(\"B\",\"C\")
g1.ajouter_arc(\"A\",\"D\")
g1.ajouter_arc(\"D\",\"C\")
g2 = Graphe3()
g3.ajouter_arc(\"A\",\"B\")
g3.ajouter_arc(\"B\",\"C\")
g3.ajouter_arc(\"A\",\"D\")
g3.ajouter_arc(\"D\",\"C\")
g2.ajouter_arc(\"E\",\"F\")
On suit l’algorithme proposé, en faisant uniquement attention au cas d’un graphe qui ne contiendrait aucun
sommet.
def est_connexe(g):
\"\"\"le graphe est-il connexe?
(uniquement pour un graphe non orienté)\"\"\"
ts = g.sommets()
if len(ts) == 0:
return True
s = ts.pop()
vus = set()
parcours(g, vus, s)
for s in ts:
if s not in vus:
return False
return True
Dans cet exercice, on se propose d'utiliser le parcours en profondeur pour construire un chemin entre deux sommets, lorsque c'est possible.
On le fait avec deux fonctions, comme dans le programme parcours en profobdeur.
def parcours_ch(g, vus, org, s):
\"\"\"parcours depuis Le sommet s, en venant de org\"\"\"
...
def chemin(g, u, v):
\"\"\"un chemin de u à v, Le cas échéant, None sinon\"\"\"
...
L'idée est que l'attribut vus n'est plus un ensemble mais un dictionnaire, qui associe à chaque sommet visité le sommet qui a permis de l'atteindre pendant le parcours en profondeur.
La fonction parcours_ch prend un argument supplémentaire, org (pour origine), qui est justement le sommet qui a permis d'atteindre s, en empruntant l'arc org —>s.
Écrire le code de la fonction parcours_ch.
Il est très semblable à celui de la fonction parcours du programme parcours en profondeur.
Écrire ensuite le code de la fonction chemin qui renvoie un chemin entre les sommets u et v, le cas échéant, None s'il n'existe pas de chemin entre ces deux sommets.
Pour cela, lancer un parcours en profondeur à partir du sommet u, en donnant à org la valeur None, puis, si
le sommet v a été atteint, construire le chemin dans un tableau en «remontant» le dictionnaire vus de v jusqu'à u.
Tester avec le graphe suivant:
print(\"A->F?\",chemin(g2, \"A\", \"F\"))
print(\"A->G?\",chemin(g2, \"A\", \"G\"))
Résultat:
A->F? ['A', 'D', 'E', 'B', 'C', 'F']
A->G? None
Mettre le résultat ici (code et figure).
Pour parcours_ch, l'ajout dans un ensemble de-
vient un ajout dans un dictionnaire.
def parcours_ch(g, vus, org, s):
\"\"\"parcours depuis le sommet s, en venant de org\"\"\"
if s not in vus:
vus[s] = org
for v in g.voisins(s):
parcours_ch(g, vus, s, v)
Pour chemin, on prend soin de tester si v a été atteint par le parcours. Dans
le cas contraire, on renvoie None. Sinon, on construit le chemin avec une
boucle while.
def chemin(g, u, v):
\"\"\"chemin de u à v, le cas échéant, None sinon\"\"\"
vus = {}
parcours_ch(g, vus, None, u)
if v not in vus:
return None
ch = []
s=v
while s is not None:
ch.append(s)
s = vus[s]
ch.reverse()
return ch
De fait, le chemin est construit à l'envers. On prend soin de le renverser avec
la méthode reverse avant de le renvoyer.
Dans cet exercice, on se propose d'utiliser le parcours en largeur pour construire un chemin de longueur minimale entre deux sommets.
On le fait avec deux fonctions, comme dans le programme parcours en largeur.
def parcours_largeur_ch(g, source):
\"\"\"parcours depuis le sommet source\"\"\"
...
def chemin(g, u, v):
\"\"\"un chemin de u à v, le cas échéant, None sinon\"\"\"
L'idée est qu'un dictionnaire vus remplace le dictionnaire dist.
Ce dictionnaire vus associe à chaque sommet visité le sommet qui à permis de l'atteindre pendant le parcours en largeur.
Écrire le code de la fonction parcours_largeur_ch.
Il est très semblable à celui de la fonction parcours_largeur du programme parcours en largeur.
Pour le sommet source, on lui associe la valeur None dans le dictionnaire vus.
Écrire ensuite le code de la fonction chemin qui renvoie un chemin réalisant la distance entre les sommets u et v, le cas échéant, et None s'il n'existe pas de chemin entre ces deux sommets.
Pour cela, lancer un parcours en largeur à partir du sommet u puis, si le sommet v a été atteint, construire le chemin dans un tableau en «remontant» le dictionnaire vus de v jusqu'à u.
Tester avec le graphe suivant:
print(\"A->F?\",chemin(g2, \"A\", \"F\"))
print(\"A->G?\",chemin(g2, \"A\", \"G\"))
Résultat:
A->F? ['A', 'B', 'C', 'F']
A->G? None
Mettre le résultat ici (code et figure).
On garde la structure du programme 42, le diction-
naire vus prenant la place du dictionnaire dist.
def parcours_largeur_ch(g, source):
\"\"\"parcours depuis Le sommet source\"\"\"
vus = {source: None}
courant = {source}
suivant = set()
while len(courant)>0:
s = courant.pop()
for v in g.voisins(s):
if v not in vus:
suivant.add(v)
vus[v] = s
if len(courant) == 0:
courant, suivant = suivant, set()
return vus
La seconde partie, à savoir la reconstruction du chemin, n’est pas différente
de celle effectuée dans l’exercice précédent pour un parcours en profondeur.
def chemin(g, u, v):
\"\"\"chemin de u à v, Le cas échéant, None sinon\"\"\"
vus = parcours_largeur_ch(g, u)
if v not in vus:
return None
ch = []
s=v
while s is not None:
ch.append(s)
s = vus[s]
ch.reverse()
return ch
![](\"https://sciencesappliquees.com/images/nsi/graphe14.png\")
Les nœuds d'un arbre binaire peuvent être vus comme les sommets d'un graphe non orienté.
En particulier, on peut donc parcourir les nœuds d'un arbre avec un parcours en profondeur ou en largeur.
Pour le parcours en profondeur, il s'agit d'un parcours que nous avons déjà présenté, à savoir le parcours préfixe.
Dans cet exercice, on se propose de parcourir les nœuds d'un arbre binaire avec un parcours en largeur.
Écrire une fonction largeur(a) qui reçoit un arbre binaire a en argument et imprime les valeurs de ses différents nœuds dans un ordre donné par un parcours en largeur, c'est-à-dire la valeur contenue dans la racine, puis les valeurs contenues dans les nœuds immédiatement en-dessous (niveau 1), puis celles contenues dans les nœuds encore en-dessous (niveau 2), etc.
Tester le programme avec l'arbre ci-dessus et le code suivant:
largeur(a1)
Résultat:
8
4
12
2
6
10
14
1
3
7
9
13
15
Indication : Il faut utiliser les classes suivantes pour construire l'arbre a1:
class Noeud:
\"\"\"un noeud d'un arbre binaire\"\"\"
def __init__(self, g, v, d):
self.gauche = g
self.valeur = v
self.droit = d
def __eq__(self, n):
return n is not None \\
and self.gauche == n.gauche \\
and self.valeur == n.valeur \\
and self.droit == n.droit
class ABR:
\"\"\"arbre binaire de recherche\"\"\"
def __init__(self):
self.racine = None
def ajouter(self, x):
if self.racine is None :
self.racine = Noeud(None,x,None)
else :
self.__ajoute__(x,self.racine)
def contient(self, x):
return self.__appartient__(x, self.racine)
def affiche(self):
self.__afficher__(self.racine)
print(\"\\n\")
def __afficher__(self,a):
if a is None:
return
print (\"(\", end=\"\")
self.__afficher__(a.gauche)
print(a.valeur, end=\"\")
self.__afficher__(a.droit)
print(\")\", end=\"\")
def __ajoute__(self,x,a):
if x < a.valeur:
if a.gauche is None:
a.gauche = Noeud(None, x, None)
else:
self.__ajoute__(x,a.gauche)
elif x > a.valeur:
if a.droit is None:
a.droit = Noeud(None, x, None)
else:
self.__ajoute__(x,a.droit)
def __appartient__(self,x, a):
\"\"\"détermine si x apparaît dans l'ABR\"\"\"
if a is None:
return False
if x < a.valeur:
return self.__appartient__(x, a.gauche)
elif x > a.valeur:
return self.__appartient__(x, a.droit)
else:
return True
Mettre le résultat ici (code et figure).
On crée l'arbre a1:
a1 = ABR()
a1.ajouter(8)
a1.ajouter(4)
a1.ajouter(12)
a1.ajouter(2)
a1.ajouter(6)
a1.ajouter(10)
a1.ajouter(14)
a1.ajouter(1)
a1.ajouter(3)
a1.ajouter(7)
a1.ajouter(9)
a1.ajouter(13)
a1.ajouter(15)
a1.affiche()
a1.affiche()
a1.affiche()
Le programme en largeur est le suivant:
def largeur(a):
h = hauteur(a.racine)
for i in range(1, h+1):
affiche_niveau(a.racine, i)
print()
def affiche_niveau(Noeud, niveau):
if Noeud is None:
return
if niveau == 1:
print(Noeud.valeur)
elif niveau > 1:
affiche_niveau(Noeud.gauche, niveau-1)
affiche_niveau(Noeud.droit, niveau-1)
def hauteur(Noeud):
if Noeud is None:
return 0
else:
lheight = hauteur(Noeud.gauche)
rheight = hauteur(Noeud.droit)
return 1+max(lheight, rheight)
![](\"https://sciencesappliquees.com/images/nsi/graphe18.png\")
Il est représenté part un liste à 2 dimensions en Python
grid = [[1, 0, 1, 1, 1, 1, 1 ,1],
[1, 0, 0, 0, 0, 0, 1 ,1],
[1, 1, 1, 0, 0, 0, 1 ,1],
[1, 0, 0, 0, 1, 0, 0 ,1],
[1, 0, 1, 1, 0, 0, 1 ,1],
[1, 0, 1, 0, 0, 1, 0 ,1],
[1, 0, 1, 0, 0, 0, 0 ,1],
[1, 1, 1, 1, 1, 1, 0 ,1]]
Avec :
- O pour un passage;
- 1 pour un mur;
- l'entrée est en haut à gauche en (1,0);
- la sortie est en bas à droite en (len(grid[0])-2,len(grid)-1).
En le modélisant par un graphe et en le parcourant en largeur à l'aide de la fonction chemin, on détermine le moyen pour en sortir:
Vous allez donc écrire une fonction generer_graphe qui a comme argument une grille de labyrinthe et qui retourne son graphe non orienté (Graphe3).
En effet, grace au graphe du labyrinthe et à la fonction chemin, vu précédemment, nous pourrons déterminer le chemin pour en sortir.
Indications : Pour déterminer le graphe, il faut parcourir le labyrinthe et pour chacune des cases ajouter ou non des arcs.
Par exemple :
![](\"https://sciencesappliquees.com/images/nsi/graphe19.png\")
on ajoute pour cette cellule l'arc correspondant :
glaby.ajouter_arc((x,y),(x+1,y))
et pas :
glaby.ajouter_arc((x,y),(x,y+1))
car il y a un mur.
Tester avec le code suivant :
graphe_laby = generer_graphe(grid)
itineraire = chemin(graphe_laby,(1,0),(len(grid[0])-2,len(grid)-1))
print(itineraire)
Pour notre grille le résultat est le suivant:
[(1, 0), (1, 1), (2, 1), (3, 1), (3, 2), (4, 2), (5, 2), (5, 3), (5, 4), (4, 4), (4, 5), (4, 6), (5, 6), (6, 6), (6, 7)]
Donc avec les fonctions generer_graphe et chemin, nous pouvons déterminer les parcours pour des labyrinthe plus complexes:
","title":"Exercice","tagtitle":"h1"},{"edit":"
Mettre le résultat ici (code et figure).
def generer_graphe(grille):
glaby = Graphe3()
for i in range(0,len(grille)-1):
for j in range(0,len(grille[0])-1):
if grille[i][j] == 0 and grille[i][j+1]==0:
glaby.ajouter_arc((j,i),(j+1,i))
if grille[i][j] == 0 and grille[i+1][j]==0:
glaby.ajouter_arc((j,i),(j,i+1))
j+=1
if grille[i][j]==0 and grille[i+1][j]==0:
glaby.ajouter_arc((j,i),(j,i+1))
i+=1
for j in range(0,len(grille[0])-1):
if grille[i][j] == 0 and grille[i][j+1]==0:
glaby.ajouter_arc((j,i),(j+1,i))
return glaby