Détermination de la présence d'un cycle - Exemple 2

Algorithme

def parcours_rec_cycle(g, s, d):
    if d[s] == "gris":
        return True
    if d[s] == "noir":
        return False
    d[s] = "gris"
    for voisin in g.liste_voisins(s):
        if parcours_rec_cycle(g, voisin, d):
            return True
    d[s] = "noir"
    return False

Déroulement détaillé sur un exemple

Graphe

On recherche les cycles à partir du sommet ①.

from classeGraphe import *

# Construction de l'objet Graphe g2
g2 = Graphe()
g2.ajout_sommet(1)
g2.ajout_sommet(2)
g2.ajout_sommet(3)
g2.ajout_sommet(4)
g2.ajout_sommet(5)
g2.ajout_arc(1, 2)
g2.ajout_arc(1, 5)
g2.ajout_arc(2, 3)
g2.ajout_arc(3, 4)
g2.ajout_arc(4, 2)
g2.ajout_arc(5, 3)

# Dictionnaire avec tous les sommets étiquetés en "Blanc"
d_blanc = {1: "blanc", 2: "blanc", 3: "blanc", 4: "blanc", 5: "blanc"}

# Choix du sommet de départ
s2 = 1

# Lancement de la recherche d'un cycle
resultat = parcours_rec_cycle(g2, s2, d_blanc)

Déroulement détaillé

p_r_c avec s = 1 et d = {1:"blanc",2:"blanc",3:"blanc",4:"blanc",5:"blanc"}

Ligne 2 : Comme ① n'est pas "gris", alors rien

Ligne 4 : Comme ① n'est pas "noir", alors rien

Ligne 6 : ① est étiqueté à "gris" donc d = {1:"gris", 2:"blanc",3:"blanc",4:"blanc",5:"blanc"}

Ligne 7 : Boucle (🡆) avec les voisins de ①, c'est-à-dire ② et ⑤ :

🡆 Itération avec voisin = 2 :

Ligne 8 : Comme...

p_r_c avec s = 2 et d = {1:"gris",2:"blanc",3:"blanc",4:"blanc",5:"blanc"}

Ligne 2 : Comme ② n'est pas "gris", alors rien

Ligne 4 : Comme ② n'est pas "noir", alors rien

Ligne 6 : ② est étiqueté à "gris" donc d = {1:"gris",2:"gris",3:"blanc",4:"blanc",5:"blanc"}

Ligne 7 : Boucle (🡆) avec les voisins de ②, c'est-à-dire ③ :

🡆 Itération avec voisin = 3 :

Ligne 8 : Comme ..

p_r_c avec s = 3 et d = {1:"gris",2:"gris",3:"blanc",4:"blanc",5:"blanc"}

Ligne 2 : Comme ③ n'est pas "gris", alors rien

Ligne 4 : Comme ③ n'est pas "noir", alors rien

Ligne 6 : ③ est étiqueté à "gris" donc d = {1:"gris", 2:"gris",3:"gris",4:"blanc",5:"blanc"}

Ligne 7 : Boucle (🡆) avec les voisins de ③, c'est-à-dire ④ :

🡆 Itération avec voisin = 4 :

Ligne 8 : Comme...

p_r_c avec s = 4 et d_t = {1:"gris",2:"gris",3:"gris",4:"blanc",5:"blanc"}

Ligne 2 : Comme ④ n'est pas "gris", alors rien

Ligne 4 : Comme ④ n'est pas "noir", alors rien

Ligne 6 : ④ est étiqueté à "gris" donc d = {1:"gris",2:"gris",3:"gris",4:"gris",5:"blanc"}

Ligne 7 : Boucle (🡆) avec les voisins de ④, c'est-à-dire ② :

🡆 Itération avec voisin = 2 :

Ligne 8 : Comme...

p_r_c avec s = 2 et d = {1:"gris",2:"gris",3:"gris",4:"gris",5:"blanc"}

Ligne 2 : Comme ② est "gris", alors return True

True

... alors return True

True

... alors return True

True

... alors return True

True

... alors return True

True