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
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 --- Cgraphe_6 :
graph LR
A --- B
A --- C
C --- D
C --- E
E --- D
Lancer # Testsbksl-nlgraphepy-und5 = {"A":["B", "C"], "B":["A", "E"], "C":["A"], "E":["B"]}bksl-nlgraphepy-und6 = {"A":["B", "C"], "B":["A"], "C":["A", "D", "E"], "D": ["C", "E"], "E":["C", "D"]}bksl-nlassert cyclepy-undbfs(graphepy-und5, "A") == Falsebksl-nlassert cyclepy-undbfs(graphepy-und6, "A") == Truebksl-nlbksl-nl# Autres testsbksl-nlgraphepy-und1 = {"A":["B", "C"], "B":["A", "D", "E"], "C":["A", "D"],bksl-nl"D":["B", "C", "E"], "E":["B", "D", "F", "G"], "F":["E", "G"], "G":["E", "F", "H"],bksl-nl"H":["G"]}bksl-nlgraphepy-und2 = {"A":["B", "C"], "B":["A", "E"], "C":["A"],bksl-nl"E":["B", "F"], "F":["E"]}bksl-nlgraphepy-und3 = {"A":["B"], "B":["A", "C"], "C":["B"]}bksl-nlgraphepy-und4 = {"A":["B", "D", "E"],"B":["A", "C"],"C":["B", "D"],bksl-nl"D":["A","C","E"],"E":["A", "D", "F", "G"],"F":["E", "G"],"G":["E", "F", "H"],"H":["G"]}bksl-nlgraphepy-und7 = {"A":["B", "C"],"B":["A"],"C":["A", "D", "F"],bksl-nl"D":["C","E"],"E":["D", "F"],"F":["C", "E"]}bksl-nlassert cyclepy-undbfs(graphepy-und1, "A") == Truebksl-nlassert cyclepy-undbfs(graphepy-und2, "A") == Falsebksl-nlassert cyclepy-undbfs(graphepy-und3, "A") == Falsebksl-nlassert cyclepy-undbfs(graphepy-und4, "A") == Truebksl-nlassert cyclepy-undbfs(graphepy-und7, "A") == Truebksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder def cyclepy-undbfs(graphe, depart):bksl-nl distances = {depart : 0}bksl-nl file = [depart]bksl-nl while file != []:bksl-nl sommet = ...bksl-nl for voisin in ...:bksl-nl if voisin not in distances:bksl-nl distances[voisin] = ...bksl-nl file.append(voisin)bksl-nl elif distances[voisin] >= distances[sommet]:bksl-nl return ...bksl-nl return ...bksl-nlbksl-nl# Testsbksl-nlgraphepy-und5 = {"A":["B", "C"], "B":["A", "E"], "C":["A"], "E":["B"]}bksl-nlgraphepy-und6 = {"A":["B", "C"], "B":["A"], "C":["A", "D", "E"], "D": ["C", "E"], "E":["C", "D"]}bksl-nlassert cyclepy-undbfs(graphepy-und5, "A") == Falsebksl-nlassert cyclepy-undbfs(graphepy-und6, "A") == Truebksl-nlbksl-nl def cyclepy-undbfs(graphe, depart):bksl-nl distances = {depart : 0}bksl-nl file = [depart]bksl-nl while file != []:bksl-nl sommet = file.pop(0)bksl-nl for voisin in graphe[sommet]:bksl-nl if voisin not in distances:bksl-nl distances[voisin] = distances[sommet] + 1bksl-nl file.append(voisin)bksl-nl elif distances[voisin] >= distances[sommet]:bksl-nl return Truebksl-nl return Falsebksl-nlbksl-nlbksl-nl
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 --- Cgraphe_6 :
graph LR
A --- B
A --- C
C --- D
C --- E
E --- D
def cherchepy-undcyclepy-undrec(graphe, sommet, vus=None):bksl-nl if vus is None:bksl-nl vus = {sommet: None}bksl-nl precedent = vus[sommet]bksl-nl for voisin in graphe[sommet]:bksl-nl if voisin != precedent:bksl-nl if voisin in vus:bksl-nl return Truebksl-nl else:bksl-nl vus[voisin] = sommetbksl-nl if cherchepy-undcyclepy-undrec(graphe, voisin, vus):bksl-nl return Truebksl-nl return Falsebksl-nlbksl-nl# Testsbksl-nlgraphepy-und5 = {"A":["B", "C"], "B":["A", "E"], "C":["A"], "E":["B"]}bksl-nlgraphepy-und6 = {"A":["B", "C"], "B":["A"], "C":["A", "D", "E"], "D": ["C", "E"], "E":["C", "D"]}bksl-nlassert cherchepy-undcyclepy-undrec(graphepy-und5, "A") == Falsebksl-nlassert cherchepy-undcyclepy-undrec(graphepy-und6, "A") == Truebksl-nlprint("😀")bksl-nlbksl-nl 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