Exercices - suite

Exercice 1 : matrice d'adjacence et liste d'adjacence⚓︎

Question 1. Matrice d'adjacence

Donner la liste de listes représentant la matrice d'adjacence du graphe suivant :

Solution

[
[0, 1, 1, 1, 0, 0],
[1, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1],
[0, 0, 1, 0, 1, 0],
]

Question 2. liste d'adjacence avec dictionnaire

Compléter la fonction conversion_dico qui prend en paramètres une liste de listes m qui représente la matrice d'adjacence d'un graphe, et qui renvoie la liste d'adjacence correspondante, implémentée à l'aide d'un dictionnaire.

Par exemple, pour le graphe suivant :

>>> m = [[0, 1, 0, 1], [1, 0, 1, 1], [0, 1, 0, 0], [0, 0, 0, 0]]
>>> conversion_dico(m)
{0: [1, 3], 1: [0, 2, 3], 2: [1], 3: []}
>>>

Évaluations restantes : 5/5

.128013f:6Sd=4yr./opg2mcb1w37v{ej[ l8P5)ti]knua(}_sh050f0z0I0O0J0D0S0C0r0D0O0S0S0g010I0J0n010406050S0N0q0q0O0j0i040e0m0D0N0.0m0M050l0^0`0|0~0?0n04051e171h0l1e0?0f0J0x0$0(0*0,0T0J0o0T0D1v0T0I0;050X0s0D0z1q0)0+011u1w1y1w0I1E1G1C0I0j1f0I0T0$110S0n0O0M0,0p011I1s010b0Z0z0M0O0q0z1C1#1%1,1K1/1G1=1@0;0a0C0F0j0m0n0m0S0J140M0C0V1Z0j0j0z0r2c171`0M1f0l1X2p1U1W1V1D0f1|0,1y0M1;291C1n1p0%1J2z0J2B0M0m2F1C0n2i1f2n2p2T0@1$2d2H1-2M0j0{0D0;0t2m2X0=2W1{2Z1K2#2%0;0p2+1%2-2n2y012=0O2(040v2_2o0?2|2:0,2 310h342{2X2}3a0;0G3d363f382~0m2$300;0d3k2.2Y1r2;3p2?040w3u373x393z3r040E3d1i2R172F2s0f1W2x3n0r2N1^1f3P1g3N2V182,053V0V2S3m3F010L0;0V0b3L3E2I010u0;0C3@3-3_0M0b0;3V0M0x0z0j2a150R1n3V3~2/3.0:040P4e3w400;0q4k2}4h0H0c3k0C4v3}3^2!0;0o3d4x3 1-0m0;0g4C3v4q0;0y0Q4u4w4K3n3:040b3p4J4y2;0;0J4X4E1K0m3{042K4$4f400s0;0j1%0o0z4p3n4h4j3%2`4R3.0M4:041 4_4g0;4|2V4Y394n553_4r4s4P4w4Q5a2~4A5d1-4h0B5n4Z4+5r0,4h0K4-4l4F4H5y4L040B5x4}355i5i4 3_4T4V0j5C3n0M0;0A5Q3.4)4!165H044D4.2!524=0M4@5u014{5-510;545!5L5o575:5c5@5k5p5{5t5}4%5v0;0K0H5g5!065J6b5$5z1K4T0J3?5!6d3g5|59635.0;5q625%5s4#6s6e64040K6r6n6t5b045U6w5D5G2T6k3n4G040g4I6j5^1K0q0J2)5-4h4t696c6#6L505m6H4`6q606v6C6x6p6z5-6N0k600O0n0n1;0f6X5`6*6(6F6 040H5h6%5M4;0W0N0j5Z6K6S6E4B69173*0z2p2Q7m3O1o3Q2s2v2q0O1F7p0l3P0?7z0W0Y0!04.

Question 3. liste d'adjacence avec une liste

Compléter la fonction conversion_liste qui prend en paramètres une liste de listes m qui représente la matrice d'adjacence d'un graphe, et qui renvoie la liste d'adjacence correspondante, implémentée à l'aide d'une liste.

Par exemple, pour le graphe suivant :

>>> m = [[0, 1, 0, 1], [1, 0, 1, 1], [0, 1, 0, 0], [0, 0, 0, 0]]
>>> conversion_liste(m)
[[1, 3], [0, 2, 3], [1], []]
>>>

Évaluations restantes : 5/5

.128013f:6Sd=4yr./opg2mcb1w37vej[ l8P5)ti]knua(_sh050f0y0H0N0I0C0Q0B0r0C0N0Q0Q0g010H0I0n010406050Q0M0q0q0N0j0i040e0m0C0M0,0m0L050l0?0^0`0|0;0n04051c151f0l1c0;0f0I0x0!0$0(0*0R0I0o0R0C1t0R0H0/050V0s0C0y1o0%0)011s1u1w1u0H1C1E1A0H0j1d0H0R0!0 0Q0n0N0L0*0p011G1q010b0X0y0L0N0q0y1A1Z1#1*1I1-1E1:1=0/0a0B0E0j0m0n0m0Q0I120L0B0T1X0j0j0y0r2a151^0L1d0l1V2n1S1U1T1B0f1`0*1w0L1/271A1l1n0#1H2x0I2z0L0m2D1A0n2g1d2l2n2R0=1!2b2F1+2K0j0_0C0/0t2k2V0:2U1_2X1I2Z2#0/0p2)1#2+2l2w012:0N2$040v2@2m0;2`2.0*2}2 0h322_2V2{380/0F3b343d362|0m2!2~0/0d3i2,2W1p2/3n2;040w3s353v373x3p040D3b1g2P152D2q0f1U2v3l0r2L1?1d3N1e3L2T162*053T0T2Q3k3D010K0/0T0b3J3C2G010u0/0B3=3+3@0L0b0/3T0L0x0y0j28130P1w0Q0H0y3|2-3,0.040O4e3u3~0/0q4k2{4h0G0c3i0B4v3{3?2Y0/4a4c3b4x3}1+0m0/0g4D3t4q0/0A0J4u4w4L3l3.040b3n4K4y2/0/0I4Y4F1I0m3_042I4%4f3~0s0/0j1#0o4d3#2^4S4g0/4j4`2m4|4:4A1/4p3l4h4 2T4Z374n564}040G4s4Q4w4R5b2|4A0I4b4_5a4(0*4H040k5e4m040N0n0n1/0f5y1+584O0G5j5k4E4/1+4U4W0j4.4l4z040z5T2{4*4#1450045N5U2/4;044?0L4^5G1I585;375,1}5@015?5%525V4o5~5m4h0A5{0L4#5{4h0J5h4t5%065M6g5)2{4U0I3;5%6i3l6704615s5O5=4N6668625t5|0/0J656z6u5c5W696C5Y3l5v0g4J6n5 1I0q0I2%6J046d2R6f6h6#6R6H4B5r3$636w6F5*6H4$6.4M044P6=6M0/5x6_3,6q5B5D0L5F6}3@5}6t6/5n6I745H0/5K6e5k6%3-4=0U0M0j5$2R6o6~5o5q3s0l3(0y2n2O7w3M1m3O2q2t2o0N1D7z0l3N0;7J0U0W0Y04.

Exercice 2 : parcours en largeur⚓︎

parcours de graphe

Question

Donner la liste des sommets par parcours en largeur du graphe ci-dessus si le sommet de départ est B en conservant l'ordre alphabétique.

Solution

['B', 'A', 'D', 'E', 'C', 'F', 'G', 'H']

Question

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

Cette fonction renverra la liste des sommets parcourus à partir du sommet depart.

Compléter le script ci-dessous, en ajoutant le test correspondant au graphe ci-dessus :

Solution

Voir la leçon sur les parcours de graphes ... 😂

🐍 Script Python

# Test
mon_graphe = {"A":["B", "C"], "B":["A", "D", "E"], "C":["A", "D"],
"D":["B", "C", "E"], "E":["B", "D", "F", "G"], "F":["E", "G"], "G":["E", "F", "H"],
"H":["G"]}
assert parcours_BFS(mon_graphe, "B") == ['B', 'A', 'D', 'E', 'C', 'F', 'G', 'H']

Exercice 3 : parcours en profondeur⚓︎

parcours de graphe

Question

Donner une liste des sommets par parcours en profondeur du graphe ci-dessus si le sommet de départ est A.

Solution

['A', 'B', 'D', 'C', 'E', 'F', 'G', 'H']
['A', 'C', 'D', 'E', 'G', 'H', 'F', 'B']
et beaucoup d'autres possibilités ...

Question

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

Cette fonction renverra la liste des sommets parcourus à partir du sommet depart.

Compléter le script ci-dessous, en ajoutant le test correspondant au graphe ci-dessus :

Solution

Voir la leçon sur les parcours de graphes ... 😂