Détecter un cycle dans un graphe orienté et non orienté
Un cycle est un sous graphe dont les sommets peuvent être organisés en séquence \((v_1,v_2,..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..n\} \cup \{(v_n,v_1)\}$$
Etant donné un graphe \(G=(S,A)\), écrivez deux programmes pour détecter un cycle en utilisant les algorithmes suivants :
- Parcours en largeur
- Parcours en profondeur
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
Parcours en largeur
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], ]
Idée
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. Maintenant, la question est de savoir comment vérifier un tel chemin?
De plus, la réponse à cette question est très simple, exécutez une traversée à partir d'un sommet "v" si nous revenons à ce sommet, nous retournons True sinon retournons False.
Le programme suivant vérifie s'il existe un chemin partant d'un sommet u vers un sommet v
def ExistChemin(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 visites[i] == False: 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 False
La fonction ci-dessus est la fonction principale, maintenant pour vérifier s'il existe un cycle, il suffit de vérifier tous les sommets s'il existe un chemin partant de ce sommet et y retournant
def estCycle(matriceAdj): n = len(matriceAdj) for i in range(n): if ExistChemin(matriceAdj, i, i) == True: return True return False # tester 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 Cycle(matriceAdj) == True: 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 au 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 estCycle(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 du graphe parent = [-1] * n # Au départ le parent de u est u lui même parent[u] = u file.append(u) while file: courant = file.pop(0) visites[courant] = True for i in range(n): if matriceAdj[courant][i] > 0 and visites[i] == False: file.append(i) visites[i] = True # Parent de i et le noeud courant parent[i] = 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, retourner True elif matriceAdj[courant][i] > 0 and visites[i] == True and parent[courant] != i: return True return False # Tester 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 estCycle(matriceAdj, 0) == True: print("le graphe contient un cycle") else: print("le graphe est acyclique")
Parcours en profondeur
Graphe orienté
L'utilisation de la parcours en profondeur est un peu délicate, car l'algorithme est récursif, et comme vous le savez 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
Maintenant, une question vient à l'esprit de chaque lecteur, comment cette pile est utile pour détecter un cycle ?
Avant de discuter de notre problème, je vais prendre un exemple de la façon dont les appels récursifs sont empiler vers la pile et dépiler
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 récursifs à la pile, une fois que nous arrivons au cas de base, nous commençons à supprimer les appels récursifs de la pile
J'espère que c'est clair. Si vous avez une question, laissez-la dans la section des commentaires ci-dessous
Revenons maintenant à la question de savoir comment il est utile de savoir quel élément est déjà dans la pile
Lors de l'exécution de l'algorithme, si nous revenons à un élément I (Visités[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 rendons comme visité (Visités[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 supprimons de la pile (Pile[i] = False)
Le programme suivant est la mise en œuvre de l'idée ci-dessus
def estCyclique(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 visites[i] == False: estCyclique(matriceAdj, visites, i, pile) # si i est un element adjacent (matriceAdj[u][i] > 0) # i existe déjà dans la pile # i est déjà visité # donc il existe un cycle elif matriceAdj[u][i] > 0 and pile[i] == True and visites[i] == True: 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], ] visites = [False] * (len(matriceAdj)) pile = [False] * (len(matriceAdj)) if estCyclique(matriceAdj, visites, 0, pile) == True: print("le graphe contient un cycle") else: print("le graphe est acyclique")
Graphe non orienté
La même idée pour le graphe orienté, mais ici nous devons également vérifier lorsque nous revenons à un sommet, ce sommet n'est pas le parent du sommet de l'appelant
def estCyclique(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 visites[i] == False: parent[i] = u estCyclique(matriceAdj, visites, i, pile, parent) # si i est un element adjacent (matriceAdj[u][i] > 0) # i existe déjà dans la pile # i est déjà visité # i n'est pas le parent de u # Donc il y'a un cycle, retourner True elif matriceAdj[u][i] > 0 and pile[i] == True and visites[i] == True 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 du sommet de parent est -1 parent[0] = -1 if estCyclique(matriceAdj, visites, 0, pile, parent) == True: print("le graphe contient un cycle") else: print("le graphe est acyclique")
J'espère que le problème est clair, aussi la solution. Si vous avez des questions, n'hésitez pas à les laisser dans la section commentaire ci-dessous ou à me contacter