en + Cycles - compléments
On peut trouver d'autres algorithmes pour la détection de cycles.
Info
Nous nous plaçons dans le cas de graphes connexes non orientés.
I. Utiliser les distances
Les distances
On parcourt le graphe en largeur, Ă partir d'un sommet depart choisi au hasard. Au fur et Ă mesure de la progression,
on construit le dictionnaire distances qui prend comme clés les sommets visités, et comme valeur associée à chaque clé la distance
à laquelle il se trouve du sommet de départ (nombre d'arcs), que nous appelons ici distance. Le parcours étant un parcours en largeur,
les distances des sommets parcourus restent les mêmes, ou augmentent. Si la distance d'un voisin d'un sommet, est supérieure ou égale
Ă la distance du sommet, cela signifie qu'on ne provient pas de ce sommet. On arrĂŞte le parcours, et la fonction renvoie True.
Ă€ vous de jouer
Compléter le script ci-dessous
Les graphes utilisés pour les tests sont :
graphe_5 :
graph LR
A --- B
B --- E
A --- C
graphe_6 :
graph LR
A --- B
A --- C
C --- D
C --- E
E --- D
.128013 l(9 _4:;=vTm26!-uS8w.s3/]+fr7g}ebh[pPic05a,{onkFyd1)t 050Y0G0#0Q0M0b0w0e0N0b0Q0w0w0j010#0M0K010406050w0r0m0m0Q0C0X040s0T0b0r0_0T0U050y101214160~0K04051m1f1p0y1m0~0Y0M0k0.0:0=0@0:0U0E0r0Q0E0G0q0K0X0#0I1d0e0I0M0E0I0b1R0I0#0|050)0H0b0G1y0;0?011Q1S1U1S0#1!1$1Y0#0C1n1M0.190w0K0Q0U0@0n011(1A010B0+0G0U0Q0m0G1Y1}1 241*271$2a2c0|0a0e0L0C0T0K0T0w0M1c0U0e0%1{0C0C0G0N2x1f2f0U1n0y1M2K1@1_1^1Z0Y2h1B0M0U292u1Y1v1x0/1)2U2W0U0T2!1Y0K2D1n2I2K2;0 1~2y2$252*0C130b1Y0Q1P2D0B0@030f0f0N2+0G1U2)0T0q0O0q0Z0|0e0Z1f0Q2=2^0}2@2g2`1*2|2~30320G340136383a3c2X3f0q22040e0n3m3o1 3q2I2T013v0Q2 1n310I333537390%3F2*3H0x3j0x3N2H3p0~3R3t0@3U3W053Y3!3B3$3E2V3G3g0g3j0g3/1g3;3r2_1z3u0T2}3V3x3Z3z3#3D3(413*3g0P3j0P472;3=2^3S3_4h3}3C3%3b4n3e3g0o3j0o4t493?4c3^4e3w3X3y3A4B403d3H0D3j0D4K3P4v3s4N3T4P4g4R4i4T3 4m4W3g0t3j0t4#2J4%4b2%4*4f3`3|4j3~4l4D4=0q0d3j0d4`3Q4w3@4 4Q3{4S4k4C3)4F3h0O0|0Z0O5c4|4x4+515j545l4E3H0Z3i045D5t4a5v504z534U4;423h3J0Z3M0y3n3:3P1q2/1f2!2N0Y1_2S5f4C2Z1w1n2.0G2:3p5W2J054C5;2g0M0Y0@372I5C3x5|5~555m610e2l0G645A575E3/4M4~0V0|0%0B5?5`4}250u3j6m5I5f0U0B0|0N0X0/0G0f0H0B0w6s6g250{040c6G5e4)0U0|0E0C0Q0K0I0G6M4(4~6J0R6m0e6t6O6j0G1~0C0#6X6o1*6J0!0h6m0~485X3R63015 2^3H3J5i6}4:565P22682b6a6~655B3g725U3K0e7j6(4~6P041v0w0)0U0N0G6F6`2J6%6H1*0T0|0j6$7l6I0|0S6/4x6*6,6.7w3K7F6;0|6@7O7y6N4~0m0M0|5s7O7Q0@6J0F6^7J740f603g3,4R7-6c5P3,792c6b4V7^1Y7h7j7k7z3^0|2j6W7U7%017B047D8883016J0J7J6u7L147N2?8f6J0z7+7$6|5}7c7/0q447=8v75664323697|5O4o8y7 3n817V6Y256i040u1Q1$7E8f7n868W7W258b0p8d2;8O6:7(0|0J0z7T4u7,8B7.704p628@7@8J4q7`7b8C7e0q4q2K8M8N81897n0w0T120(8!8P7A7C9g8,3T85288j4)8b0v9p7m0|2t0K9t7G6K9y1*7Y7!9B8-040!8s8o4w7-8x4H8A8H768J4H909Q8D0q9O3N98998f8R0B4e9k7K040k0T0M2v1e8e8#7A6q042V9*8k046R6T6V9F8g8.a19b9d2c8n5=8p0|8:9Ja99L8@8x4Y9P7c8}5n4Y9Uak7}8Jai9Z9!98898R0M6l9=9h849,9.9:9{9q9^2*a83P8+3S0T9^9`aA9l7n7p7r7t7v9KaBa2048;498taf648x4@aj92574@aoa.5Pa,atauau9a6j9/aV7ua18ha40|9-9/aQaY9l8qaG4~8b8)3paM9|aU1 aWb0a3a(aZa59eaK5@aa048raRaN0|0Aba259D5Fad6{a)8w8_588{9V9359a;7d5759967ia_9!a{048Zbm9l9rb2046T0K290Ybk9AbY9+b4aFb-5f6=bDbrbF6 1 5C5pa-bO5P5r8F7abK6db}a^bTaw0|4Daz8*bVbh7sa b;4)b1ci9uaDb59;b73Sb9bv5f8b020E0#0ibdaLcea}bichcqb=blcG6)049cbpb+ac7O6_cq9MbH5DbJap8I5ncVbNal5C6e80bTbU9$0|2D0#0r0Ccpbeaw0N0|0l0C0r878=b-cTb{3g5ScWa=8Jd3c#aqcZ7g97829?0@8Rc.c:c=cB9$c^040W3V0wc}a%2?0y5_5Y5:5!5-1f0#5%dA2Q2L0Q1#dx0y5#6_0%0)0+0w04.
II. Algorithme récursif
Recherche de cycle récursive
Tester ci-dessous
Les graphes utilisés pour les tests sont :
graphe_5 :
graph LR
A --- B
B --- E
A --- C
graphe_6 :
graph LR
A --- B
A --- C
C --- D
C --- E
E --- D
Nous pouvons observer le déroulement dans Python Tutor pour ces deux graphes :
Déroulé pour graphe_6
Déroulé pour graphe_5
III. Site créé par Frédéric ZINELLI
AlgoGraphe
Crédits
Serge Bays, Romain Janvier
# Tests(insensible Ă la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)