Cet article présente un algorithme basé sur le parcours en profondeur (DFS) pour identifier tous les cycles simples dans un graphe orienté représenté par une matrice d'adjacence. Contrairement à de nombreuses approches qui ne recherchent que les cycles avec des numéros de nœuds croissants ou qui omettent la déduplication, notre méthode identifie tous les cycles uniques.

Principe de l'algorithme

L'algorithme suit une approche DFS clasique avec deux modifications importantes : le maintien d'un chemin actuel dans une pile et la déduplication des résultats.

Pendant le parcours, nous utilisons deux structures principales :

• Un tableau booléen visite[] pour marquer les nœuds déjà visités
• Une pile cheminActuel[] pour stocker le chemin de recherche actuel

Lorsque nous visitons un nœud v :

1. Si v est déjà dans cheminActuel, nous avons détecté un cycle
2. Nous vérifions si ce cycle existe déjà dans notre ensemble de résultats
3. Si le cycle est nouveau, nous l'ajoutons à l'ensemble des résultats
4. Si v n'est pas visité, nous le marquons comme visité, l'ajoutons à cheminActuel, et continuons le parcours DFS sur ses voisins
5. Après l'exploration de tous les voisins, nous retirons v de cheminActuel (backtracking)

Stratégie de déduplication

La déduplication est cruciale car un cycle comme 0→1→2→3→0 est identique à 2→3→0→1→2. Notre approche consiste à :

1. Comparer la longueur des cycles candidats
2. Trouver le point de départ corrrespondant dans les cycles existants
3. Vérifier si tous les nœuds correspondent dans l'ordre cyclique

Implémentation de l'algorithme

Voici l'implémentation en C++ de notre solution :

void parcoursProfondeur(int sommet) {
    int position = trouverDansPile(cheminActuel, sommet);
    
    // Si le sommet est déjà visité mais pas dans le chemin actuel
    if (position == -1 && visite[sommet]) {
        visite[sommet] = false;
        return;
    }
    
    // Si le sommet est visité et présent dans le chemin actuel
    if (visite[sommet]) {
        if (position >= 0) {
            vector<int> cycle;
            // Extraire le cycle de la pile
            for (int i = position; i < cheminActuel.size(); i++) {
                cycle.push_back(cheminActuel[i]);
            }
            ajouterCycle(cycle);
            return;
        }
        return;
    }
    
    // Marquer le sommet comme visité et l'ajouter au chemin
    visite[sommet] = true;
    cheminActuel.push_back(sommet);
    
    // Explorer tous les voisins
    for (int voisin = 0; voisin < tailleMatriceAdj; voisin++) {
        if (matriceAdj[sommet][voisin] == 1) {
            parcoursProfondeur(voisin);
        }
    }
    
    // Backtracking
    cheminActuel.pop_back();
}
</int>

Fonction d'ajout de cycle avec déduplication :

void ajouterCycle(vector<int> cycle) {
    bool cycleExistant = false;
    int count, debut;
    
    if (cyclesTrouves.empty()) {
        cyclesTrouves.push_back(cycle);
        return;
    }
    
    // Vérifier si le cycle existe déjà
    for (int i = 0; i < cyclesTrouves.size(); i++) {
        count = 0;
        debut = 0;
        
        // Ne comparer que les cycles de même longueur
        if (cycle.size() == cyclesTrouves[i].size()) {
            // Trouver le point de départ correspondant
            for (int k = 0; k < cyclesTrouves[i].size(); k++) {
                if (cycle[0] == cyclesTrouves[i][k]) {
                    debut = k;
                }
            }
            
            // Comparer les cycles en tenant compte de la nature cyclique
            for (int j = 0, k = debut; j < cycle.size(); j++, k = (k + 1) % cyclesTrouves[i].size()) {
                if (cycle[j] == cyclesTrouves[i][k]) {
                    count++;
                }
            }
            
            // Si tous les nœuds correspondent, c'est le même cycle
            if (count == cycle.size()) {
                return;
            }
        }
    }
    
    // Ajouter le nouveau cycle
    cyclesTrouves.push_back(cycle);
}
</int>

Complexité algorithmique

Dans le pire des cas (graphe orienté complet), le nombre de cycles possibles est :