Aller au contenu

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 connexes1 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 5

graphe_6 :

graphe 6

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013f06S:d=F4yr./oTpg2mcb1!w937v{e[ l,8+P5)ti]kn;ua(}_sh050g0E0O0V0P0H0Z0G0u0H0V0Z0Z0h010O0P0q010406050Z0U0t0t0V0l0k040e0o0H0U0^0o0S050n0 1113150}0q04051l1e1o0n1l0}0g0P0C0-0/0;0?0!0P0r0!0H1C0!0O0{050(0v0H0E1x0:0=011B1D1F1D0O1L1N1J0O0l1m0O0!0-180Z0q0V0S0?0s011P1z010b0*0E0S0V0t0E1J1,1.1?1R1_1N1|1~0{0a0G0L0l0o0q0o0Z0P1b0S0G0$1*0l0l0E0u2j1e210S1m0n1(2w1#1%1$1K0g230?1F0S1{2g1J1u1w0.1Q2G0P2I0S0o2M1J0q2p1m2u2w2!0~1-2k2O1@2T0l120H0{0G0w2t2(0|2%222*1R2,2.2:0s2?1.2^2u2F012}0V2/040G0A312v0}342{0?37390G0j3d332(353j2:0M3n3f3p3h360o2-382:0d3u2_2)1y2|3z2~3a0B3E3g3H3i3J3B3a0J3N3w3P3y3A3k0z3V2`3X3r040w0c3$3G2P3Y3K0w2=1f2@3v3%3/3)0w303@321p2Y1e2M2z0g1%2E3x0u2U1 1m441n422$3 2v054a0$2Z3W3/0R0{0$0b3n3F350y2:4u3O3{0b0{0u0k0.0E0Y0v0b0Z4z4o1@0`040W4M3`2+0{0r0l0V0q0!0E4S3.4O0{0I3n0G4v3x0S4r0E1-0l0O4$354P0N0f3u0G4~4,4A4U041u0Z0(0S0u0E4L4i3a4-3X0o0{0h4+5d3/4P0D4^4.4:4=4@5b504N1R4P4|5s5j1@0t0P0{3,5b5z5v0{0X4}4 5G3i0{254#5y511R5f045h5R5u0?4P0F5n3(5p135r2$5S5Z0{0Q5K4~5M014q040y1B1N5i5,365O1`5|5Y015U0x5W2!5t4T5H040F0Q5x2!064 6h684%2|0{0Z0o110%61690?5U662@6j3q5 5{5F5}5U0m5$3{0{2f0q6F4(4Q6K1R5B5D6N5-040N5:6i5=5@0b3z6r6k5N040C0o0P2h1d5X6s634x042R6#6y044W4Y4!6R015!6}4/046n6p5*2@5=4P6d6V6i5L5}5@0P4t6.6$5~6(6*6,6@3x0o6;2T75326x7o6;6?7h6^5456585a5+625w7a7b6W5}717A1.7C6}6 6B62716)6+7x7E6/787n5e5g7!6G536+7B597P0{5#7R6/71731~7s4j5}7Z7y7o0{0K7%5A5C3*7H7I7c7S6z5Q7X7i6D700{4Y0q1{0g7-6M7:7i7T7l7W767`0{6U5b6g85866/5@0E1F7g675=7L7*7N7,8l4_7.8d7k7V6-8a8K045/7|7#04020r0O0T6v7t8E4r8G578I8Q3x7Q8,5%726o7@8j798u8w7I6X0{2p0O0U0l8P6w6X0u0{0p0l0U893^6h8|048~90928$7d95040i380Z9a320}0n4l0E2w2X9u431v452z2C2x0V1M9x0n449r0$0(0*0Z04.

II. Algorithme récursif⚓︎

Recherche de cycle récursive

Tester ci-dessous

Les graphes utilisés pour les tests sont :

graphe_5 :

graphe 5

graphe_6 :

graphe 6

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier

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

  1. Voir : Les graphes - Structure au paragraphe 1.2.4 : Structures de graphes ↩