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

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

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")
                            

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")

                        

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")

                

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