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é

🐍 Console Python
>>> 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

.128013f06S:d=4yr./oxpg2mcb1w937vej[ l,8P5)ti]knua(_sh050g0B0L0R0M0F0U0E0t0F0R0U0U0h010L0M0p010406050U0Q0s0s0R0k0j040e0n0F0Q0:0n0P050m0`0|0~100^0p04051g191j0m1g0^0g0M0A0(0*0,0.0V0M0q0V0F1x0V0L0?050Z0u0F0B1s0+0-011w1y1A1y0L1G1I1E0L0k1h0L0V0(130U0p0R0P0.0r011K1u010b0#0B0P0R0s0B1E1%1)1.1M1;1I1@1_0?0a0E0I0k0n0p0n0U0M160P0E0X1#0k0k0B0t2e191|0P1h0m1Z2r1W1Y1X1F0g1~0.1A0P1?2b1E1p1r0)1L2B0M2D0P0n2H1E0p2k1h2p2r2V0_1(2f2J1/2O0k0}0F0?0E0v2o2Z0@2Y1}2#1M2%2)2+0r2.1)2:2p2A012^0R2*040E0y2|2q0^2 2?0.32340E0i382~2Z303e2+0J3i3a3k3c310n2(332+0d3p2;2!1t2@3u2_350z3z3b3C3d3E3w350H3I3r3K3t3v3f0x3Q2=3S3m040v0c3i1k2T192H2u0g1Y2z3s0t2P1`1h3,1i3*2X1a2/053=0X2U3R2K010O0?0X0b3(3J440w2+4a432$0b0?1(0k3=0Q0k0U4f3Y440=040S4q3B440P0?0R0g0C0R0t1?4F4w304t0G3i0E3A3l0?0o4I3s4K4M4O3s4z040U0n0|0Y0U0T4E4F0,0M1H0B4p3}2}4W3S4t0K0f3p0E4|4N4b1/46040M494;2q4~4g2@4Q4V4 1M0n4d042O0L5b580.5e0?2M5j4r2$0?4!4$0L4(4*4/2c4.4:2X5c0.4t4`5535064}5K575q594Z4#1_5v4)0t4+5z1I5B3~5D010n0?0l4S3Z4A0p0p1?0g5)4s0?4v5H4?4y5a5@5!4^4{5L4|5^500?0b3u5p4x5r040j66305m52185H5M675O4B4D4F0P4H5{5k014t0D5:684R6p5N5E0?0N5G2V0E5J5 5L615O4k4m4o6u1M4t5?5C6q4Y6k4E4G0B6N6z044L6g6I3d0?6a6x6i6Z6#6D6%315s5Q4%5T5V4-5X6Y6r0?0K4M063q6y45470B546R735f4N6+3l4i045x4,5A6|6P6|6T4C6V6n6X7c4T0?6.2/6h4P046w786,6}044_5~605!4Y5t5R5w5U5y6`4/6b3s5$040h7Q4@0?0D0N7F7w4X4j0~6L5Y4=5|5=7l4A7n6m6o7A4J7t7V5_7y7j7^6$7H6=5u7L6_7i7r7W7D705K6:512k0L4n6f6/7 5P816^7N842V0^0m400B2r2S8r3+1q3-2u2x2s0R4.2r3,8o0X0Z0#0U04.