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 w]itkc[v8o-)ylbp_.P3(ajg=/m}4rse7Sf{d 612:5nuh 050L0G0e0w0d0o0F0M0g0o0w0F0F0z010e0d0q010406050F0T0B0B0w0E0n040I0k0o0T0/0k0S050A0_0{0}0 0@0q04051f181i0A1f0@0L0d0i0%0)0+0-0)0S0y0T0w0y0G0l0q0n0e0U160M0U0d0y0U0o1K0U0e0=050Y0p0o0G1r0*0,011J1L1N1L0e1T1V1R0e0E1g1F0%120F0q0w0S0-0P011X1t010J0!0G0S0w0B0G1R1?1^1}1Z201V23250=0a0M0t0E0k0q0k0F0d150S0M0W1;0E0E0G0g2q18280S1g0A1F2D1-1/1.1S0L2a1u0d0S222n1R1o1q0(1Y2N2P0S0k2T1R0q2w1g2B2D2*0^1@2r2V1~2Z0E0|0o1R0w1I2w0J0-030r0r0g2!0G1N2Y0k0l0P0l0O0=0O180w2+2.0?2-292:1Z2=2@2_2{0G2}012 3133352Q38380=0P3e3g1^3i2B2M013n0w2^1g2`0U2|2~30320W3x2Z3z0u0=0u3D2A3h0@3H3l0-3K3M053O3Q3t3S3w2O3y390D0=0D3#193%3j2/1s3m0k2?3L3p3P3r3R3v3U3@3W390R0=0R3}2*3(2.3I3,473:3u3T344d37390N0=0N4j3 3)423+443o3N3q3s4r3?363z0H0=0H4A3F4l3k4D3J4F464H484J3=4c4M390j0=0j4R2C1j2(182T2G0L1/2L3*014s2S1p1g2%0G2)3h3$3F054s52290d0L0-302B3z3b4H5a5c4b4t4(3a1|2e0G5j4s3V4v5n2D3f403I0f0=0W0J544.4C2W010b0=0M5E58415H0S0J0=320S0i0G0E2o160r1o325M5y4`0;040v5%5G2;0=0B5-4m5)0=0m0Q5M0@3~553H5i015d2.3z1{5h5b615k5t645o245q685s4u6b5w040M6l5L5.3m0=0y5M6n5?4V0k0=0z6s5(4V5*0K0C5{5=5967621^3X3p604$5l3^0l3Y0M5p5r4L6Q3Y6j6m6t4U5H5A040J446z6o3+0=0d6,6u5H0k5J042O6;6$2;0p0=0E1^1A6G5O1~5*5,5}5F6=6}0=2d733I767e4`0S5:7h6B5^5_6F785N0M6N0r5e3_6M6I696h7w6T6d6V4%6Q3`6Z6!6m6A5P6q7l5H5*0h7O5/6_7S1Z5*0c6{741Z6w046y7q6#7!0-7Q7Y7q5|2,5 7y7v0l4g667E6P4e7^6c257{6a4f1R0A3f7J7K6-016(6*0E7Z4n0=0x8e4`6@6/177)7L7b04701w0G7V7,0=777;7a3m6~047d7q8o7W8w8u3J7k8E897Q8I7j7U8L8z8v040c0m7o7/7e7t7@4x7`6f6W7}4x7C808(7F8*8486877J8F0-6(0d5D8n898P5;8R6|8G047R917+8J8Q8y928T0c959a978P8h967f0=7.2*7*3I7$0z7(9n8^010B0d3c8I5*5`8Y9j8!63394O8%6O820l4O8,6e9J7A9L8;6k8?9U9u8P6r9j5@948O6/9z9l8I7$0s9$040w0q0q220L9(5+9-9i9f9k040m7p9{9E6K4)7x819Q4*9Na55m4*7I6l9u6(2w0e0T0E8m9t8~7N9C2,0A574/514;4~180e4@aw2J2E0w1Uat0A4=5|0W0Y0!0F04.
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 w]itkc[v8o-)ylbp_.P3(ajg=/m4rse7Sfd 612:5nuh 050J0F0e0w0d0o0E0K0g0o0w0E0E0z010e0d0q010406050E0R0B0B0w0D0n040H0k0o0R0-0k0Q050A0@0_0{0}0=0q04051d161g0A1d0=0J0d0i0#0%0)0+0%0Q0y0R0w0y0F0l0q0n0e0S140K0S0d0y0S0o1I0S0e0:050W0p0o0F1p0(0*011H1J1L1J0e1R1T1P0e0D1e1D0#100E0q0w0Q0+0N011V1r010I0Y0F0Q0w0B0F1P1;1?1{1X1~1T21230:0a0K0t0D0k0q0k0E0d130Q0K0U1/0D0D0F0g2o16260Q1e0A1D2B1+1-1,1Q0J281s0d0Q202l1P1m1o0$1W2L2N0Q0k2R1P0q2u1e2z2B2(0?1=2p2T1|2X0D0`0o1P0w1G2u0I0+030r0r0g2Y0F1L2W0k0l0C0l0M0:0M160w2)2,0;2+272.1X2:2=2@2_0F2{012}2 31332O360l1_040N3c3e1?3g2z2K013l0w2?1e2^0S2`2|2~300U3v2X3x0u0:0u3C2y3f0=3G3j0+3J3L053N3P3r3R3u2M3w370C0:0C3!173$3h2-1q3k0k2;3K3n3O3p3Q3t3T3?3V370P0:0P3|2(3%2,3H3+463/3s3S324c35370L0:0L4i3~3(413*433m3M3o3q4q3=343x0G0:0G4z3E4k3i4C3I4E454G474I3;4b4L370j0:0j4Q2A1h2$162R2E0J1-2J3)014r2Q1n1e2#0F2%3f3#3E054r51270d0J0+2~2z3x394G595b4a4s4%381`2c0F5i4r3U4u5m2B3d3 3H0f0:0U0I534-4B2U010b0:0K5D57405G0Q0I0:300Q0i0F0D2m140r1L0E0e0F5L5x4_0/040v5(5F2/0:0B5.4l5*0:0m0O5L0=3}543G5h015c2,3x3z3-0K614#5k3@3y5n225p625j5s651P0A3d0K6o5K5/3k0:5!5$5L6q5@4U0k0:0z6w5)4U5+0h0c5|5?585a6h5d373X5g6M6a6j6P6e235q4K6c6Q3C6p6x4T5G5z040I436D6r3*0:0d6/6y5G0k5I042M6@6)2/0p0:0D1?1y6K5N1|5+5-5~5E6^706t20763H797h4_0Q5;7k6F5_5`6J7b5M686S0r6O363n696i4t3x3_0K5o6Y4$6c3_5v046%6%6E5O6t0d5#5%7t7Q1|6A040s7o7R040w0q0q200J7$780:0v6H0m7s2*607w7y4f6R7I6b4d0l4f7G6f7~6U816l6n7O6o7X1X6+6-0D6~776s040x8h3H6`6=157t6(8i3*7104731u7V7^7d1X7j7W6:3I8v2b7.8C7:8J6;045=8E8B0+6G8M3I6=8U5+0c0m7r7t5}8A6L5i7y4w7}6h5r7D4v6W6g6T8:0l8,6$8a7O8c0+6+0d5C8r8~8V8O8X0:0h8U7m6|97040c998Q6 8j8l9h8t018Y8m4_7Z0z6C938F0B0d3a9d5{8$7h7B7y4N8-8@5l4N836X8.6Z809F8{8|8|949b6u8z528F8T9l4m8W9!5^9e8U7Z7#9%4U9b7)7+0Q7-9-5G8D8(9m9b9k9`7i5_7@9X4l9D644(7A7w8/5l4)9K8?7Caa887N6p946+2u0e0R0D8q2(8s9#049Va1540A564.504:4}160e4?aD2H2C0w1SaA0A4;5}0U0W0Y0E04.
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)