인접 행렬을 사용하여 C++에서 유향 그래프의 모든 사이클을 찾는 알고리즘

Question

그래프 인접 행렬 (예 : g [] [])이 주어지면 그래프가 지정됩니다. 모든 그래프 사이클 (존재하는 경우)의 카운트를 찾아서 인쇄해야합니다.

자바로이 알고리즘을 작성하려고했는데 때로는 제대로 작동합니다. 그래프에 복잡한 사이클이있는 경우 알고리즘이 미친 사이클을 반환합니다. 제발 내 코드를보고이 문제를 해결하는 데 도움이됩니다.

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

C++가 문제가되면 다른 언어로 변경하십시오. 최대 지식 내 지식 C++에는 그래프 문제를보다 효율적으로/효율적으로 처리 할 수있는 특별한 기능이 없습니다. 또는 하위 수준을 추상화하는 프레임 워크를 찾아 상위 수준 질문에 집중할 수 있습니다. 그 목적으로 Boost Graph library을 고려할 수 있습니다.

Answer 2

이 문제는 일반적으로 지수 적으로 복잡합니다. 문제는 각 꼭지점이 각각에 연결되면 모든 그래프 사이클의 수는 2^n 이상입니다 (모든 노드의 하위 집합이 여러 사이클을 형성 함).

따라서 일반적으로 좋은 알고리즘은 없습니다. 너비 너비 우선 검색을 사용할 수있는주기를 찾으려면. 모든 사이클을 찾으려면 무차별 대입 알고리즘을 사용해야합니다.