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

.128013ldy14{]kj/weibmc_:35}aPr 7=o[f.gt286sSh)(punv050c0m0H0w0n0b0L0z0q0b0w0L0L0B010H0n0Q010406050L0R0p0p0w0y0d040M0C0b0R0.0C0S050k0^0`0|0~0?0Q04051e171h0k1e0?0c0n0T0$0(0*0,0N0n0G0N0b1v0N0H0;050X0o0b0m1q0)0+011u1w1y1w0H1E1G1C0H0y1f0H0N0$110L0Q0w0S0,0I011I1s010E0Z0m0S0w0p0m1C1#1%1,1K1/1G1=1@0;0a0z0x0y0C0Q0C0L0n140S0z0V1Z0y0y0m0q2c171`0S1f0k1X2p1U1W1V1D0c1|0,1y0S1;291C1n1p0%1J2z0n2B0S0C2F1C0Q2i1f2n2p2T0@1$2d2H1-2M0y0{0b0;0e2m2X0=2W1{2Z1K2#2%0;0I2+1%2-2n2y012=0w2(040t2_2o0?2|2:0,2 310f342{2X2}3a0;0u3d363f382~0C2$300;0K3k2.2Y1r2;3p2?040A3u373x393z3r040J3d1i2R172F2s0c1W2x3n0q2N1^1f3P1g3N2V182,053V0V2S3m3F010i0;0V0E3d0z3v3g0E0;3V0S0T0m0y2a150r1n3V3L3E2I010:040P473-490S0;0p4e2/3.4b0O0s3k0z4r3^482!0;0G3@3_3n0C0;0B4y4u1K4b0g0v4q4s4z3.3:040E3p4E4f4v040n4S4l490C0l0;2K4X3w4g0o0;0y1%0G0m4k4)1-4b4d3%2`4M4*0;1 4;2}4@4 3n4h044j4_2o4{4?0;0O4o4K4s4L4F394w524m0;0D5k4g4$5o5a040h4(2}4B044D57044t4T4G5m5u5A065f5f591K4O4Q0y5v530;0j5Q3.4!4$165A5C4Y2!4+044-0S4/5r5E4c5,395%4~5A5L0,515?5h2~4i5/4a5m5~544W5`5D5^0;0h5c4p5H5J6c5!4=5M4$3?5Z5@5|555~4b5n645#2;5q6q6f665t6p2V5{545T6u50675U4Z4C5z2T6e2}0p0n2)6n0;6a2T5I6d6V6k544x6D3n6o616t6z655 5t5~5x0F6%040w0Q0Q1;0c6Q5.6!3.6B6`0O5e6L3n4O2i0H0R0y5Y6K6X5j5H173*0m2p2Q7g3O1o3Q2s2v2q0w1F7j0k3P0?7t0W0Y0!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

.128013ldy14]kj/weibmc_:35aPr 7=o[f.gt286sSh)(punv050c0l0F0u0m0b0J0x0p0b0u0J0J0z010F0m0O010406050J0P0o0o0u0w0d040K0A0b0P0,0A0Q050j0?0^0`0|0;0O04051c151f0j1c0;0c0m0R0!0$0(0*0L0m0E0L0b1t0L0F0/050V0n0b0l1o0%0)011s1u1w1u0F1C1E1A0F0w1d0F0L0!0 0J0O0u0Q0*0G011G1q010C0X0l0Q0u0o0l1A1Z1#1*1I1-1E1:1=0/0a0x0v0w0A0O0A0J0m120Q0x0T1X0w0w0l0p2a151^0Q1d0j1V2n1S1U1T1B0c1`0*1w0Q1/271A1l1n0#1H2x0m2z0Q0A2D1A0O2g1d2l2n2R0=1!2b2F1+2K0w0_0b0/0e2k2V0:2U1_2X1I2Z2#0/0G2)1#2+2l2w012:0u2$040s2@2m0;2`2.0*2}2 0f322_2V2{380/0t3b343d362|0A2!2~0/0I3i2,2W1p2/3n2;040y3s353v373x3p040H3b1g2P152D2q0c1U2v3l0p2L1?1d3N1e3L2T162*053T0T2Q3k3D010h0/0T0C3b0x3t3e0C0/3T0Q0R0l0w28130q1w0J0F0l3J3C2G010.040N473+490Q0/0o4e2-3,4b0M0r3i0x4r3?482Y0/43453=3@3l0A0/0z4z4u1I4b0B0g4q4s4A3,3.040C3n4F4f4v040m4T4l490A0k0/2I4Y3u4g0n0/0w1#0E463#2^4N494b4d4=2m4@2Y4,041}4k4*1+4_523e4i563l4n4o4L4s4M4G374w0m444;2T5g014C040D593,4h040u0O0O1/0c5s4^0/0N4J0M5d5e4t4U1I4P4R0w4)57040i5P4B4$4W144{045J4Z4~4-4/5l3$5n555Y4}2/4 515-5+5D5B4V4j5=5K0*4I5^2/4%5 5}0/0g0M5c5Y065I6a5!535L4%3;5Y6c5Q5`5m5|4a0/0B622|615{5#4H646p6t6d5h5R6q4b4K6h5.0*5p0z4E6F5n0o0m2%6C0/4p686b6U6i3l5u4x5)4?5?046x6l6u6A4X6y2{6D6q5p5r6-6X0/5w5y0Q5A6?4m5@6}4g0/5S70540/5G6T5f6m4P2g0F0P0w5X2R6W5t5i5k3s0j3(0l2n2O7p3M1m3O2q2t2o0u1D7s0j3N0;7C0U0W0Y04.

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 ... 😂