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 w]itkc[v8o-)yl0bp_!.P3(a;+g=/m}T4rse97Sf,d{ 612:F5nuh 050Q0K0e0y0d0o0J0S0g0o0y0J0J0C010e0d0r010406050J0!0E0E0y0I0n040N0k0o0!0_0k0Z050D101214160~0r04051m1f1p0D1m0~0Q0d0i0.0:0=0@0:0Z0B0!0y0B0K0l0r0n0e0#1d0S0#0d0B0#0o1R0#0e0|050)0q0o0K1y0;0?011Q1S1U1S0e1!1$1Y0e0I1n1M0.190J0r0y0Z0@0V011(1A010O0+0K0Z0y0E0K1Y1}1 241*271$2a2c0|0a0S0v0I0k0r0k0J0d1c0Z0S0%1{0I0I0K0g2x1f2f0Z1n0D1M2K1@1_1^1Z0Q2h1B0d0Z292u1Y1v1x0/1)2U2W0Z0k2!1Y0r2D1n2I2K2;0 1~2y2$252*0I130o1Y0y1P2D0O0@030s0s0g2+0K1U2)0k0l0p0l0U0|0S0U1f0y2=2^0}2@2g2`1*2|2~30320K340136383a3c2X3f0l22040S0V3m3o1 3q2I2T013v0y2 1n310#333537390%3F2*3H0w3j0w3N2H3p0~3R3t0@3U3W053Y3!3B3$3E2V3G3g0H3j0H3/1g3;3r2_1z3u0k2}3V3x3Z3z3#3D3(413*3g0Y3j0Y472;3=2^3S3_4h3}3C3%3b4n3e3g0T3j0T4t493?4c3^4e3w3X3y3A4B403d3H0M3j0M4K3P4v3s4N3T4P4g4R4i4T3 4m4W3g0j3j0j4#2J4%4b2%4*4f3`3|4j3~4l4D4=0l0L3j0L4`3Q4w3@4 4Q3{4S4k4C3)4F3h0p0|0U0p5c4|4x4+515j545l4E3H0U3i045D5t4a5v504z534U4;423h3J0U3M0D3n3:3P1q2/1f2!2N0Q1_2S5f4C2Z1w1n2.0K2:3p5W2J054C5;2g0d0Q0@372I5C3x5|5~555m610S2l0K645A575E3/4M4~0f0|0%0O5?5`4}250b3j6m5I5f0Z0O0|0g0n0/0K0s0q0O0J6s6g250{040x6G5e4)0Z0|0B0I0y0r0#0K6M4(4~6J0P6m0S6t6O6j0K1~0I0e6X6o1*6J0m0W6m0~485X3R63015 2^3H3J5i6}4:565P22682b6a6~655B3g725U3K0S7j6(4~6P041v0J0)0Z0g0K6F6`2J6%6H1*0k0|0C6$7l6I0|0R6/4x6*6,6.7w3K7F6;0|6@7O7y6N4~0E0d0|5s7O7Q0@6J0F6^7J740s603g3,4R7-6c5P3,792c6b4V7^1Y7h7j7k7z3^0|2j6W7U7%017B047D8883016J0h7J6u7L147N2?8f6J0c7+7$6|5}7c7/0l447=8v75664323697|5O4o8y7 3n817V6Y256i040b1Q1$7E8f7n868W7W258b0t8d2;8O6:7(0|0h0c7T4u7,8B7.704p628@7@8J4q7`7b8C7e0l4q2K8M8N81897n0J0k120(8!8P7A7C9g8,3T85288j4)8b0u9p7m0|2t0r9t7G6K9y1*7Y7!9B8-040m8s8o4w7-8x4H8A8H768J4H909Q8D0l9O3N98998f8R0O4e9k7K040i0k0d2v1e8e8#7A6q042V9*8k046R6T6V9F8g8.a19b9d2c8n5=8p0|8:9Ja99L8@8x4Y9P7c8}5n4Y9Uak7}8Jai9Z9!98898R0d6l9=9h849,9.9:9{9q9^2*a83P8+3S0k9^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{048Zbm9l9rb2046T0r290Qbk9AbY9+b4aFb-5f6=bDbrbF6 1 5C5pa-bO5P5r8F7abK6db}a^bTaw0|4Daz8*bVbh7sa b;4)b1ci9uaDb59;b73Sb9bv5f8b020B0e0zbdaLcea}bichcqb=blcG6)049cbpb+ac7O6_cq9MbH5DbJap8I5ncVbNal5C6e80bTbU9$0|2D0e0!0Icpbeaw0g0|0G0I0!878=b-cTb{3g5ScWa=8Jd3c#aqcZ7g97829?0@8Rc.c:c=cB9$c^040X3V0Jc}a%2?0D5_5Y5:5!5-1f0e5%dA2Q2L0y1#dx0D5#6_0%0)0+0J04.
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)