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 :
graphe_6 :
.128013 vt4=8fw2pmuP(751,:cSsFr]{k[63;0 dg)}/+n9iyelh_boaT.!- 050H0R0c0X0P0S0v0G0t0S0X0v0v0e010c0P0j010406050v0l0k0k0X0x0Q040u0W0S0l0_0W0N050L101214160~0j04051m1f1p0L1m0~0H0P0b0.0:0=0@0:0N0I0l0X0I0R0#0j0Q0c0T1d0G0T0P0I0T0S1R0T0c0|050)0V0S0R1y0;0?011Q1S1U1S0c1!1$1Y0c0x1n1M0.190v0j0X0N0@0i011(1A010g0+0R0N0X0k0R1Y1}1 241*271$2a2c0|0a0G0m0x0W0j0W0v0P1c0N0G0%1{0x0x0R0t2x1f2f0N1n0L1M2K1@1_1^1Z0H2h1B0P0N292u1Y1v1x0/1)2U2W0N0W2!1Y0j2D1n2I2K2;0 1~2y2$252*0x130S1Y0X1P2D0g0@030U0U0t2+0R1U2)0W0#0F0#0q0|0G0q1f0X2=2^0}2@2g2`1*2|2~30320R340136383a3c2X3f0#22040G0i3m3o1 3q2I2T013v0X2 1n310T333537390%3F2*3H0D3j0D3N2H3p0~3R3t0@3U3W053Y3!3B3$3E2V3G3g0d3j0d3/1g3;3r2_1z3u0W2}3V3x3Z3z3#3D3(413*3g0p3j0p472;3=2^3S3_4h3}3C3%3b4n3e3g0C3j0C4t493?4c3^4e3w3X3y3A4B403d3H0o3j0o4K3P4v3s4N3T4P4g4R4i4T3 4m4W3g0f3j0f4#2J4%4b2%4*4f3`3|4j3~4l4D4=0#0O3j0O4`3Q4w3@4 4Q3{4S4k4C3)4F3h0F0|0q0F5c4|4x4+515j545l4E3H0q3i045D5t4a5v504z534U4;423h3J0q3M0L3n3:3P1q2/1f2!2N0H1_2S5f4C2Z1w1n2.0R2:3p5W2J054C5;2g0P0H0@372I5C3x5|5~555m610G2l0R645A575E3/4M4~0A0|0%0g5?5`4}250h3j6m5I5f0N0g0|0t0Q0/0R0U0V0g0v6s6g250{040n6G5e4)0N0|0I0x0X0j0T0R6M4(4~6J0r6m0G6t6O6j0R1~0x0c6X6o1*6J0J0s6m0~485X3R63015 2^3H3J5i6}4:565P22682b6a6~655B3g725U3K0G7j6(4~6P041v0v0)0N0t0R6F6`2J6%6H1*0W0|0e6$7l6I0|0z6/4x6*6,6.7w3K7F6;0|6@7O7y6N4~0k0P0|5s7O7Q0@6J0K6^7J740U603g3,4R7-6c5P3,792c6b4V7^1Y7h7j7k7z3^0|2j6W7U7%017B047D8883016J0B7J6u7L147N2?8f6J0y7+7$6|5}7c7/0#447=8v75664323697|5O4o8y7 3n817V6Y256i040h1Q1$7E8f7n868W7W258b0!8d2;8O6:7(0|0B0y7T4u7,8B7.704p628@7@8J4q7`7b8C7e0#4q2K8M8N81897n0v0W120(8!8P7A7C9g8,3T85288j4)8b0Z9p7m0|2t0j9t7G6K9y1*7Y7!9B8-040J8s8o4w7-8x4H8A8H768J4H909Q8D0#9O3N98998f8R0g4e9k7K040b0W0P2v1e8e8#7A6q042V9*8k046R6T6V9F8g8.a19b9d2c8n5=8p0|8:9Ja99L8@8x4Y9P7c8}5n4Y9Uak7}8Jai9Z9!98898R0P6l9=9h849,9.9:9{9q9^2*a83P8+3S0W9^9`aA9l7n7p7r7t7v9KaBa2048;498taf648x4@aj92574@aoa.5Pa,atauau9a6j9/aV7ua18ha40|9-9/aQaY9l8qaG4~8b8)3paM9|aU1 aWb0a3a(aZa59eaK5@aa048raRaN0|0Mba259D5Fad6{a)8w8_588{9V9359a;7d5759967ia_9!a{048Zbm9l9rb2046T0j290Hbk9AbY9+b4aFb-5f6=bDbrbF6 1 5C5pa-bO5P5r8F7abK6db}a^bTaw0|4Daz8*bVbh7sa b;4)b1ci9uaDb59;b73Sb9bv5f8b020I0c0EbdaLcea}bichcqb=blcG6)049cbpb+ac7O6_cq9MbH5DbJap8I5ncVbNal5C6e80bTbU9$0|2D0c0l0xcpbeaw0t0|0Y0x0l878=b-cTb{3g5ScWa=8Jd3c#aqcZ7g97829?0@8Rc.c:c=cB9$c^040w3V0vc}a%2?0L5_5Y5:5!5-1f0c5%dA2Q2L0X1#dx0L5#6_0%0)0+0v04.
II. Algorithme récursif
Recherche de cycle récursive
Tester ci-dessous
Les graphes utilisés pour les tests sont :
graphe_5 :
graphe_6 :
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)