그래프의주기가 Java인지 어떻게 결정합니까?

Question

그래서 내가 이렇게 (G라고도 함) 2 차원 배열에서 크루스 칼의 알고리즘을 구현한다 할 노력하고있어 :

0 0 0 0 0 12 13 0 
0 0 6 0 0 0 0 3 
0 6 0 4 0 0 0 5 
0 0 4 0 10 0 0 7 
0 0 0 10 0 11 8 9 
12 0 0 0 11 0 1 0 
13 0 0 0 8 1 0 2 
0 3 5 7 9 0 2 0 

0으로부터이의 더 가장자리는 두 정점하고 값을 연결하지 말은 가장자리가 연결을 의미합니다 두 개의 꼭지점 여기서 값은 가장자리의 가중치를 나타내고 행과 열은 연결된 두 개의 꼭지점입니다. 따라서 12는 0과 5를 연결하게됩니다. 그래서 내가 결정한 것은 배열에서 가장 작은 요소를 찾아서 G와 같은 크기의 다른 2 차원 배열 (H)에 추가하는 것입니다. 그러나 모든 값은 0입니다. 그런 다음 확인합니다. 그 가장자리를 추가하는 것이주기를 형성하는지 확인하고, 그렇다면 나는 모든 가장자리가 채워질 때까지 계속 H에서 가장자리를 제거하고 계속 진행합니다. 여기에 내가했던 일이야 :

 int numVerts = G.length; 

     int [][] H = new int[numVerts][numVerts]; 
     int minWeight; 
     int k = 0; 
     int l = 0; 
     int boolcount = 0; 
     boolean [] R = new boolean[G.length]; 
     Arrays.fill(R, false); 

     while (boolcount != numVerts){ 
      for (int i = 0; i < numVerts; i++){ 
       for (int j = 0; j < numVerts; j++){ 
        if ((G[i][j] != 0) && (G[i][j] < minWeight)){ 
         minWeight = G[i][j]; 
         k = i; 
         l = j; 
        } 
       } 
      } 
      H[k][l] = minWeight; 
      H[l][k] = minWeight; 
      G[k][l] = 0; 
      G[l][k] = 0; 
      if (/*it forms a cycle*/){ 
      H[k][l] = 0; 
      H[l][k] = 0; 
      } else { 
       //keep the edge 
      } 

그래서 지금 파악해야 할 유일한 것은 가장자리가 배열이 2D로 표현하는 방법을 기반으로 H.에서 다른 가장자리 사이클을 형성하면 내가 확인합니까 어떻게 배열, 나는 가장자리가 사이클을 형성하는지 알아낼 수 있을까? 내가 생각했던 한 가지 방법은 새로 추가 된 가장자리가 다른 가장자리와 같은 조합에있는 경우에는 순환을 만드는 것이기 때문에 추가하지 말고 union-find를 사용하는 것입니다.하지만 구현하는 데 문제가 있습니다.

P.S : 가장자리를 유지하기로 결정했을 때 코드를 게시하지 않았지만 기본적으로 가로 채기를 중지 할 시점을 결정할 때 코드를 업데이트합니다.

Answer 1

시작점을 지정하십시오. 먼저 가장자리 너비를 무시하면서 그래프 너비를 가로 지르면서지나갑니다. 무게가 < 인 가장자리를 발견하면주기적인 그래프가 나타납니다.