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: []}
>>>
.128013 vt4=8fw2pmuP(j751:cSsr]{k[63 dg)}/niyelh_boa.- 050E0M0c0S0K0N0v0D0t0N0S0v0v0e010c0K0j010406050v0l0k0k0S0w0L040u0R0N0l0/0R0J050I0_0{0}0 0@0j04051f181i0I1f0@0E0K0b0%0)0+0-0)0J0F0l0S0F0M0U0j0L0c0O160D0O0K0F0O0N1K0O0c0=050Y0Q0N0M1r0*0,011J1L1N1L0c1T1V1R0c0w1g1F0%120v0j0S0J0-0i011X1t010g0!0M0J0S0k0M1R1?1^1}1Z201V23250=0a0D0m0w0R0j0R0v0K150J0D0W1;0w0w0M0t2q18280J1g0I1F2D1-1/1.1S0E2a1u0K0J222n1R1o1q0(1Y2N2P0J0R2T1R0j2w1g2B2D2*0^1@2r2V1~2Z0w0|0N1R0S1I2w0g0-030P0P0t2!0M1N2Y0R0U0i0U0r0=0r180S2+2.0?2-292:1Z2=2@2_2{0M2}012 3133352Q38380=0i3e3g1^3i2B2M013n0S2^1g2`0O2|2~30320W3x2Z3z0C0=0C3D2A3h0@3H3l0-3K3M053O3Q3t3S3w2O3y390d0=0d3#193%3j2/1s3m0R2?3L3p3P3r3R3v3U3@3W390q0=0q3}2*3(2.3I3,473:3u3T344d37390B0=0B4j3 3)423+443o3N3q3s4r3?363z0p0=0p4A3F4l3k4D3J4F464H484J3=4c4M390f0=0f4R2C1j2(182T2G0E1/2L3*014s2S1p1g2%0M2)3h3$3F054s52290K0E0-302B3z3b4H5a5c4b4t4(3a1|2e0M5j4s3V4v5n2D3f403I0z0=0W0g544.4C2W010h0=0D5E58415H0J0g0=320J0b0M0w2o160P1o325M5y4`0;040n5%5G2;0=0k5-4m5)0=0G0s5M0@3~553H5i015d2.3z1{5h5b615k5t645o245q685s4u6b5w040D6l5L5.3m0=0F5M6n5?4V0R0=0e6s5(4V5*0y0H5{5=5967621^3X3p604$5l3^0U3Y0D5p5r4L6Q3Y6j6m6t4U5H5A040g446z6o3+0=0K6,6u5H0R5J042O6;6$2;0Q0=0w1^1A6G5O1~5*5,5}5F6=6}0=2d733I767e4`0J5:7h6B5^5_6F785N0D6N0P5e3_6M6I696h7w6T6d6V4%6Q3`6Z6!6m6A5P6q7l5H5*0A7O5/6_7S1Z5*0x6{741Z6w046y7q6#7!0-7Q7Y7q5|2,5 7y7v0U4g667E6P4e7^6c257{6a4f1R0I3f7J7K6-016(6*0w7Z4n0=0o8e4`6@6/177)7L7b04701w0M7V7,0=777;7a3m6~047d7q8o7W8w8u3J7k8E897Q8I7j7U8L8z8v040x0G7o7/7e7t7@4x7`6f6W7}4x7C808(7F8*8486877J8F0-6(0K5D8n898P5;8R6|8G047R917+8J8Q8y928T0x959a978P8h967f0=7.2*7*3I7$0e7(9n8^010k0K3c8I5*5`8Y9j8!63394O8%6O820U4O8,6e9J7A9L8;6k8?9U9u8P6r9j5@948O6/9z9l8I7$0T9$040S0j0j220E9(5+9-9i9f9k040G7p9{9E6K4)7x819Q4*9Na55m4*7I6l9u6(2w0c0l0w8m9t8~7N9C2,0I574/514;4~180c4@aw2J2E0S1Uat0I4=5|0W0Y0!0v04.
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 vt4=8fw2pmuP(j751:cSsr]k[63 dg)/niyelh_boa.- 050D0K0c0Q0I0L0v0C0t0L0Q0v0v0e010c0I0j010406050v0l0k0k0Q0w0J040u0P0L0l0-0P0H050G0@0_0{0}0=0j04051d161g0G1d0=0D0I0b0#0%0)0+0%0H0E0l0Q0E0K0S0j0J0c0M140C0M0I0E0M0L1I0M0c0:050W0O0L0K1p0(0*011H1J1L1J0c1R1T1P0c0w1e1D0#100v0j0Q0H0+0i011V1r010g0Y0K0H0Q0k0K1P1;1?1{1X1~1T21230:0a0C0m0w0P0j0P0v0I130H0C0U1/0w0w0K0t2o16260H1e0G1D2B1+1-1,1Q0D281s0I0H202l1P1m1o0$1W2L2N0H0P2R1P0j2u1e2z2B2(0?1=2p2T1|2X0w0`0L1P0Q1G2u0g0+030N0N0t2Y0K1L2W0P0S0d0S0r0:0r160Q2)2,0;2+272.1X2:2=2@2_0K2{012}2 31332O360S1_040i3c3e1?3g2z2K013l0Q2?1e2^0M2`2|2~300U3v2X3x0B0:0B3C2y3f0=3G3j0+3J3L053N3P3r3R3u2M3w370d0:0d3!173$3h2-1q3k0P2;3K3n3O3p3Q3t3T3?3V370q0:0q3|2(3%2,3H3+463/3s3S324c35370A0:0A4i3~3(413*433m3M3o3q4q3=343x0p0:0p4z3E4k3i4C3I4E454G474I3;4b4L370f0:0f4Q2A1h2$162R2E0D1-2J3)014r2Q1n1e2#0K2%3f3#3E054r51270I0D0+2~2z3x394G595b4a4s4%381`2c0K5i4r3U4u5m2B3d3 3H0y0:0U0g534-4B2U010h0:0C5D57405G0H0g0:300H0b0K0w2m140N1L0v0c0K5L5x4_0/040n5(5F2/0:0k5.4l5*0:0F0s5L0=3}543G5h015c2,3x3z3-0C614#5k3@3y5n225p625j5s651P0G3d0C6o5K5/3k0:5!5$5L6q5@4U0P0:0e6w5)4U5+0z0x5|5?585a6h5d373X5g6M6a6j6P6e235q4K6c6Q3C6p6x4T5G5z040g436D6r3*0:0I6/6y5G0P5I042M6@6)2/0O0:0w1?1y6K5N1|5+5-5~5E6^706t20763H797h4_0H5;7k6F5_5`6J7b5M686S0N6O363n696i4t3x3_0C5o6Y4$6c3_5v046%6%6E5O6t0I5#5%7t7Q1|6A040R7o7R040Q0j0j200D7$780:0n6H0F7s2*607w7y4f6R7I6b4d0S4f7G6f7~6U816l6n7O6o7X1X6+6-0w6~776s040o8h3H6`6=157t6(8i3*7104731u7V7^7d1X7j7W6:3I8v2b7.8C7:8J6;045=8E8B0+6G8M3I6=8U5+0x0F7r7t5}8A6L5i7y4w7}6h5r7D4v6W6g6T8:0S8,6$8a7O8c0+6+0I5C8r8~8V8O8X0:0z8U7m6|97040x998Q6 8j8l9h8t018Y8m4_7Z0e6C938F0k0I3a9d5{8$7h7B7y4N8-8@5l4N836X8.6Z809F8{8|8|949b6u8z528F8T9l4m8W9!5^9e8U7Z7#9%4U9b7)7+0H7-9-5G8D8(9m9b9k9`7i5_7@9X4l9D644(7A7w8/5l4)9K8?7Caa887N6p946+2u0c0l0w8q2(8s9#049Va1540G564.504:4}160c4?aD2H2C0Q1SaA0G4;5}0U0W0Y0v04.
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 ... 😂
Exercice 4 : parcours en largeur ... avec une file sans file
Nous reprenons l'algorithme du parcours en largeur optimisé avec le dictionaire vus. (Se reporter au cours sur le parcours en largeur)
La liste des sommets parcourus visites va servir en même temps de file. En effet pour simuler le défilement, il suffira de se déplacer d'un rang vers la droite dans cette liste. La variable i sera l'indice de l'élément qui serait défilé.
Au début i = 0, et défiler revient à faire i = i + 1.
Question 1
Comment exprimer en Python l'instruction "Tant que la file n'est pas vide" ? Il faut trouver la condition pour qu'on puisse défiler.
Solution
while i < len(visites)
Question 2
Compléter ci-dessous :
.128013 vt4=8fw2pmuP(751,:cSsêr]{ék[63;0 dg)}/+n9qiyelh_boaT.- 050I0T0c0Z0R0U0v0H0t0U0Z0v0v0e010c0R0j010406050v0l0k0k0Z0x0S040u0Y0U0l0`0Y0O050M111315170 0j04051n1g1q0M1n0 0I0R0b0/0;0?0^0;0O0J0l0Z0J0T0$0j0S0c0V1e0H0V0R0J0V0U1S0V0c0}050*0X0U0T1z0=0@011R1T1V1T0c1#1%1Z0c0x1o1N0/1a0v0j0Z0O0^0i011)1B010g0,0T0O0Z0k0T1Z1~20251+281%2b2d0}0a0H0m0x0Y0j0Y0v0R1d0O0H0(1|0x0x0T0t2y1g2g0O1o0M1N2L1^1`1_1!0I2i1C0R0O2a2v1Z1w1y0:1*2V2X0O0Y2#1Z0j2E1o2J2L2=101 2z2%262+0x140U1Z0Z1Q2E0g0^030W0W0t2,0T1V2*0Y0$0D0$0q0}0H0q1g0Z2?2_0~2^2h2{1+2}2 31330T350137393b3d2Y3g0$23040H0i3n3p203r2J2U013w0Z301o320V3436383a0(3G2+3I0E3k0E3O2I3q0 3S3u0^3V3X053Z3#3C3%3F2W3H3h0d3k0d3:1h3=3s2`1A3v0Y2~3W3y3!3A3$3E3)423+3h0p3k0p482=3?2_3T3`4i3~3D3(3c4o3f3h0D3k0D4u4a3@4d3_4f3x3Y3z3B4C413e3I0o3k0o4L3Q4w3t4O3U4Q4h4S4j4U404n4X3h0f3k0f4$2K4(4c2(4+4g3{3}4k3 4m4E4?0$0P3k0P4{3R4x3^504R3|4T4l4D3*4G3i0G0}0q0G5d4}4y4,525k555m4F3I0q3j045E5d1r2:1g2#2O0I1`2T5g4D2!1x1o2/0T2;3q3;3Q054D5Y2h0R0I0^382J5D3y5*5,565n5/0H2m0T5=5B585F3:4N4 0B0}0(0g5!2K4b3T0h3k675(4~2|0g0}0X0g0v0W0b3N495#61260|040n6d695g0O0}0J0x0Z0j0V0T6w6r1+6t0r6d0H6x4*6z040(1 0x0c6H5f4*6t0K0s6d0 6p683S5;015-2_3I3K5j6+4;57433J245`5|4W6^6:0M3o0H726N6I3_0}0b0R2w0c0T0v6M6O4 0Y0}0e7e75016t0C6W4)4 6Q6S156V6(6e3T6t0y6M746X4 0t5F030H0l2X0H2k6G7w6%2@6*5+6,0W5.3h3-4S6=5?5C7W6`2c5{7T5}6^7X3O737C7q2|770l7d7w7:6f1+7h047j7_7f6s0}0z7p7{766R0T6T7v7Q7D82046#807l0B0t0}0!0x0l7N8c7;6J0}0L6$850H7Z7V0$457Y7S6?5@447%2d6|4=6^8B7.73813v0}0R7k8d7|7i8T8r0^0k0R0}5t7_7`3T7F0}7H2W1w0t1(2B0U02030E0P0F0A0U0A2d0O0c2A1(0c0w7b0H2u0l0x0H1%2A0A7M8 8b4a7w698y6.4q5:8D7!584r5_7(8J6@4p0$4r2L718O8i0}0h1R1%8X863U8R9I3T7}020U0c0F9M6y0X0}2l8w5g6t6v9j7l6Q787a7c9Y6Y0}6!7B8P0^8+047H1P0j0T1c9d7M9a0*900H0Q8o8x0H9P9R9b2a0n9)2x7c0K8v9$4x9l203I4I8C9v8F3g8H7)8E7#aq9A3L7/9C8U0^63040g4f9T6P770Y792WaG7g6b04aL8haA9K046B6D6F9,4 7naY7=04ac7b7^8q9Ja!ah8YaT8Sa.a,0}0y0y8g2=729;019?9^2z02a30Y9R0I9e29b20lb40F0Ha(7c0C0R0y0H0)0H1P2E0J152B0v7cbdaJ2w0Oa*9ia+8x9p8z4Zan7*6}9x4Z9t8IbF8KbH1Z70axayaya}aC0R66aRa/9(buaQa{a}0YaO2+9h3Q8)5gb(8R1fbX9J9(7@a#8s8fagbzaj0O3I4^bEat584^bJas9q6^c18NbRccb-aHa%aKa)b_0^7}0#cjaT6D9`0O0Icn9!cnbZaKb;bz9Z9.9:7la bl2z2a7Mb|5Z7R5=8z5ac2c89x5ac6aoaucOcbcdbS9%7?bx6qaSa-czcf0bb!cycKc(a@aM267}7 b$8i8k048m8ocJc%5)bB9m5p9ocU5~5qcTbL9w5o5sbO9BbRa}6Qa;c_aSc@c=8QaPdnck0}0Ndq018!5r7B7Pc/d1cMd35Ed5daapdEd9c36^dEaw7/bT0}2E0c99c.b,dh77ch9+7O6w0M5%5J5X5L5U1g0c5Od,2R2M0Z1$d)0M5M6%0(0*0,0v04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)