Aller au contenu

2) Parcours de graphes

Listes d'adjacence - liste d'adjacence

Ce nom est trompeur, mais très souvent utilisé.
On appelle souvent "listes d'adjacence", ou même "liste d'adjacence", le dictionnaire dont les clés sont les sommets du graphes, et les valeurs les listes (parfois tuples) des voisins associés à chaque sommet.

I. Introduction : modéliser un labyrinthe⚓︎

Considérons les problèmes suivants :

  • Comment rechercher le chemin le plus court entre deux stations dans le métro? Indépendamment de l'aspect ludique, c'est en fait un problème difficile qu'on aurait bien du mal à résoudre de façon raisonnable sur un gros graphe comme celui du métro.
  • Comment trouver la sortie d'un labyrinthe?

Les labyrinthes⚓︎

Voici l'image d'un labyrinthe :

Ce labyrinthe peut être représenté par le graphe suivant :

  • Chaque sommet du graphe correspond à une case du labyrinthe

  • une arête relie 2 cases voisines quand le passage est possible.

  • Si une paroie empêche de passer on ne met pas l'arête.

Par exemple il n'y a pas d'arête entre les sommets (1,1) et (1,2) mais il y en a une entre (1,1) et (2,1).

Les noeuds

A quoi correspondent les deux chiffres des noeuds de cette représentation ?

Solution

Le premier chiffre est un numéro de ligne, le deuxième un numéro de colonne.

Nous allons représenter ce graphe par le dictionnaire suivant :

Python
graphe = {11: [21], 12: [], 13: [23, 14], 14: [13, 15, 24], 15: [14, 25], 16: [26, 17], 17: [16, 18], 18: [17, 28],
         21: [11, 22], 22: [21, 23, 32], 23: [22, 13], 24: [14, 34], 25: [15, 26], 26: [25, 16, 36, 27], 
         27: [37, 26], 28: [18, 38], 31: [], 32: [22, 42], 33: [], 34: [24, 35], 35: [34, 36], 
         36: [26, 35, 46, 37], 37: [27, 36, 47], 38: [28, 48], 41: [], 42: [32, 43], 43: [42, 44], 44: [43], 
         45: [46], 46: [36, 45], 47: [37, 48], 48: [47, 38]}
Pour simplifier la figure, nous avons adopté les conventions suivantes : le nœud 11 représente en fait 1,1, le nœud 12 représente 1,2 etc ...

Dessiner ce graphe avec netwoks

Dessiner ce graphe avec graphviz

Créer un fichier png de ce graphe avec graphviz

Résoudre ce labyrinthe

Ce labyrinthe est assez simple, et une fois sa représentation en graphe tracée comme ci-dessus, il semble assez facile de résoudre ce labyrinthe, c'est à dire de trouver un chemin qui permette d'aller d'une case "entrée" à une case "sortie".

Supposons que la case "entrée" soit la case (1,1) et la case sortie la case (4,8). Cela correspond respectivement aux noeuds 11 et 48. Observons le graphe précédent. On voit assez facilement plusieurs chemins possibles. En donner trois possibles.

Solution
  • 11-21-22-23-13-14-15-25-26-16-17-18-28-38-48
  • 11-21-22-23-13-14-24-34-35-36-37-47-48
  • 11-21-22-23-13-14-24-34-35-36-26-16-17-18-28-38-48

Quels parcours ?

Nous voulons écrire un script Python qui permette de résoudre automatiquement, dans le cas où c'est possible, n'importe quel labyrinthe, même très compliqué.

Pour cela on peut penser parcourir le graphe en partant de l'entrée, en suivant différents chemins, jusqu'à atteindre le sommet de sortie.
Plusieurs algorithmes "classiques" permettent de parcourir les graphes. Nous allons commencer par les étudier, puis nous essaierons de résoudre ce problème en choisissant l'algorithme le plus adapté à cette situation.

II. Les parcours de graphes⚓︎

Contrairement aux arbres, les graphes n’ont pas de racine, de « début ». On peut donc choisir n’importe quel sommet pour commencer le parcours. Ceci dit, le parcours de certains graphes orientés demande un choix de sommet de début réfléchi.

😅 La vidéo suivante explique le principe des parcours. Pour bien justifier l'utilisation de la pile, la première étape du premier parcours présenté n'est pas tout à fait celle du parcours en profondeur que nous verrons au IV.

A retenir

  • Parcours en largeur : File
  • Pacours en profondeur : Pile

III. Le parcours en largeur⚓︎

Parcours en largeur

parcours est la liste vide qui contiendra les sommets visités par parcours en largeur
F est une file vide
On enfile un sommet dans F
Tant que F n'est pas vide
    S = Tête de F
    On défile F et on ajoute le sommet dans parcours
    On enfile les voisins de S qui ne sont ni dans la file ni dans parcours
Fin Tant Que

👉 9 étapes :

Question

Ecrire le code d'une fonction parcours_en_largeur qui parcourt en largeur un graphe à partir du sommet depart et dont sa liste d'adjacence est representée par un dictionnaire nommé graphe.

Cette fonction renverra la liste des sommets parcourus en partant du sommet depart.

Compléter le script ci-dessous :

Graphe du test :

graphe largeur

def parcours_en_largeur(graphe, depart):
file = [depart]
parcours = ...
...
return parcours
# Test
assert parcours_en_largeur({"A": ["B", "D", "E"],"B": ["A", "C"], "C": ["B", "D"],
"D": ["A", "C", "E"], "E": ["A", "D", "F", "G"], "F": ["E", "G"], "G": ["E", "F", "H"],
"H": ["G"]},"A") == ['A', 'B', 'D', 'E', 'C', 'F', 'G', 'H']
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
rounded
>>> 
 
