Parcours en profondeur de graphe

Dans cet exercice, on considère un graphe non orienté représenté sous forme de listes d’adjacence. On suppose que les sommets sont numérotés de 0 à n-1.

Ainsi, le graphe suivant:

image du graphe 2024 sujet 21

sera représenté par la liste d’adjacence suivante:

adj = [[1, 2], [0, 3], [0], [1], [5], [4]]

On souhaite déterminer les sommets accessibles depuis un sommet donné dans le graphe. Pour cela, on va procéder à un parcours en profondeur du graphe.

Compléter les fonctions parcours et accessibles.

  • La fonction parcours prend en paramètres une liste d'adjacence liste_adjacence, un entier x reprĂ©sentant un sommet, et la liste des sommets accessibles sommets_accessibles Elle rĂ©alise un parcours en profondeur rĂ©cursif du graphe donnĂ© par les listes d'adjacence adjacence depuis le sommet x en accumulant les sommets rencontrĂ©s dans la liste sommets_accessibles

  • La fonction accessibles prend en paramètres une liste d'adjacence liste_adjacence, un entier x reprĂ©sentant un sommet.
    Elle renvoie la liste des sommets accessibles dans le graphe donné par la listes d'adjacence liste_adjacence depuis le sommet x

Exemples

Bug

Attention, les exemples donnés correspondent à un graphe orienté qui n'est pas celui représenté dans le sujet.

graphe orienté

Python Console Session
>>> accessibles([[1, 2], [0], [0, 3], [1], [5], [4]], 0)
[0, 1, 2, 3]
>>> accessibles([[1, 2], [0], [0, 3], [1], [5], [4]], 4)
[4, 5]
Compléter le code ci-dessous

###(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)
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:=vm26j-uS8w.s3/]fr7gebh[pPic05a,onkyd1x)t050S0C0W0M0I0b0u0e0J0b0M0u0u0i010W0I0G010406050u0p0k0k0M0z0R040q0O0b0p0;0O0P050w0{0}0 110_0G04051h1a1k0w1h0_0S0I0j0)0+0-0/0+0P0B0p0M0B0C0o0G0R0W0E180e0E0I0B0E0b1M0E0W0@050!0D0b0C1t0,0.011L1N1P1N0W1V1X1T0W0z1i1H0)140u0G0M0P0/0l011Z1v010y0$0C0P0M0k0C1T1^1`1 1#221X25270@0a0e0H0z0O0G0O0u0I170P0e0Y1?0z0z0C0J2s1a2a0P1i0w1H2F1/1;1:1U0S2c1w0I0P242p1T1q1s0*1!2P2R0P0O2V1T0G2y1i2D2F2,0`1_2t2X202#0z0~0b1T0M1K2y0y0/030f0f0J2$0C1P2!0O0o0T3a0@0e0T1a0M2-2:0^2/2b2=1#2@2_2{2}0C2 01313335372S3a0o1}040e0l3g3i1`3k2D2O013p0M2`1i2|0E2~3032340Y3z2#3B0v3d0v3H2C3j0_3L3n0/3O3Q053S3U3v3W3y2Q3A3b0g3d0g3)1b3+3l2;1u3o0O2^3P3r3T3t3V3x3Y3{3!3b0L3d0L412,3,2:3M3:4b3@3w3X364h393b0m3d0m4n433-463/483q3R3s3u4v3`383B0A3d0A4E3J4p3m4H3N4J4a4L4c4N3_4g4Q3b0r3d0r4V2E4X452Y4!493;3?4d3^4f4x4,0o0d3d0d4;3K4q3.4_4K3=4M4e4w3Z4z3a0K0@0T0K561l2*1a2V2I0S1;2N594w2U1r1i2)0C2+3j3*3J054w5D2b0I0S0/322D3B0T3r5L5N4 5g5Q1~2g0C5U5f4y5X2F3h443M0Q0@0Y0y5F2E5+590s3d5;5J4@2?0y0@1_0z340p0z0u5`5?4Z0?040c664G4^0P0@0M0S0n0M0J246l6c58680@0N5`0e676e0@0U6o4Y4^696s423J6u6d2?0@0u0O0}0Z0u0f6k6l0-0I1W0C656E5=6H1#690V0h5`0_6X5{0e5T015O2:3B3D5c6-4*503|3C5Y265!6.5V5%3b6=0w3h0e766G6p4^5-040I5:6*786A6I046y7f6v200O5^042#0W6t7m1#7o0@2Q7t6Z3/6J6L270W6O6Q6V2q6U6W2.7A01696%7f6)7M4q6@0f5P3b3$4L7V5$513$0e5Z5#4P6`7Z3H777:7g5|3o7C6M7F6P0J6R7J1X7L5E7N0O0@0t6z7?7B040M0G0G240S863M696b6*7u887k7T7h6!0@0V6(8f7V7X0o3~7!5M6 7$6`3~7)6}7+4+8C1T743E7;768k017b0y487z797i0R8T8o0/7w7c197l7N6f896i6k6m0C8f59690F8/4Z8)8m818U8p040x7Q2,0e7S8`5K8z6/1`3B4k8y8G6_4i0o4k8E279b5W4j8J758M7;8O8)6062648?6B0@8i8n873N6g8+6l0P6n8j7N6C8X9z8)8W9G8{0/9I8%9O9A046K7_7G7|7I6T7 9u206#6t925G3L8u6:4A5S9570514B9g6~6^9j0o4B5)3k9N945U8v4S9a8A7,9d4S9^9i710oa43)7N7b5/9$1#7p6ua09K5~899Y6S7Kaj9P9wau9T6h6j9D9F9y8g6r9J4r6xax6#8 43an6,9;8v4.a59`ac4.aaa68H9daR7/779p7^7E9X7}9!6VaG5983040ia.6q040F0x8saN9-973b53aS9=6`53aWaT51b0a#8N8(5 0 9s809+9S8hax8)az8,9E8.aN8:aF9R8Y9T8_bgbt9Q90a%9U7D6N7{a+atbpa@8r7R8taP9.5i9:ab515l6|9haX9c5hbS9~7:8O7b2y0W638$bzbbbB9WbE9ZbG4o660w5I5o5C5q5z1a0W5tb}2L2G0M6U2F5r6)0Y0!0$0u04.