title: How do I determine if a graph has a cycle in Java?
body: <p>So what I'm trying to do is implement Kruskal's algorithm from a 2d array (called G) like this:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>The 0's mean no edge is connecting those two vertices and a value means an edge is connecting two vertices where the value represents the edge's weight and the row and column is the two vertices it's connecting. So 12 would be connecting 0 and 5. So what I decided to do is find the smallest element in the array and then add that to another 2d array (H) that's the same size as G but all the values are 0. Then I check and see if adding that edge forms a cycle and if it does then I remove the edge from H and keep going until every row is filled. Here's what I did:</p>
  
  <pre><code>        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 &lt; numVerts; i++){
                  for (int j = 0; j &lt; numVerts; j++){
                      if ((G[i][j] != 0) &amp;&amp; (G[i][j] &lt; 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
              }
  </code></pre>
  
  <p>So the only thing I need to figure out now is how do I check if an edge forms a cycle with any other edge in H. Based on how the arrays are represented in the 2d array, I could I figure out if the edges form cycles? One way I was thinking is using union-find to say if the newly added edge is in the union as the other edges then don't add it because it creates a cycle but I'm having trouble implementing that. </p>
  
  <p>P.S: I also didn't post the code for when I decide to keep the edge but basically that's where I update the boolcount for when I determine when to stop traversing. </p>