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

.128013kg[: r)S/(.lo4y,6b=ac1x5ujd3t28_Pw7evp-fh09mn]is050B0K0D0u0V0m0W0f0v0m0u0W0W0t010D0V0M010406050W0z0S0S0u0g0p040i0n0m0z0;0n0T050j0{0}0 110_0M04051h1a1k0j1h0_0B0V0L0)0+0-0/0+0T0c0z0u0c0K0N0M0p0D0P180f0P0V0c0P0m1M0P0D0@050!0s0m0K1t0,0.011L1N1P1N0D1V1X1T0D0g1i1H0)140W0M0u0T0/0E011Z1v010O0$0K0T0u0S0K1T1^1`1 1#221X25270@0a0f0H0g0n0M0n0W0V170T0f0Y1?0g0g0K0v2s1a2a0T1i0j1H2F1/1;1:1U0B2c1w0V0T242p1T1q1s0*1!2P2R0T0n2V1T0M2y1i2D2F2,0`1_2t2X202#0g0~0m1T0u1K2y0O0/030G0G0v2$0K1P2!0n0N0w3a0@0f0w1a0u2-2:0^2/2b2=1#2@2_2{2}0K2 01313335372S3a0N1}040f0E3g3i1`3k2D2O013p0u2`1i2|0P2~3032340Y3z2#3B0C3d0C3H2C3j0_3L3n0/3O3Q053S3U3v3W3y2Q3A3b0o3d0o3)1b3+3l2;1u3o0n2^3P3r3T3t3V3x3Y3{3!3b0y3d0y412,3,2:3M3:4b3@3w3X364h393b0r3d0r4n433-463/483q3R3s3u4v3`383B0J3d0J4E3J4p3m4H3N4J4a4L4c4N3_4g4Q3b0F3d0F4V2E4X452Y4!493;3?4d3^4f4x4,0N0R3d0R4;3K4q3.4_4K3=4M4e4w3Z4z3a0Q0@0w0Q561l2*1a2V2I0B1;2N594w2U1r1i2)0K2+3j3*3J054w5D2b0V0B0/322D3B0w3r5L5N4 5g5Q1~2g0K5U5f4y5X2F3h443M0b0@0Y0O5F2E0f5+590T0O0@1_0g340z0g0W5;5J4@200?040k625@4Z0T0@0u0B0A0u0v246i694G4^660q625?6m2?0@0x6l584Z6o6q6a4^6c040W0n0}0Z0W0G6h6i0-0V1W0K61425G6s1#660h0e620_6S2E5+5T015O2:3B3D5c6(4*503|3C5Y265!6)5V5%3b6-0j3h0f716r6x4^5-040V5:6#3E6B6t046v7a734Y4^0n0I0@2#0D6A6U0/7k0@2Q7p747d6F6H0D6J6L6Q2q6P6R2.7q01666Y7g6!7H4q6/0G5P3b3$4L7Q5$513$0f5Z5#4P6=7U3H727+7h643o0@7y277A6K0v6M7E1X7G5E7I0n0@0l6w7i7d0u0M0M240B827.0/66687a7c7/7e8a3M6W6Z8j7Q7S0N3~7V5M6`7X6=3~7!6^7$4+8w1T6 3E7,718g0/760O487v838h0p8N8b017s77197g8I3N6d6f6h6j0K8j59660d8)6b6u8-6n0@0U7L2,0f7N7}7P8t6*1`3B4k8s8A6;4i0N4k8y27935W4j8D708G7,8Y6D5|5~608:650@8e7O8O3/8!6g6i0T6k8f7I6z8X7I6D8Q9y7w6V0@6p9B9G9s6E6G7=7B7^7D6O7{9m9H040h6q8`6T8|5U8p4B928u7%954B986_6:9b0N9)3H9!6$3L8o6+3b4S9*9;6|0N4S9/9aa29 3)7I765/8R4r5`047C6N7F9V8c9oak8Zag8#9v9x9q8S9A8^9h8/9F9r7J0@6X8maz2t9|8 4-5S8}6{514.a59+8B954.5)8F8H9C7:9O6I7@7_9T6Qad597 040ta)6y0@0d0UaEat0faH0T3B53a0aM6=53aPa151a|7*72ax049j0n5 7|9#aA8dan6D6e9u8%anav3j7-4raya@8*9Ia.6CaY7z9Qa$ajaF8kaC9Z8naL8p5laKa651bIb1a~95bIaU7+8Y762y0D5 8WawaX9Nbxa#9SbA4o690j5I5o5C5q5z1a0D5tb=2L2G0u6P2F5r6!0Y0!0$0W04.