Java how to check if a row is empty in a 2d array.

Question

Let's say I have a 2d array (G) that looks like this:

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

I have to traverse an array like this and find the minimum value that's not zero. After I find the minimum value I add it to another 2d array called H which is empty but has the same size as G. Once I add the value to H I then set the value in G to zero and traverse though the array again to find the 2nd smallest value, then the 3rd, then the 4th and so on. I stop traversing the array when every single line in H has a value in it. So for the above array, on my first pass I would find 1 to be the lowest value so I add it to H like this:

0  0  0  0  0  0  0  0 
0  0  0  0  0  0  0  0 
0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0
0  0  0  0  0  0  1  0 
0  0  0  0  0  1  0  0
0  0  0  0  0  0  0  0

Here's what I wrote in java:

int numVerts = G.length;
int [][] H = new int[numVerts][numVerts];
while (/*there exists an empty row in H*/){
    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;
}

So I can solve this problem any way I want and that's the way I'm choosing to solve it. So the only thing I have to figure out is how do I tell if all the rows in H have at least 1 value without just flat out traversing through H because I'm already traversing through G and adding values in certain places in H.

Answer 1

You do not want to traverse through H again. So you have to somehow store the rows of H in which you put a new value.

You could make a boolean array the size of the number of rows in H. Then after each time you add something to H you set the value for the row to true in the boolean array. Then you iterate through the boolean array and see if a value is still false. If this is not the case you are finished.