3 exos
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: []}
>>>
.128013 l( _4:=vm26j-uS8w.s3/]fr7g}ebh[pPic5a{onkyd1)t 050R0C0U0L0I0b0t0d0J0b0L0t0t0h010U0I0G010406050t0o0j0j0L0y0Q040p0N0b0o0/0N0O050v0_0{0}0 0@0G04051f181i0v1f0@0R0I0i0%0)0+0-0)0O0A0o0L0A0C0n0G0Q0U0E160d0E0I0A0E0b1K0E0U0=050Y0D0b0C1r0*0,011J1L1N1L0U1T1V1R0U0y1g1F0%120t0G0L0O0-0k011X1t010x0!0C0O0L0j0C1R1?1^1}1Z201V23250=0a0d0H0y0N0G0N0t0I150O0d0W1;0y0y0C0J2q18280O1g0v1F2D1-1/1.1S0R2a1u0I0O222n1R1o1q0(1Y2N2P0O0N2T1R0G2w1g2B2D2*0^1@2r2V1~2Z0y0|0b1R0L1I2w0x0-030e0e0J2!0C1N2Y0N0n0k0n0S0=0S180L2+2.0?2-292:1Z2=2@2_2{0C2}012 3133352Q38380=0k3e3g1^3i2B2M013n0L2^1g2`0E2|2~30320W3x2Z3z0u0=0u3D2A3h0@3H3l0-3K3M053O3Q3t3S3w2O3y390f0=0f3#193%3j2/1s3m0N2?3L3p3P3r3R3v3U3@3W390K0=0K3}2*3(2.3I3,473:3u3T344d37390l0=0l4j3 3)423+443o3N3q3s4r3?363z0z0=0z4A3F4l3k4D3J4F464H484J3=4c4M390q0=0q4R2C1j2(182T2G0R1/2L3*014s2S1p1g2%0C2)3h3$3F054s52290I0R0-302B3z3b4H5a5c4b4t4(3a1|2e0C5j4s3V4v5n2D3f403I0P0=0W0x544.4C2W010r0=0d5E58415H0O0x0=320O0i0C0y2o160e1o325M5y4`0;040c5%5G2;0=0j5-4m5)0=0T0g5M0@3~553H5i015d2.3z1{5h5b615k5t645o245q685s4u6b5w040d6l5L5.3m0=0A5M6n5?4V0N0=0h6s5(4V5*0M0B5{5=5967621^3X3p604$5l3^0n3Y0d5p5r4L6Q3Y6j6m6t4U5H5A040x446z6o3+0=0I6,6u5H0N5J042O6;6$2;0D0=0y1^1A6G5O1~5*5,5}5F6=6}0=2d733I767e4`0O5:7h6B5^5_6F785N0d6N0e5e3_6M6I696h7w6T6d6V4%6Q3`6Z6!6m6A5P6q7l5H5*0F7O5/6_7S1Z5*0w6{741Z6w046y7q6#7!0-7Q7Y7q5|2,5 7y7v0n4g667E6P4e7^6c257{6a4f1R0v3f7J7K6-016(6*0y7Z4n0=0m8e4`6@6/177)7L7b04701w0C7V7,0=777;7a3m6~047d7q8o7W8w8u3J7k8E897Q8I7j7U8L8z8v040w0T7o7/7e7t7@4x7`6f6W7}4x7C808(7F8*8486877J8F0-6(0I5D8n898P5;8R6|8G047R917+8J8Q8y928T0w959a978P8h967f0=7.2*7*3I7$0h7(9n8^010j0I3c8I5*5`8Y9j8!63394O8%6O820n4O8,6e9J7A9L8;6k8?9U9u8P6r9j5@948O6/9z9l8I7$0s9$040L0G0G220R9(5+9-9i9f9k040T7p9{9E6K4)7x819Q4*9Na55m4*7I6l9u6(2w0U0o0y8m9t8~7N9C2,0v574/514;4~180U4@aw2J2E0L1Uat0v4=5|0W0Y0!0t04.
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], []]
>>>
.128013 l( _4:=vm26j-uS8w.s3/]fr7gebh[pPic5aonkyd1)t 050P0B0S0K0H0b0t0d0I0b0K0t0t0h010S0H0F010406050t0o0j0j0K0y0O040p0L0b0o0-0L0M050v0@0_0{0}0=0F04051d161g0v1d0=0P0H0i0#0%0)0+0%0M0A0o0K0A0B0n0F0O0S0D140d0D0H0A0D0b1I0D0S0:050W0C0b0B1p0(0*011H1J1L1J0S1R1T1P0S0y1e1D0#100t0F0K0M0+0k011V1r010x0Y0B0M0K0j0B1P1;1?1{1X1~1T21230:0a0d0G0y0L0F0L0t0H130M0d0U1/0y0y0B0I2o16260M1e0v1D2B1+1-1,1Q0P281s0H0M202l1P1m1o0$1W2L2N0M0L2R1P0F2u1e2z2B2(0?1=2p2T1|2X0y0`0b1P0K1G2u0x0+030e0e0I2Y0B1L2W0L0n0f0n0Q0:0Q160K2)2,0;2+272.1X2:2=2@2_0B2{012}2 31332O360n1_040k3c3e1?3g2z2K013l0K2?1e2^0D2`2|2~300U3v2X3x0u0:0u3C2y3f0=3G3j0+3J3L053N3P3r3R3u2M3w370f0:0f3!173$3h2-1q3k0L2;3K3n3O3p3Q3t3T3?3V370J0:0J3|2(3%2,3H3+463/3s3S324c35370l0:0l4i3~3(413*433m3M3o3q4q3=343x0z0:0z4z3E4k3i4C3I4E454G474I3;4b4L370q0:0q4Q2A1h2$162R2E0P1-2J3)014r2Q1n1e2#0B2%3f3#3E054r51270H0P0+2~2z3x394G595b4a4s4%381`2c0B5i4r3U4u5m2B3d3 3H0N0:0U0x534-4B2U010r0:0d5D57405G0M0x0:300M0i0B0y2m140e1L0t0S0B5L5x4_0/040c5(5F2/0:0j5.4l5*0:0R0g5L0=3}543G5h015c2,3x3z3-0d614#5k3@3y5n225p625j5s651P0v3d0d6o5K5/3k0:5!5$5L6q5@4U0L0:0h6w5)4U5+0E0w5|5?585a6h5d373X5g6M6a6j6P6e235q4K6c6Q3C6p6x4T5G5z040x436D6r3*0:0H6/6y5G0L5I042M6@6)2/0C0:0y1?1y6K5N1|5+5-5~5E6^706t20763H797h4_0M5;7k6F5_5`6J7b5M686S0e6O363n696i4t3x3_0d5o6Y4$6c3_5v046%6%6E5O6t0H5#5%7t7Q1|6A040s7o7R040K0F0F200P7$780:0c6H0R7s2*607w7y4f6R7I6b4d0n4f7G6f7~6U816l6n7O6o7X1X6+6-0y6~776s040m8h3H6`6=157t6(8i3*7104731u7V7^7d1X7j7W6:3I8v2b7.8C7:8J6;045=8E8B0+6G8M3I6=8U5+0w0R7r7t5}8A6L5i7y4w7}6h5r7D4v6W6g6T8:0n8,6$8a7O8c0+6+0H5C8r8~8V8O8X0:0E8U7m6|97040w998Q6 8j8l9h8t018Y8m4_7Z0h6C938F0j0H3a9d5{8$7h7B7y4N8-8@5l4N836X8.6Z809F8{8|8|949b6u8z528F8T9l4m8W9!5^9e8U7Z7#9%4U9b7)7+0M7-9-5G8D8(9m9b9k9`7i5_7@9X4l9D644(7A7w8/5l4)9K8?7Caa887N6p946+2u0S0o0y8q2(8s9#049Va1540v564.504:4}160S4?aD2H2C0K1SaA0v4;5}0U0W0Y0t04.
Exercice 2 : parcours en largeur
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 ... 😂
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
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 ... 😂
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)