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 :

graph LR
    A --- B
    B --- E
    A --- C

graphe_6 :

graph LR
    A --- B
    A --- C
    C --- D
    C --- E
    E --- D

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Ctrl+Clic pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
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

.1280130ldTy1,4{]k/we!ibmc_:35}aPr+ 7F=9o[f.gt28;6sSh)(punv050d0o0N0z0q0c0S0D0t0c0z0S0S0G010N0q0X010406050S0Y0s0s0z0B0f040T0I0c0Y0^0I0Z050m0 1113150}0X04051l1e1o0m1l0}0d0q0!0-0/0;0?0U0q0M0U0c1C0U0N0{050(0r0c0o1x0:0=011B1D1F1D0N1L1N1J0N0B1m0N0U0-180S0X0z0Z0?0O011P1z010K0*0o0Z0z0s0o1J1,1.1?1R1_1N1|1~0{0a0D0A0B0I0X0I0S0q1b0Z0D0$1*0B0B0o0t2j1e210Z1m0m1(2w1#1%1$1K0d230?1F0Z1{2g1J1u1w0.1Q2G0q2I0Z0I2M1J0X2p1m2u2w2!0~1-2k2O1@2T0B120c0{0D0g2t2(0|2%222*1R2,2.2:0O2?1.2^2u2F012}0z2/040D0w312v0}342{0?37390D0i3d332(353j2:0x3n3f3p3h360I2-382:0R3u2_2)1y2|3z2~3a0E3E3g3H3i3J3B3a0P3N3w3P3y3A3k0H3V2`3X3r040g0b3$3G2P3Y3K0g2=1f2@3v3%3/3)0g303@321p2Y1e2M2z0d1%2E3x0t2U1 1m441n422$3 2v054a0$2Z3W3/0l0{0$0K3n0D3F3q0K0{0t0f0.0o0u0r0K0S3n4w3x0`040W4I3O3{0{0M0B0z0X0U0o4O4o1@4L0h4u4J3(4r0o1-0B0N4Y3`4!0{0V0v3u0D4_4v4P2+4r0q0S0(0Z0t0o4H4i3a4(3/0I0{0G4%4|1R4L0j4/3.4}040$4,4.564{4Z5f0{4@5p581@0s0q0{3,565w5s040y4^4`5D3i0{254X5v5e0?5a045c5O5r0?4L0J5i3q4*5n5Z4K0{0k5H4_5J014q040n1B1N5d5V365L1`5@4:1R5R0p5T2!5q5}5W0{0J0k5u2!064`6c635j2|0{0S0I110%5|6f5Q5b6m5!045M5%3X5R0L6u4Q042f0X6y4;4M6D1R5y5A6G65040V5+6d5-5/0K3z6q3x0Z0{0!0I4 2R6U6v0n0{6#5U645_044S4U4W6K015X6=6W046i6k5o2$5P6?5)693^6d746e355/0q4t6+6n6-6Y6!1d7b350I6(042T6}2@763x7j6)7g625-6_1u501.53556~5^4L72326b757I7v4~7y52546=6@5C6 6_7e2h7t2@5-4L5*7h7q6p7#4)5l4 517A7P666^6h6j1~7n406 7Z6$590{0C7{5x5z3*6O7I6c7K6s5{7R5^6w7:044U0X1{0d7.6F896,7T6Z7V8i6N567H847p3X5/0o1F7a7u7S7L7,7O8k7c7Q7C8l6X8n6*8I8G5)7 5~0{020M0N0Q617o867x8D7B7X7_7/8F6r6{7?8i68838t8u4p0{2p0N0Y0B7W328=1@0l0t0{0e0B0Y5N6a856 5/8^8`8|2v8~1R900{0F380S963^1e4l0o2w2X9q431v452z2C2x0z1M9t0m440}9D0%0)0+04.

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

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Ctrl+Clic pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
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 ↩