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"
(Ctrl+Clic pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
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

.1280130ldy1,4]kj/weibmc_:35aPr 7=9o[f.gt286sSh)(punxv050d0n0I0w0o0c0M0z0r0c0w0M0M0B010I0o0R010406050M0S0q0q0w0y0e040N0D0c0S0:0D0T050l0`0|0~100^0R04051g191j0l1g0^0d0o0V0(0*0,0.0O0o0H0O0c1x0O0I0?050Z0p0c0n1s0+0-011w1y1A1y0I1G1I1E0I0y1h0I0O0(130M0R0w0T0.0J011K1u010F0#0n0T0w0q0n1E1%1)1.1M1;1I1@1_0?0a0z0x0y0D0R0D0M0o160T0z0X1#0y0y0n0r2e191|0T1h0l1Z2r1W1Y1X1F0d1~0.1A0T1?2b1E1p1r0)1L2B0o2D0T0D2H1E0R2k1h2p2r2V0_1(2f2J1/2O0y0}0c0?0z0f2o2Z0@2Y1}2#1M2%2)2+0J2.1)2:2p2A012^0w2*040z0u2|2q0^2 2?0.32340z0h382~2Z303e2+0v3i3a3k3c310D2(332+0L3p2;2!1t2@3u2_350A3z3b3C3d3E3w350K3I3r3K3t3v3f0C3Q2=3S3m040f0b3i1k2T192H2u0d1Y2z3s0r2P1`1h3,1i3*2X1a2/053=0X2U3R2K010j0?0X0F3i0z3A3l0F0?1(0y3=0S0y0M3(3J440=040Q4m432$0?0w0d0k0w0r1?4A4s3Y4o0?0g4a4c3s0T0?0U4D3B4F044H3}2}4b4n4u040M0D0|0Y0M0s4z4A0,0o1H0n4l4T2q4J3S4p0P0t3p0z4{4V4t1M46040o494:354=444L044N544}4E1/0D0m0?2O0I4I4W1M5f0?2M5k4~3d0?4Z4#0I4%4)4.2c4-4/2X5l0.4p4_5b064|5K5c4P4X5u1_5w4(0r4*5A1I5C3~5E010D0?0G4O3l4v0R0R1?0d5(3s4p4r54564X5a5D5r014@4`5L4{5@4 0?0F3u5q5d2@0?0e665N5m5g51185b615s044w4y4A0T4C5?5Z4p0E5/3Z4M6u4Q0i5H2V0z5J5 5L6i314f0~4i4k6x1/5;6M686k4x4z4B0n6P5F4G6b5)046a6q5{4p4S6B6G585P4$5S5U4,5W6W5|0?0P4a063q670.50486Z4K4e6k5T5z6=4.6@6O6%6~6H6R6m6U7a6Y6h5Z585_5Y6(6_6A2/6D607l5t4!5Q5x764+5B723S5#040B7D4Q0E0i5~7u5{584g6K5X2}6G7b5`7d586l6T6o6V7c6c6X4R7I5^7i7*7k7O7w5v7z6;7C7%305}5I5K6G502k0I4j6g6+7v4Y7x6/5y7B6?540^0l400n2r2S8g3+1q3-2u2x2s0w4-2r3,8d0X0Z0#0M04.