방향성 그래프의 사이클 수를 얻기 위해 모서리를 뒤집는다.

Question

나는 방향성 그래프에서 가능한 모든 사이클을 얻기 위해 코드를 작성 해왔다. Here은 뒤쪽 가장자리를 추적하고 하나의 뒤쪽 가장자리가 발견 될 때마다 하나의주기가 감지되었다는 사실을 반환하는 구현입니다. 이것을 다음과 같이 확장했습니다 : 트리에서 가능한 모든 뒤쪽 가장자리를 계산합니다. 뒷쪽 가장자리의 수는 순환 횟수를 제공해야합니다. 이것이 맞는지 확실하지 않습니다. 이를 사용하여 다음을 구현했습니다. count 변수는 유용하지 않습니다. 처음에 나는 각 사이클 수를 알려주도록했다. 그러나 그것은 정답을주지 않습니다. 그러나 모든 뒤쪽 가장자리를 저장하는 edgeMap의 크기는 일부 그래프에서는 정확한 수의 사이클을 제공하지만 전부는 아닙니다.

코드는 그림에서 G2와 G3에서 작동하지만 G1에서는 실패합니다. (G1에는 2 사이클 밖에 없지만 3 개의 뒷 모서리가 있습니다.) 하나의 backedge 하나 이상의주기에 참여할 수 있기 때문에 내가 잘못 갈 수있는 곳의 제안은,

public int allCyclesDirectedmain(){ 
     clearAll(); 
     int count=0; 
     Map<Vertex, Vertex> edgeMap = new HashMap<>(); 


     for (Vertex v : vertexMap.values()) { 
      if (!v.isVisited && allCyclesDirected(v,edgeMap)) 
       count++; 
     } 
     System.out.println(edgeMap); 
     return count; 

    } 
public boolean allCyclesDirected(Vertex v, Map<Vertex, Vertex> edgeMap){ 
     if (!v.isVisited){ 
      v.setVisited(true); 
      Iterator<Edge> e = v.adj.iterator(); 
      while (e.hasNext()){ 
        Vertex t = e.next().target; 
        if (!t.isVisited && allCyclesDirected(t,edgeMap)){ 
         edgeMap.put(v, t); 
          return true; 
        } 
        else 
          return true; 
        } 
       } 
     return false; 
    } 

Answer 1

backedges의 수는 사이클 수없는 도움이 될 것입니다.

그래프 G1에서 깊이 우선 탐색의 진행을 A :> B-> C를 방문한 다음 D와 E 중 하나를 선택합니다. D를 취한다고 가정 해 봅니다. 그런 다음 E를 방문하고 B로가는 배지를 찾습니다. 문제는 EB 가장자리가 BCE주기와 BCDE주기에 모두 참여한다는 것입니다.

다음은 또 다른 예입니다. 네 개의 노드에 대한 완전한 지향 그래프를 생각해보십시오. 거기에 더 이상 - 12 가장자리하지만

• 6 개의 정점 사이클
• 8 세 꼭지점 사이클
• 6 네 꼭지점 사이클 20 사이클의 총

있다 그래프의 가장자리! 실제로 그래프에 지수주기가있을 수 있고 그 수를 계산하는 문제는 #CYCLE, is not computable in polynomial time if P != NP입니다.