Détection de cycles dans un graphe
Un cycle est un sous-graphe dont les sommets peuvent être organisés en séquence \((v_1, v_2, \ldots, v_n)\) de telle sorte que l'ensemble d'arêtes \(A\) est défini par :
\(A = \{(v_i, v_{i+1}) \mid i = 1 \ldots n\} \cup \{(v_n, v_1)\}\)
Étant donné un graphe \(G = (S, A)\), écrivez deux programmes pour détecter un cycle en utilisant les algorithmes suivants :
- Parcours en largeur (BFS)
- Parcours en profondeur (DFS)
Exemple
Dans le graphe ci-dessus, il existe un cycle entre les sommets 3, 4 et 5.
Solution
Pour donner aux lecteurs plus de détails et une meilleure compréhension du problème, nous discuterons de la solution pour les graphes non orientés et orientés séparément.
Parcours en largeur (BFS)
Graphe orienté
La matrice d'adjacence du graphe ci-dessus est :
matriceAdj = [[0, 1, 1, 0, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 1, 0],
[0, 0, 0, 0, 1],
[0, 0, 1, 0, 0]]L'idée est très simple : pour vérifier s'il existe un cycle, il suffit de vérifier s'il existe un chemin partant d'un sommet disons "v" et revenant à ce sommet pour tous les sommets.
S'il existe un tel chemin, nous disons que le graphe contient un cycle.
Exécutez une traversée à partir d'un sommet "v" ; si nous revenons à ce sommet, nous retournons True, sinon False.
Le programme suivant vérifie s'il existe un chemin partant d'un sommet u vers un sommet v :
def exist_chemin(matriceAdj, u, v):
n = len(matriceAdj) # nombre de sommets
file = []
visites = [False] * n
file.append(u)
while file:
courant = file.pop(0)
visites[courant] = True
for i in range(n):
if matriceAdj[courant][i] > 0 and not visites[i]:
file.append(i)
visites[i] = True
# Si i est un noeud adjacent et égal à v (destination)
# donc il existe un chemin de u à i
elif matriceAdj[courant][i] > 0 and i == v:
return True
# pas de chemin entre u et v
return FalseLa fonction ci-dessus est la fonction auxiliaire. Maintenant, pour vérifier s'il existe un cycle, il suffit de vérifier pour tous les sommets s'il existe un chemin partant de ce sommet et y retournant :
def est_cycle(matriceAdj):
n = len(matriceAdj)
for i in range(n):
if exist_chemin(matriceAdj, i, i):
return True
return False
# Test de la fonction
matriceAdj = [[0, 1, 1, 0, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 1, 0],
[0, 0, 0, 0, 1],
[0, 0, 1, 0, 0]]
if est_cycle(matriceAdj):
print("le graphe contient un cycle")
else:
print("le graphe est acyclique")Graphe non orienté
Si nous remplaçons les arêtes orientées entre les sommets par des arêtes non orientées, nous obtenons la matrice suivante (matrice symétrique) :
matriceAdj = [[0, 1, 1, 0, 1],
[1, 0, 0, 0, 0],
[1, 0, 0, 1, 1],
[0, 0, 1, 0, 1],
[1, 0, 1, 1, 0]]Pour un graphe non orienté, nous appliquons simplement le parcours en largeur pour détecter un cycle.
L'idée est d'utiliser un tableau pour mémoriser le parent de chaque sommet (de quel sommet nous avons découvert chaque sommet).
En découvrant les sommets, on vérifie si on retourne à un sommet déjà visité et que ce sommet n'est pas le parent du sommet courant. Si c'est le cas, alors il existe un cycle.
def est_cycle_non_orienté(matriceAdj, u):
n = len(matriceAdj)
file = []
visites = [False] * n
visites[u] = True
# Pour mémoriser à partir de quel sommet nous avons découvert chaque sommet
parent = [-1] * n
parent[u] = u # Au départ, le parent de u est u lui-même
file.append(u)
while file:
courant = file.pop(0)
visites[courant] = True
for i in range(n):
if matriceAdj[courant][i] > 0 and not visites[i]:
file.append(i)
visites[i] = True
parent[i] = courant # Parent de i est le noeud courant
# Si i est un noeud adjacent, déjà visité et i n'est pas le parent de courant
# Donc il y a un cycle
elif matriceAdj[courant][i] > 0 and visites[i] and parent[courant] != i:
return True
return False
# Test de la fonction
matriceAdj = [[0, 1, 1, 0, 1],
[1, 0, 0, 0, 0],
[1, 0, 0, 1, 1],
[0, 0, 1, 0, 1],
[1, 0, 1, 1, 0]]
if est_cycle_non_orienté(matriceAdj, 0):
print("le graphe contient un cycle")
else:
print("le graphe est acyclique")Parcours en profondeur (DFS)
Graphe orienté
L'utilisation du parcours en profondeur est un peu délicate, car l'algorithme est récursif, et derrière chaque algorithme récursif, il existe une pile utilisée pour les appels récursifs.
Parce que pendant l'exécution de l'algorithme nous n'avons pas accès à cette pile, nous allons créer une pile et suivre les sommets déjà dans la pile.
Lors de l'exécution de l'algorithme, si nous revenons à un élément i (visites[i] = True) qui existe déjà dans la pile (pile[i] = True), cela signifie qu'il existe un cycle.
Une fois que nous découvrons un sommet, nous le marquons comme visité (visites[i] = True) et l'ajoutons également à la pile (pile[i] = True). Une fois que nous avons fini de découvrir tous ses sommets adjacents, nous le retirons de la pile (pile[i] = False).
Exemple - factorielle d'un nombre
def fact(n):
if n == 1:
return 1
else:
return n * fact(n-1)
Comme vous pouvez le voir, pendant les appels récursifs, nous ajoutons les appels à la pile. Une fois que nous arrivons au cas de base, nous commençons à supprimer les appels de la pile.
Le programme suivant est la mise en œuvre de l'idée ci-dessus :
def est_cyclique_dfs(matriceAdj, visites, u, pile):
n = len(matriceAdj)
visites[u] = True
pile[u] = True
for i in range(n): # éléments adjacents
if matriceAdj[u][i] > 0 and not visites[i]:
if est_cyclique_dfs(matriceAdj, visites, i, pile):
return True
# si i est un élément adjacent, existe déjà dans la pile et est visité
# donc il existe un cycle
elif matriceAdj[u][i] > 0 and pile[i] and visites[i]:
return True
pile[u] = False
return False
matriceAdj = [[0, 1, 1, 0, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 1, 0],
[0, 0, 0, 0, 1],
[0, 0, 1, 0, 0]]
n = len(matriceAdj)
visites = [False] * n
pile = [False] * n
if est_cyclique_dfs(matriceAdj, visites, 0, pile):
print("le graphe contient un cycle")
else:
print("le graphe est acyclique")Graphe non orienté
La même idée que pour le graphe orienté, mais ici nous devons également vérifier que le sommet adjacent n'est pas le parent du sommet courant :
def est_cyclique_dfs_non_orienté(matriceAdj, visites, u, pile, parent):
n = len(matriceAdj)
visites[u] = True
pile[u] = True
for i in range(n): # éléments adjacents
if matriceAdj[u][i] > 0 and not visites[i]:
parent[i] = u
if est_cyclique_dfs_non_orienté(matriceAdj, visites, i, pile, parent):
return True
# si i est un élément adjacent, existe dans la pile, est visité
# et i n'est pas le parent de u → cycle
elif matriceAdj[u][i] > 0 and pile[i] and visites[i] and parent[u] != i:
return True
pile[u] = False
return False
matriceAdj = [[0, 1, 1, 0, 1],
[1, 0, 0, 0, 0],
[1, 0, 0, 1, 1],
[0, 0, 1, 0, 1],
[1, 0, 1, 1, 0]]
n = len(matriceAdj)
visites = [False] * n
pile = [False] * n
parent = [-1] * n
parent[0] = -1 # parent du sommet de départ
if est_cyclique_dfs_non_orienté(matriceAdj, visites, 0, pile, parent):
print("le graphe contient un cycle")
else:
print("le graphe est acyclique")- Un cycle existe s'il y a un chemin d'un sommet vers lui-même.
- Pour les graphes orientés, on utilise une pile supplémentaire pour suivre les sommets dans la récursion.
- Pour les graphes non orientés, il faut aussi vérifier que le sommet adjacent n'est pas le parent.
- BFS est itératif, DFS est récursif (mais peut aussi être implémenté itérativement).
- La matrice d'adjacence est utilisée pour représenter le graphe.
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.