Algorithme pour trouver tous les cycles dans un graphe orienté en C++ à l'aide de la matrice d'adjacence

Question

La matrice d'adjacence de graphe donné (par exemple g [] []), le graphe est dirigé. Vous devez trouver le nombre de tous les cycles de graphique (s'il existe) et les imprimer.

J'ai essayé d'écrire cet algorithme en Java, parfois cela fonctionne correctement. Si le graphe a des cycles complexes, l'algorithme retourne des cycles fous. S'il vous plaît, regardez mon code et aidez à résoudre ce problème

public static final int k = 6; 

public static int g[][] = { { 0, 1, 0, 0, 0, 0 }, 
          { 1, 0, 1, 0, 0, 0 }, 
          { 0, 0, 0, 1, 0, 0 }, 
          { 0, 0, 0, 0, 1, 0 }, 
          { 0, 0, 1, 0, 0, 0 }, 
          { 0, 0, 0, 0, 0, 0 } }; 

public static Vector stack = new Vector(); 

public static void printStack() { 
    System.out.print("stack is: { "); 
    for (int i = 0; i < stack.size(); i++) { 
     System.out.print(stack.get(i) + " "); 
    } 
    System.out.println("};"); 

} 

public static boolean checkCycle() { 
    boolean res = false; 

    for (int i = 0; i < stack.size() - 1; i++) { 
     if (stack.get(i).equals(stack.lastElement())) { 
      res = true; 
      break; 
     } 

    } 
    return res; 
} 

public static boolean go_to_line(int line) { 
    boolean res = false; 
    for (int i = 0; i < k; i++) { 
     if (g[line][i] == 1) { 
      stack.add(i); 
      if (checkCycle() == true) { 
       System.out.println("Cycle found!"); 
       res = true; 
      } else { 
       res = go_to_line(i); 
      } 
     } 
    } 

    return res; 
} 

public static int cycles_count() { 
    int res = 0; 

    for (int i = 0; i < k; i++) { 
     if (g[i][i] == 1) { 
      System.out.println("Knot detected at item {" + i + "}!"); 
      res++; 
     } 

     for (int j = i + 1; j < k; j++) { 
      if (g[j][i] == 1) { 
       stack.add(j); 
       stack.add(i); 

       if (go_to_line(i) == true) { 
        res++; 

        System.out.print("Final "); 
        printStack(); 
        stack.removeAllElements(); 
       } 
      } 
     } 
    } 

    return res; 
} 

Answer 1

Si C++ est le problème alors changez pour une autre langue. à ma connaissance, le C++ ne possède pas de fonctionnalité particulière qui rend le travail sur les graphes plus efficace et pratique. Alternativement, vous pourriez vouloir chercher un cadre qui résumera le niveau bas, vous permettant de vous concentrer sur la question de haut niveau. Vous pourriez envisager Boost Graph library à cette fin.

Answer 2

Ce problème a une complexité exponentielle dans le cas général. Le fait est que si chaque sommet est connecté à chacun, alors le nombre de tous les cycles de graphes est supérieur à 2^n (n'importe quel sous-ensemble de nœuds forme plusieurs cycles).

Il n'y a donc pas de bon algorithme dans le cas général. Pour trouver un cycle, vous pouvez utiliser la recherche par largeur d'abord. Pour trouver tous les cycles, vous devez utiliser un algorithme de force brute.