x
x
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013l(9 _4:=vm26!-uS8w.s3/]fr7gebh[pPic05a,onkyd1)t050S0C0V0M0I0b0u0e0J0b0M0u0u0i010V0I0G010406050u0p0k0k0M0z0R040q0O0b0p0:0O0P050w0`0|0~100^0G04051g191j0w1g0^0S0I0j0(0*0,0.0*0P0B0p0M0B0C0o0G0R0V0E170e0E0I0B0E0b1L0E0V0?050Z0D0b0C1s0+0-011K1M1O1M0V1U1W1S0V0z1h1G0(130u0G0M0P0.0l011Y1u010y0#0C0P0M0k0C1S1@1_1~1!211W24260?0a0e0H0z0O0G0O0u0I160P0e0X1=0z0z0C0J2r19290P1h0w1G2E1.1:1/1T0S2b1v0I0P232o1S1p1r0)1Z2O2Q0P0O2U1S0G2x1h2C2E2+0_1^2s2W1 2!0z0}0b1S0M1J2x0y0.030f0f0J2#0C1O2Z0O0o0T390?0e0T190M2,2/0@2.2a2;1!2?2^2`2|0C2~01303234362R390o1|040e0l3f3h1_3j2C2N013o0M2_1h2{0E2}2 31330X3y2!3A0v3c0v3G2B3i0^3K3m0.3N3P053R3T3u3V3x2P3z3a0g3c0g3(1a3*3k2:1t3n0O2@3O3q3S3s3U3w3X3`3Z3a0L3c0L402+3+2/3L3/4a3?3v3W354g383a0m3c0m4m423,453.473p3Q3r3t4u3_373A0A3c0A4D3I4o3l4G3M4I494K4b4M3^4f4P3a0r3c0r4U2D4W442X4Z483:3=4c3@4e4w4+0o0d3c0d4:3J4p3-4^4J3;4L4d4v3Y4y390K0?0T0K551k2)192U2H0S1:2M584v2T1q1h2(0C2*3i3)3I054v5C2a0I0S0.312C3A0T3q5K5M4~5f5P1}2f0C5T5e4x5W2E3g433L0Q0?0X0y5E2D5*580s3c5:5I4?2=0y0?1^0z330p0z0u0f230f0*0z1B625_5=4Y0=040c6c4F4@0P0?0B0z0M0G0E0C6i576e0?0N5_0e6d6k5-0C5 0V6t4X4@6f0U0h6y0e0e0^415F3K5S015N2/3A3C5b6T4)4 3{3B5X255Z6U5U5$3a6Y0w3g6N6N6A2=0?2d6s6Q2D6z6j1 0O0?0i6y6^1!6f0F6G5{3n6C6E7a3L6f0x5_6P2-6S5L6,5O3a3#4K6!6-503#0e5Y5!4O6%7r3G6?6 6u6B045 616375701!7204746}3D760.787i7S7k5D7m5T7p0o3}7s7n6#5V3|6)267z4*6%7)7D6?7U015,040s1K1W7M7G2=0D0?2e7f586f6h7S7`6l046{876v040U816H710?0n7R2+7F8l1!0k0I0?5l8b7N7V0?6L7Y7f7t7%4j7*7;6$4h0o4j7x6*8J7-8M1S6;3D7E7_8z3M0?0u0O0|0Y8k7b0.7P8p3i8r8*8Z8e228g4@7P0t8@6_7I2m8{770?8a7l828t8v048x938s8A8i7j8E7+0f7%4A8I6,5#504A8O7:9k7A8L9i7^8W8/4q5~0~7K0u8 8+0?8`8y943.0?6p0G230S9C01899O8d8#8%6F9G9a9P0?8j8D9W2s8F6W3a4R9j7,6.0o4R9o6+9-509+9u8W7`7|0y478)9x040j0O0I2p187S9w580O5@042P9 588d6n6p6r9O789R8!8$269V998:7h8C4n9e7$9)0o4-9,7u6%4-9;8Q9.aA9_9v6@8Y7|0I5/a77`aa0?2!aq7!9H9Y6gama1a3a5ae4YaSaca68q8c9y600O629B9$7g9Za(8^ab1_9NaQ8Ya*aUak91a!a2a4ada aXa*b8a-8Y8d8fa@889Zau42a@9(1_3A52aB9l6%52aF9q7=8LbqaJaK7Ea.8=80bha)9Ea!9K9Mb3aZbG7Hb6a%bO1 6J6M6?7Z6R4pbn0P5P5ibr9r5g5k7/9=aC8Lb+5(8VaLaX7|2x0V62a,8.bD7Ja;7L9#2-0w5H5n5B5p5y190V5sca2K2F0M1Vc70w5q6P0X0Z0#0u04.
Optimisation

Le coût d'une recherche dans une liste (pour tester si un sommet a déjà été visité) est beaucoup plus important que le coût de la recherche dans un ensemble (hors programme NSI), ou dans un dictionnaire. ( Les tables de hash)

Nous allons donc proposer une autre version pour améliorer l'efficacité de l'algorithme.

  • Un sommet est "parcouru" lorsqu'il a été mis dans la liste parcours
  • Un sommet est "en attente" lorqu'il est dans la file.
  • Tous les autres sommets sont "pas vu".

Compléter le script suivant :

def parcours_largeur_opt(graphe, depart):
file = [depart]
parcours = []
etat = {sommet: "pas vu" for sommet in graphe}
etat[depart] = "en attente"
while file != []:
sommet = file.pop(0)
parcours.append(sommet)
etat[sommet] = ...
for voisin in graphe[sommet]:
if etat[voisin] == ...:
...
...
return parcours
# Test
assert parcours_largeur_opt({"A": ["B", "D", "E"],"B": ["A", "C"], "C": ["B", "D"],
"D": ["A", "C", "E"], "E": ["A", "D", "F", "G"], "F": ["E", "G"], "G": ["E", "F", "H"],
"H": ["G"]},"A") == ['A', 'B', 'D', 'E', 'C', 'F', 'G', 'H']
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
rounded
>>> 
 
x
x
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013l(9 _4:;=vm26!-uS8w.s3/]fr7g}ebh[pPic05qa,{onkyd1)t050W0E0Z0P0K0b0v0e0L0b0P0v0v0j010Z0K0I010406050v0q0l0l0P0A0V040r0S0b0q0@0S0T050x0~1012140|0I04051k1d1n0x1k0|0W0K0k0,0.0:0=0.0T0C0q0P0C0E0p0I0V0Z0G1b0e0G0K0C0G0b1P0G0Z0`050%0F0b0E1w0/0;011O1Q1S1Q0Z1Y1!1W0Z0A1l1K0,170v0I0P0T0=0m011$1y010z0)0E0T0P0l0E1W1{1}221(251!282a0`0a0e0J0A0S0I0S0v0K1a0T0e0#1_0A0A0E0L2v1d2d0T1l0x1K2I1=1@1?1X0W2f1z0K0T272s1W1t1v0-1%2S2U0T0S2Y1W0I2B1l2G2I2/0}1|2w2!232(0A110b1W0P1N2B0z0=030f0f0L2)0E1S2%0S0p0m0p0X0`0e0X1d0P2:2?0{2=2e2^1(2`2|2~300E32013436383a2V3d3d3h0m3k3m1}3o2G2R013t0P2}1l2 0G313335370#3D2(3F0w3h0w3J2F3n0|3N3r0=3Q3S053U3W3z3Y3C2T3E3e0g3h0g3+1e3-3p2@1x3s0S2{3R3v3V3x3X3B3!3}3$3e0N3h0N432/3.2?3O3=4d3_3A3Z394j3c3e0n3h0n4p453/483;4a3u3T3w3y4x3|3b3F0B3h0B4G3L4r3q4J3P4L4c4N4e4P3{4i4S3e0s3h0s4X2H4Z472#4$4b3?3^4f3`4h4z4.0p0d3h0d4?3M4s3:4{4M3@4O4g4y3#4B3f0M0`0X0M584^4t4%4}5f505h4A3F0X3g045z5p465r4|4v4 4Q4-3~3f205B3I0x3l3,4Y5E5b4u4)4w4,525L0X3(5B3*5Q3K4@5U4#5W5e4*5g4R5#405B425*5S2H1o2-1d2Y2L0W1@2Q5b4y2X1u1l2,0E2.3n5|1l4y6d2e0K0W0=352G5y3v6k6m515i6p0e2j0E6s5w535A3+4I4`0U0`0#0z6f5-4`0t3h6K6E2_0z0`1|0A370q0A0v0f0.0A1F6X0f2q0Z6P5a4#0_040c6,4!4`0T0`0C0A0P0I0G0E6=4_236/0Q6f0e6L2_6H0E6U6+443L771(6/0Y0h750e0e0|7d5}3N6r016n2?3F5N5e7r5Z6u3e206w296y7s6t5x7B1W5*7l7l7f3;0`2h6 7o04766Q1(0S0`0j757O016/0H704t797b7*5b6/0y6f7n2;7q6l7G6o3e5%7x7_7z7I0p3(7D2a6z5?4k827K3l7M7V6-6@6T126W6Y7#7W0=7Y047!7T8d6?720`0H7;7T7?6e7^6s7{0p5^7~865K8840847F80538E7L7M7$6^040$0P7c2/8r717X7Z8k8e8t040R7.5.0`0v0S100$8+4`6/7j8q7$0v5N020O0q0S0Z0i1|0+0k0q8}8 918$8s1(6G040z4a9a8Z7P048.8:8W3n8Y3O0S6N042T9h7+046`6|6~8=8(0D7=7*7y0f8C4m4N9G6A5L4m8K8G5!889J3J8c8R0`8U9n7e8l7%8u9B3s7,129Z7p8%7g0`8w8X7$8n8p9=9#8{0`97900i270e8V0Z27a39}998x9F7 9H7u4C6qaa9M884D9P7Gag5j4D2I8b8Q9#9d0t1O1!9v5V7Q26aw4#8n0o9^9o7$7(0y8^4qa98Bac0p4U9Kaf875j4Uaj8M5LaP9U8caq9.9j9l2a9,7U9?8#8_9#8S7R9(8m0`0ua=3P6T2qa_6/6;7T7$0l0K0`5ob09#7h9Eb64s9G8C4:aQ9Q7A0p4:aV7H53beaZa!9pax046U8i0va_8na^ba9b9j6|0I270Wa}0`a 7@a$a`9k8/a)bG040Y758y9!bbaa8C55bfakaS3F55bkalb$8a7Ubpbq8,8T0%a*aG9%bz9ibLa(8;b^3O7:aA4`9@c0239{04a60i95c7b9bJ6jbWaN5naebg81cgb(b#3ecgaob,bp7$9d9f0Ac39)040k0S0K2t1ca.bK9r0`9ucEbAbL9y6}7Sccb_7(a_8Sb{b=b79:aJ45b}bccf6C2 9Lcm3f3gcl8H5j5zb+b-a!cscH6JcJb_8S9YbP7)b}brczcBcIcPb~9:cwa?8oaE3Lb.4`c5c7930ec98~9~bPcY5Tc!ce1}5y7wc(aRc.ds216xci6B7w8Pc=cra/ayavd0aBa@cS0`bCbEbPbI8zbK8Sd2cCbPbR8qbT9-cdaMdrcn7}dudA5#83dzb!dwd)c;dEdFdT9Xb;c~dMcycAdWdJ8?d7c`9qa-9_bKdfdk91a0a2a40Ecaa8dpd%0T5y8Ed+d:9Rc/8Jd/aW880X8Oap7Nar0`2B0Z6XcDe7cK8Sbt0S6Xbveh2;0x6h5~6c60691d0Z63eU2O2J0P1ZeR0x617n0#0%0)0v04.

Distances croissantes

On peut remarquer que l'algorithme de parcours en largeur permet de dresser la liste des sommets d'un graphe par distance croissante au sommet d'origine

largeur

A partir du sommet A représenté en bleu,on a par distance croissante :

  • Les sommets à une distance de 1 du sommet A représentés en vert : B, D, E
  • Les sommets à une distance de 2 du sommet A représentés en rouge : C, F, G
  • Le sommet à une distance de 3 du sommet A représenté en jaune : H

On retrouve bien dans la liste renvoyée par la fonction de parcours en largeur à partir du sommet A les sommets classés par ordre de distance croissante au sommet A : ['A', 'B', 'D', 'E', 'C', 'F', 'G', 'H'].

Note

💡 On peut se servir du parcours en largeur pour trouver un chemin de distance minimale entre deux sommets.

IV. Le parcours en profondeur⚓︎

1. Le parcours en profondeur récursif⚓︎

Une première approche⚓︎

Parcours en profondeur

Parcours en profondeur ou DFS en anglais pour Depth First Search

Le parcours en profondeur est un parcours où on va aller «le plus loin possible» sans se préoccuper dans un premier temps des autres voisins non visités :

On va visiter le premier des voisins du sommet non traités, puis faire de même avec lui (visiter le premier de ses voisins non traités), etc. Lorsqu'il n'y a plus de voisin, on revient en arrière pour aller voir le dernier voisin non visité.

Dans un labyrinthe, ce parcours s'explique très bien : on prend par exemple tous les chemins sur la droite jusqu'à rencontrer un mur, auquel cas on revient au dernier embranchement et on prend un autre chemin, puis on repart à droite, etc. Attention, pour ne pas tourner en rond autour d'un bloc, il faut marquer les endroits par lesquels on est déjà passés.

C'est un parcours qui s'écrit naturellement de manière récursive.

Méthode récursive

L’ensemble des sommets déjà visités est stocké dans un objet Python (liste, ou dictionnaire, ou ensemble).

La visite est relancée récursivement pour chaque voisin du sommet visité qui n'a pas déjà été visité.

A vous

Compléter le code de la fonction parcours_profondeur qui parcourt en profondeur un graphe à partir du sommet sommet et dont sa liste d'adjacence est representée par un dictionnaire nommé graphe.

Cette fonction renverra la liste des sommets parcourus en partant du sommet depart.

🌵 Il peut falloir plusieurs lignes de code pour remplacer les ...

Graphe du test :

graphe largeur

def parcours_profondeur(graphe, depart, vus = None):
if vus is None:
vus = []
vus.append(depart)
for voisin in graphe[depart]:
...
return vus
# Tests
assert parcours_profondeur({"A": ["B", "D", "E"],"B": ["A", "C"], "C": ["B", "D"],
"D": ["A", "C", "E"], "E": ["A", "D", "F", "G"], "F": ["E", "G"], "G": ["E", "F", "H"],
"H": ["G"]}, "A") == ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
rounded
>>> 
 
x
x
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013l(A _4:;=vm26-uS8w.Rs3/]fr7gebh[pPicNq5a,onkyd1)t050U0D0X0O0J0b0v0e0K0b0O0v0v0j010X0J0H010406050v0p0l0l0O0A0T040q0Q0b0p0=0Q0R0e020O0l0H0i0e0u0D0 0A0M0p0D0v050x0|0~10120`0H04051x1q1A0x1x0`0U0J0k0*0,0.0:0,0R0C0p0O0C0D0o0H0T0X0F190e0F0J0C0F0b1$0F0X0^050#0E0b0D1J0-0/011#1%1)1%0X1/1;1-0X0A1y1X0*150v0H0O0R0:0m011?1L010z0%0D0R1d0D1-282a2f1^2i1;2l0l2n040a0e0I0A0Q0H0Q0v0J181a0Z260A0A0D0K2I1q2p0R1y0x1X2U2224231.0U2r1M0J0R2k2F1-1G1I0+1@2(2*0R0Q2.1-0H2N1y2S2U2~0{291a2:2g2@0A0 0b1-0O1!2N0z0:030f0f0K2^0D1)2?0Q0o0w0o0V0^0V1q0O2 320_312q341^36383a3c0D3e013g3i3k3m2+3p0o2d040m3v3x2a3z2S2%013E0O391y3b0F3d3f3h3j0Z3O2@3Q0w0^0w3V2R3y0`3Z3C0:3$3(053*3,3K3.3N2)3P3q0g0^0g3`1r3|3A331K3D0Q373%3G3+3I3-3M3:493=3q0N0^0N4f2~3}323!414p453L3/3l4v3o3q0n0^0n4B4h3~4k404m3F3)3H3J4J483n3Q0B0^0B4S3X4D3B4V3#4X4o4Z4q4#474u4(3q0r0^0r4-2T1B2|1q2.2X0U242$3 014K2-1H1y2{0D2}3y3{3X054K5k2q0J0U0:3h2S3Q3s4Z5s5u4t4L4}3r2e2v0D5B4K3;4N5F2U3w4i3!0S0^0Z0z5m534U2;010s0^0e5W5q4j5Z0R0z0^290A3j0p0A0v0f2{0Q0z190Z5=5(5Q5c0@040c5 5Y350^0C0A0O0H0F0D654E610^0P5(5%663D5T0D5/0X6f4:5Z626j4g3X6l6g4;0R0^0k0p1p6x2T6z6t2g0Q0^0j6k604;0S0K0^0L196e6H5)3!620W0h5(0`6Y5Q5A015v323Q3S430e6,4{5D4a3R5G2m5J4%6`6;0x3w0e746J5*2g5S040J5V6Y764F6D6F6k7e5c0Q5#7a6G2~7j6R6T046V2*6s771^626%6Y6)303Z6@0f5w3q3@5z5t6-5C5L3?6|2w6~4|6`7J3V757X7q5+7g7o3y7Z6L6N6P6m0:620G0y6(7w6?7L6.2a3Q4c7K7S6_4w0o4c0e5H7}7O4b1-72047X6Q7!046E7$5n7,016M040t7=5c6C046b0H2k0U8m4;62646*8h8o0Z6q8u6u0^0W7;8y4E7F7H0o4y7|7M5K4M3Q4y826}8P6 7 8N7W758b780^5{0A7+6A8c0k0Q0J2G0R8+6K1^7l0^2)8?7x40686a6c6X7D8,2g7.8D67048B106r8I8@7-0^0y7A4C7=8K6/4O3G7F8Q5E4P8U7R8W7T7 4P5O897Y748$1^797b8|7f8d8/8;9H7k7m2@9c7p9D0:8_7a8=7d9S3#7#977y0^9i4h9d1a9l7_3q4*8O6^850o4*9t5I9v7~5M9/8!9B8a8z5.105;5?5^2C5{0R5}8*9*6!0^8x939e9Z04696b6d9#9f046w9Ra19J8:8{ac6hap9M6B9!aw8v8F8Hag9+7@7G9m0o4 9:7N8R4~7Q9_9;aPaL87738#8h792N0X5=9War946n8d7h7B5 0x5p545j565g1q0X59a_2!2V0O1:a?0x571w6Z5c2N0l0f0z0O0S0D0f0F7J1i1k1m1o0e9(5n1D3z1x0d172N0e0v15170J1Z2E0.0Jb0bl5%bo1F1H3!1N1P1R1T1V1X1Z1`1(1*1,b54;2t2k2m0^0I1W1Ya(5l5i5)3W53a;7EaI5w0g5N6=9p8X3ob=3s9^848Rb{2e4_4s9q3Pc09z9Y795Uan5!5$cb5,a25:0Q5=5@5_a8aacb8wce8 al925l8h6vaz8c9a0A9Qcua*aoaq7%9Y8o8ecx7)046O9XaZ7s7uct8gcD016#bm2T7CcC5rb:6/b=6;3bb^9wb`6{b}9`7Oc(c14IaT4(c=9za0cU9F7ca)ahcIa-d08}8i7m8:cK9EcQ6Wco9%aFc!aH5Bb;3p9oaIc43=b=3@c/c^c5dk4!c3b_80dkc{9 cHaBd43!8jcNdEax7/dfcTc#dic%80dlb~c_dQdraOdT81c246dWdt7{9~7(9E8`c cG8h9U9Pd98~996p9bd;d68`b(6ydCa,8f5XcU7zdLe1dN7Mdj8Zc*dmdxb=8T83c:b 8Mc?4rd!dnc-8Z889 d)d=cJaC5Z8j8leu988q8sdd63cqd?8Cey9$048Ga.ac9,0Rdy9yb@ebc,ePaRdSdt9sdZ4$eTb=eQepdBaZ8(4md_cI9KavdI4;9Ue:d-cU8oak91eC0GeEczcBdMd5629he46ZeNdy9}eaeWdo9?eVegdT9@eZdsfd9}e(eq9Cas5/a4cka75|0D5~eHaoafdg9Ie{amfycV6ie-6De/d|e5f3fHcOe_dDfBaxeK9jeMc$7_b=aMeRfcc-4 dVemdyf(fjd#fdf!fner01a!0!a%fId f61qa;1D55b25g6)0Z0#0%0v04.
return ou pas return ?

Testons sur le graphe suivant :

Dans les deux cas suivants la différence se situe ligne 7.

Sans return pour l'appel récursif de la fonction

Avec return pour l'appel récursif de la fonction

Que s'est-il passé ?

Solution

Le return devant l'appel récursif empêche de remonter au sommet A, pour explorer la branche suivante.
On est coincé dans un cul de sac.

Optimisation⚓︎

Optimisation

Le coût d'une recherche dans une liste (pour tester si un sommet a déjà été visité) est beaucoup plus important que le coût de la recherche dans un ensemble (hors programme NSI), ou dans un dictionnaire.

Nous allons donc proposer une autre version pour améliorer l'efficacité de l'algorithme.

A vous

Compléter le script.

Graphe du test :

graphe largeur

def profondeur_opt(graphe, depart, vu = None, parcours = None):
if vu is None:
vu = {sommet : False for sommet in graphe}
if parcours is None:
parcours = []
vu[depart] = True
parcours.append(...)
for voisin in graphe[depart]:
if ...:
...
return vu, parcours
# Tests
print(profondeur_opt({"A": ["B", "D", "E"],"B": ["A", "C"], "C": ["B", "D"],
"D": ["A", "C", "E"], "E": ["A", "D", "F", "G"], "F": ["E", "G"], "G": ["E", "F", "H"],
"H": ["G"]}, "A"))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
rounded
>>> 
 
x
x
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013l(9 _4:=vTm26-uS8w.s3/]fr7g}ebh[pPicN05a,{onkFyd1)t050W0D0Z0O0J0b0u0e0K0b0O0u0u0i010Z0J0H010406050u0p0l0l0O0z0V040q0R0b0p0@0R0S050w0~1012140|0H04051k1d1n0w1k0|0W0J0j0,0.0:0=0.0S0B0p0O0B0D0o0H0V0Z0F1b0e0F0J0B0F0b1P0F0Z0`050%0E0b0D1w0/0;011O1Q1S1Q0Z1Y1!1W0Z0z1l1K0,170u0H0O0S0=0m011$1y010y0)0D0S0O0l0D1W1{1}221(251!282a0`0a0e0I0z0R0H0R0u0J1a0S0e0#1_0z0z0D0K2v1d2d0S1l0w1K2I1=1@1?1X0W2f1z0J0S272s1W1t1v0-1%2S2U0S0R2Y1W0H2B1l2G2I2/0}1|2w2!232(0z110b1W0O1N2B0y0=030f0f0K2)0D1S2%0R0o0N0o0X0`0e0X1d0O2:2?0{2=2e2^1(2`2|2~300D32013436383a2V3d0o20040e0m3k3m1}3o2G2R013t0O2}1l2 0F313335370#3D2(3F0v3h0v3L2F3n0|3P3r0=3S3U053W3Y3z3!3C2T3E3e0g3h0g3-1e3/3p2@1x3s0R2{3T3v3X3x3Z3B3$3 3(3e0N3h0N452/3:2?3Q3@4f3{3A3#394l3c3e0n3h0n4r473;4a3?4c3u3V3w3y4z3~3b3F0A3h0A4I3N4t3q4L3R4N4e4P4g4R3}4k4U3e0r3h0r4Z2H4#492#4(4d3^3`4h3|4j4B4:0o0d3h0d4^3O4u3=4}4O3_4Q4i4A3%4D3f0M0`0X0M5a4`4v4)4 5h525j4C3F0X3g045B5a1o2-1d2Y2L0W1@2Q5d4A2X1u1l2,0D2.3n3.3N054A5V2e0J0W0=352G5A3v5%5)535k5,0e2j0D5/5y555C3-4K4|0T0`0#0y5X2H483Q0s3h645#4{2_0y0`2,0R0y1b0#0p0z0f2q0Z6a665d0_040c6q5~2_0`0B0z0O0H0F0D6w5c4%6t0P6a0e6r4%0S610D1|0z6p465Y6x1(6J6L6N4|6P040j0p6!6X0=0R0`0i6+6H5 0K0`0L1b6F6V656,016Z6|3I6#6y046S376l0u6;4$4|6.046:716M6~0T6@046_2U6G7b236t0Y0h6a0|71665.015*2?3F3H5g7y4.54403G215@5_4T7I7D0w3l0e7S7h6=2360040J637g733s0`6)7a6c1(0R687Y797#7i7k7m6{2;6~6t7t717v7_4u7F0f5+3e3*4P815`7I3*5?295^7z5:5z841W7Q3I7T8l7$3?7(6*7;7V7,6/7*3Q6t0Q7o7+8o040u0R100$8v6s0`7|2/7U7p1(7j0`0U3T0u7^3n8M8A017X6i0z8H6O0`8D8F6U8L8n017-0`2T8$6$6z6B6D8U6W8s0=6t0C7u8z0e81830o42865(8e884m957K8c7M4/7I963L8m7i8:7!8,6~6%760R786L8W3Q8/7/8=7W7?6`918I048K477w3P937B4n5-987G5;9M8b2a9f7H9b4o2I7R8l9k8|3R6f12770z7:9o9$7d7f9-8N8}0`0G0x909I809O829L0o4F979U9Qa09d9T997N9ba19j7T8-6%7)9{9=6 9@9D8%040#6S8+5W7`0`9_8rai9/9z8O7k0k0z0p8`4_919K1}4V9Na38g0o4W9S8d9PaM4W9Y8k7Sae9(0z9*9,ar9.0`0tal8?046C0H270Wa*7q0`6vah8X6%ao12aq8{ai7r9`7 5$9}944=a2a89g9b4=aPaL55b6acaW9l048!ay8B0j0R0J2t1cav8X9x8;bs4v8@6C6Ea;6Yaka^bxan6Ra|bB9?040x9G4!aGb49 57b7aR5557bcb89V5lbSbg9!8-7X7Zbl8.7.2(a}2H9v5daf8qb28X6t0GbJ9%6(bobqb|6tbMb1a$b35/945paKbYa4c9bXbU7Ic9aU9!cjb;am6g6i0S6k6m6oc1a?b|6%6AbzaE6b8w0`6Kbwb=7(b bvb^cB04cD9;a_8pctcLb+9q9)9s9+cQ0Yc4a~2waH0S5A5|2 87a95l5Ba6aQ8f5{5|8j9#ai7X2B0Z6lbrcNbFagcJ9EcM8VaX75cU9t7}6q0w5!5G5U5I5R1d0Z5Ldi2O2J0O1Zdf0w5J7v0#0%0)0u04.
Autre possibilité

On peut aussi construire le parcours par concaténation de listes.

Tester ci-dessous :

def parcours_profondeur_rec_N(graphe, sommet, vus = None):
if vus is None:
vus = {s: False for s in graphe}
parcours = [sommet]
vus[sommet] = True
for voisin in graphe[sommet]:
if not vus[voisin]:
parcours += parcours_profondeur_rec_N(graphe, voisin, vus)
return parcours
# Tests
print(parcours_profondeur_rec_N({"A": ["B", "D", "E"],"B": ["A", "C"], "C": ["B", "D"],
"D": ["A", "C", "E"], "E": ["A", "D", "F", "G"], "F": ["E", "G"], "G": ["E", "F", "H"],
"H": ["G"]}, "A"))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
rounded
>>> 
 
x
x
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier

Visualiser l'exécution

Vous pouvez voir l'exécution avec le graphe suivant ici :

Avec Python Tutor

2. Le parcours en profondeur itératif⚓︎

Une première approche⚓︎

Algorithme itératif avec une pile

Comme nous l'avons vu dans la vidéo, on peut aussi utiliser une pile.

✍ A noter ... et à mémoriser ... 🐘

parcours est la liste vide qui contiendra les sommets visités par parcours en profondeur
P est une pile vide
On empile un sommet dans P
Tant que P n'est pas vide
    S = dépile(P)
    On ajoute S à parcours
    On empile les voisins de S qui ne sont ni dans la pile ni dans parcours
Fin Tant Que

👉 9 étapes :

A vous

Ecrire le code d'une fonction parcours_en_profondeur qui parcourt en profondeur un graphe à partir du sommet depart et dont sa liste d'adjacence est representée par un dictionnaire nommé graphe

Cette fonction renverra la liste des sommets parcourus en partant du sommet depart.

Compléter le script ci-dessous de façon itérative :

Graphe du test :

graphe largeur

def parcours_en_profondeur(graphe, depart):
pile = ...
parcours = []
...
return parcours
# Tests
assert parcours_en_profondeur({"A": ["B", "D", "E"],"B": ["A", "C"], "C": ["B", "D"],
"D": ["A", "C", "E"], "E": ["A", "D", "F", "G"], "F": ["E", "G"], "G": ["E", "F", "H"],
"H": ["G"]},"A") == ['A', 'E', 'G', 'H', 'F', 'D', 'C', 'B']
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
rounded
>>> 
 
x
x
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013l(9 _4:=vm26!-uS8w.s3/]fr7gebh[pPic05a,onkyd1)t050S0C0V0M0I0b0u0e0J0b0M0u0u0i010V0I0G010406050u0p0k0k0M0z0R040q0O0b0p0:0O0P050w0`0|0~100^0G04051g191j0w1g0^0S0I0j0(0*0,0.0*0P0B0p0M0B0C0o0G0R0V0E170e0E0I0B0E0b1L0E0V0?050Z0D0b0C1s0+0-011K1M1O1M0V1U1W1S0V0z1h1G0(130u0G0M0P0.0l011Y1u010y0#0C0P0M0k0C1S1@1_1~1!211W24260?0a0e0H0z0O0G0O0u0I160P0e0X1=0z0z0C0J2r19290P1h0w1G2E1.1:1/1T0S2b1v0I0P232o1S1p1r0)1Z2O2Q0P0O2U1S0G2x1h2C2E2+0_1^2s2W1 2!0z0}0b1S0M1J2x0y0.030f0f0J2#0C1O2Z0O0o0m0o0T0?0e0T190M2,2/0@2.2a2;1!2?2^2`2|0C2~01303234362R390o1|040e0l3g3i1_3k2C2N013p0M2_1h2{0E2}2 31330X3z2!3B0v3d0v3H2B3j0^3L3n0.3O3Q053S3U3v3W3y2P3A3a0g3d0g3)1a3+3l2:1t3o0O2@3P3r3T3t3V3x3Y3{3!3a0L3d0L412+3,2/3M3:4b3@3w3X354h383a0m3d0m4n433-463/483q3R3s3u4v3`373B0A3d0A4E3J4p3m4H3N4J4a4L4c4N3_4g4Q3a0r3d0r4V2D4X452X4!493;3?4d3^4f4x4,0o0d3d0d4;3K4q3.4_4K3=4M4e4w3Z4z3b0K0?0T0K564?4r4#4{5d4~5f4y3B0T3c045x561k2)192U2H0S1:2M594w2T1q1h2(0C2*3j3*3J054w5R2a0I0S0.312C5w3r5Z5#4 5g5(0e2f0C5+5u515y3)4G4^0Q0?0X0y5T2D443M0s3d605X4@2=0y0?1^0z330p0z0u0f230f2(0O0y170X6f6662590=040c6r5`2=0?0B0z0M0G0E0C6x584Z6u0N660e6s4Z0P5}0C6c0V6H4Y4^6u0U0h6M0e0e0^425U3L5*015$2/3B3D5c6,4*503|3C1}5:5=4P6_6;0w3h6$6$6O4^6Q040G226M751 0O0?0i7b6y1!6u0F6V683o6R6T7m3M6u0x666(2-6+5!6-0f5%3a3$4L6?5,5v7D6{255;7A5?6_7E3H736N7i3/6b0~6e6g7h6I4^7e047g6)2D7T7#1 7k7u7*3k7;627G7C0o3~7F7z6@5-3}7K266}4+6_7{7R737c1!5|040s1K1W7!6W2=0D0?2e7r6t0?6w7?7U3N6b7a8q7-7j0?0U8g7n0.7%0n7)2+7,8h1!0k0I0?5m8v8I0.6u6!7;7w5S7y5+7_4k7|836^4i0o4k5/7L8#7 8(1S713E7S888r770u0O0|0Y8A3M7%8F3j8H8B8s788u7x8w8C0?0t8m6P6b2m9c6X8o8z8T7r7^6/4A5)7}7H514B8*827N6~8%4B2E728=748@7W6d0O6f0u9g7d9a9K7o046D0G230S9N8Q8o9U948_8{6U8O936Y7v9l9q7_4S8!9w848%4S9u7M7~7I0o9-879C897V040j0O0I2p0P9J7;928~7f8}59776B6D6F9X7k9X8^8`269#978P017t9)9$0e9m1_3B4.9.9^514.9?8,9_ay9|8=9~018b6n0zab9da0a2a4aO7$64042PaT6zaQa32Pa6ao9%0?8S4o9*8X9n529paE5153aD9/8$5h539A8;9C7SaJ8b0I5 a7aJ0OaV2!an8V98aq9Watac0?a1a#18b58rb70?aXblbc776c7Ya%bbap9(bqapbn9P0P9Tbz93bBb9ahbea(4rbhaRbp8Gb6aVbP91aJbs96bwa)046ZasbLav0P5w5jaz9r6_5l819@b-8%b/a}a b_a8bg958fbf4Z7%9bb 760?9Q9SbJ6vajbNbjc89ja,atb(5w5^2{7G7Ob?3ca^aAb.5^8:b08r8b2x0V6fbkbQ9E787X9H7Z9k7?0w5W5C5Q5E5N190V5HcP2K2F0M1VcM0w5F6(0X0Z0#0u04.

Différents parcours en profondeur ?⚓︎

Il y a souvent plusieurs possibilités

Observez les résultats obtenus pour le parcours en profondeur par algorithme récursif, ou itératif.

🌵 Les parcours obtenus sont différents. De plus, suivant l'ordre des listes d'adjacences, on obtiendra aussi des résultats de parcours différents.

🎲 Dans la vidéo d'introduction, on était amené à faire des choix arbitraires.

Optimisation⚓︎

Optimisation

Le coût d'une recherche dans une liste (pour tester si un sommet a déjà été visité) est beaucoup plus important que le coût de la recherche dans un ensemble (hors programme NSI), ou dans un dictionnaire.

Nous allons donc proposer une autre version pour améliorer l'efficacité de l'algorithme.

A vous
  • Un sommet est "parcouru" lorsqu'il a été mis dans la liste parcours
  • Un sommet est "en attente" lorqu'il est dans la pile.
  • Tous les autres sommets sont "pas vu".

Graphe du test :

graphe largeur

def parcours_profondeur_iteratif(graphe, depart):
parcours = []
etat = {sommet: "pas vu" for sommet in graphe}
pile = [...]
etat[depart] = "en attente"
while len(pile) != 0: # ou pile != []
sommet = ...
parcours.append(...)
etat[sommet] = "parcouru"
voisins = ...
for voisin in ...:
if etat[voisin] == "pas vu":
pile.append(...)
etat[voisin]= ...
return parcours
# Tests
assert parcours_profondeur_iteratif({"A": ["B", "D", "E"],"B": ["A", "C"], "C": ["B", "D"],
"D": ["A", "C", "E"], "E": ["A", "D", "F", "G"], "F": ["E", "G"], "G": ["E", "F", "H"],
"H": ["G"]}, "A") == ['A', 'E', 'G', 'H', 'F', 'D', 'C', 'B']
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
rounded
>>> 
 
x
x
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013l(9 _4:;=vm26!-uS8w.s3/]fr7g}ebh[pPic05qa,{onkyd1)t050W0E0Z0P0K0b0v0e0L0b0P0v0v0j010Z0K0I010406050v0q0l0l0P0A0V040r0S0b0q0@0S0T050x0~1012140|0I04051k1d1n0x1k0|0W0K0k0,0.0:0=0.0T0C0q0P0C0E0p0I0V0Z0G1b0e0G0K0C0G0b1P0G0Z0`050%0F0b0E1w0/0;011O1Q1S1Q0Z1Y1!1W0Z0A1l1K0,170v0I0P0T0=0m011$1y010z0)0E0T0P0l0E1W1{1}221(251!282a0`0a0e0J0A0S0I0S0v0K1a0T0e0#1_0A0A0E0L2v1d2d0T1l0x1K2I1=1@1?1X0W2f1z0K0T272s1W1t1v0-1%2S2U0T0S2Y1W0I2B1l2G2I2/0}1|2w2!232(0A110b1W0P1N2B0z0=030f0f0L2)0E1S2%0S0p0B0p0X0`0e0X1d0P2:2?0{2=2e2^1(2`2|2~300E32013436383a2V3d0p20040e0m3k3m1}3o2G2R013t0P2}1l2 0G313335370#3D2(3F0w3h0w3L2F3n0|3P3r0=3S3U053W3Y3z3!3C2T3E3e0g3h0g3-1e3/3p2@1x3s0S2{3T3v3X3x3Z3B3$3 3(3e0N3h0N452/3:2?3Q3@4f3{3A3#394l3c3e0n3h0n4r473;4a3?4c3u3V3w3y4z3~3b3F0B3h0B4I3N4t3q4L3R4N4e4P4g4R3}4k4U3e0s3h0s4Z2H4#492#4(4d3^3`4h3|4j4B4:0p0d3h0d4^3O4u3=4}4O3_4Q4i4A3%4D3f0M0`0X0M5a4`4v4)4 5h525j4C3F0X3g045B5r485t4~4x514S4/403f3H0X3K0x3l3.4!5G5d4w4+4y4.545N0X3*5D3,5S3M4_5W4%5Y5g4,5i4T5%425D445,5U5.4K4|5;504-535k5A4o5D4q5}463N1o2-1d2Y2L0W1@2Q5d4A2X1u1l2,0E2.3n5~1l4A6t2e0K0W0=352G5A3v6A6C655z3e3g0e2j0E6I5y555C3-60230U0`0#0z6v5/4|0t3h6#6V3s0z0`1|0A370q0A0v0f2,0S0z1b0#6=0f2u0E0A0P0@6!6c2H6$230_040c6*5c5:0`0C720I0G0E7d4$4|7a0Q6v0e783s6Y0E6/0Z7m4{790`0Y0h7r0e0e0|766y2w6H016D2?3F3H5g7M5#663e206N296P7N6J557R5,7G7G7t3?6.126;6?7r7,010S0`0j7=6+0=7a0H0y6v7I2;3P7T0f6E3e5)7S6B7#6R5N3*7Y2a6Q5^4m0p897)7*7?0T0`0$737{7e4|7^047`7J7s7|017a0R7z4v0`0v0S100$8G5d7a7E8A7?0v3H020O0q0S0Z0i1|0+0k0q8V8X8Z8u7n6W0`6{0A8,7A7u048J8L7y8R8C0S6(042T8=8H047h0P7j7l7J7?7a0D818G85870p5`8a8i5M8k428g7!7U6K9h1W8n7+8C8q040I26925d8x8z2/8B8v7B040H8N7f040#7x9L7o0`807J826u848b7O1}3F689j8c8j5l4o9o9k5$8k9$9u9G8-8@8s8{839H1(7~9Q2_7v9P998C7a9T9F7?9D9B4%8T0`8)8Y0i270e730Z27ajad8+9U9e9Y867P4E6Gaq8d8k4F9,9(9l5l4F2I3l7*9=8?0=6X040t1O1!a9610F0`2i9~9|0`7ca29{7-9y9AaY9?7}7CaP238x0o9E3naH3Q0l0K0`5qa%aI8D0`8Q4sap6I9g4W4P85aw5l4Waz9q55b33LaGaG8p8I8K2a9_a:a77_a+8@9zaOa`3Q8x0uaUa!2r0Ibwa|7b0Y9dbs9fas0p4=b4av9)3F4=b97$5NbJbdbe9vaZ3R7.6:0S6=0vbAbubA9x960I270WbA7aaX9`a(bX8^bi8Mbs8Oa*aobFaq9g57bK9-7V56216Oc49rc2bTbUbg049^b/0`9Kb{9M8_bjch04a5bl8}bn8|bWab04am8!7/b!0A8(8WaebEb=7Lc0bH5pauc96S5nbPb65A5naE3IbUa;5X0`0k0S0K2t0Tb$cub?a8c*a{9x9597cocjcH93cmb`c@b|cpcG9W4ubG9!6L6T2 b5bMd3c77ZcN5%6T9;bf8CaK8:boa!c!c$91c-bt8 dna69wcZc#c%c)c{4%8Pc~6d9Xb1cK7Rd5bLaB5A7Xc8aA9.5l5Q9taFcWdfbWaK0K75dsbW9xcgck9R9Jb)dudm1cd%9Icq3NcX4%9Da/d;8S8UcE8Z8#0e8%cycoa~a:7Hb07#9g5(cMdNc5e9cQd73f8mdSdTcddta#brdy8w0`bvd.8@b+b-cob;c b?9xdlc%cobDb~c@d10T5A9idHdb8k0X9ndMba5_dRcVejbeced$eo9Ic?eyc.d+eCesa)c}e*7@ctdZb?cwcyagaiak0Ee1eFe$0eeH67eaeReN9+eQbQf3eTdUb?aK2B0Z6=d-e:e%9ycAb#dB770x6x6e6s6g6p1d0Z6jft2O2J0P1Zfq0x6h7I0#0%0)0v04.

V. Bilan⚓︎

A retenir

  • Dans le parcours en largeur, on visite tous les sommets en «cercle concentriques» autour du sommet de départ : d’abord les voisins directs, puis les voisins des voisins directs etc, et on continue jusqu’à ce qu’il n’y ait plus de sommets à visiter.
    👉 On utilise une file.

  • Le parcours en profondeur d’un graphe à partir d’un sommet consiste à suivre les arêtes arbitrairement, en marquant les sommets déjà visités pour ne pas les visiter à nouveau. On avance le plus possible et on recule quand on est bloqué.
    👉 On utilise un algorithme récursif, ou une pile.

VI. Le labyrinthe⚓︎

TP : résolution d'un labyrinthe

Après avoir téléchargé le fichier, vous pourrez le lire à partir de Basthon

🌐 TD à télécharger : Fichier TP_resolution_labyrinthe_sujet.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"

😊 La correction est arrivée :

🌐 Fichier TP_resolution_labyrinthe_corr.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"

VII. Remarque⚓︎

Retour sur l'efficacité

🌵 ma_liste.pop(0)

Pour une question de simplification des codes, Nous avons souvent utilisé ma_liste.pop(0)

Ce n'est pas une façon efficace de procéder, car le temps d'exécution est proportionnel à la taille de la liste ma_liste

Recopier dans votre éditeur Python (pas sur Basthon) le script suivant, puis l'exécuter :

Python
import timeit
import matplotlib.pyplot as plt

def suppression_debut(lst):
    lst.pop(0)

# différentes tailles de listes notées n dans la suite
abscisse =  [(10**7)*i for i in range(1, 11)]
print(abscisse)
ordonnee = []

for n in abscisse:
    temps = 0
    for i in range(2):
        ma_liste = [0]*n # Création de liste de tailles n
        # Le chronométrage étant fait 2 fois, Il faut donc pour chaque mesure reprendre la liste initiale
        temps += timeit.timeit("suppression_debut(ma_liste)", number=1, globals=globals())
    ordonnee.append(temps)

# Graphique
plt.plot(abscisse, ordonnee, "ro") # en rouge
plt.show()
plt.close()

Résumé

👉 Pour pallier à ce problème, nous pouvons utiliser le deque du module collections

documentation deque

🌴 ma_liste.pop()

Recopier dans votre éditeur Python (pas sur Basthon) le script suivant, puis l'exécuter :

Python
import timeit
import matplotlib.pyplot as plt

def suppression_fin(lst):
    lst.pop()

# différentes tailles de listes notées n dans la suite
abscisse =  [(10**7)*i for i in range(1, 11)]
print(abscisse)
ordonnee = []

for n in abscisse:
    temps = 0
    for i in range(2):
        ma_liste = [0]*n # Création de liste de tailles n ne contenant que des 0
        # Le chronométrage étant fait 2 fois, Il faut donc pour chaque mesure reprendre la liste initiale
        temps += timeit.timeit("suppression_fin(ma_liste)", number=1, globals=globals())
    ordonnee.append(temps)

# Graphique
plt.plot(abscisse, ordonnee, "go") # en vert
plt.show()
plt.close()

Résumé

Nous observons que ma_liste.pop() est beaucoup plus rapide que ma_list.pop(0). En effet, pour supprimer le premier élément d'une liste, il faut tous les décaler d'un rang vers la gauche, alors que pour supprimer le dernier élément d'une liste, il suffit ... de supprimer le dernier élément de la liste 😅.

Voici les résultats obtenus par les deux méthodes pour 100 mesures (il faut plus de 10 minutes pour créer cette image)

  • Les listes ont des tailles allant de 1×107 à 10×107=108
  • Les résultats sont exprimés en secondes

pop() et pop(0)

VIII. Crédits⚓︎

Romain Janvier, Gilles Lassus, Hugues Malherbe, Nicolas Revéret, Jean-Louis Thirot.