javaarraysalgorithmbooleanprims-algorithm

Prim's Algorithem, please explain


can some one explain to me what is currently happening in this loop? This is a part of a code for my assignment on Prim's algorithm.

I get the: while countIcluded is not vertices.length, part. I need to understand what's happening below. it's worth to mention that included is an array of booleans.

Expect that I'm new to this, because I am and please explain as simple as possible (if possible) so I can understand the basics.

while (countIncluded != vertices.length) {

    // find the not included vertex with minimum cost
    int u = -1;
    for (int i = 0; i < vertices.length; i++) {
        if (!included[i]) {
            if (u == -1 || C[u] > C[i])
                u = i;
        }
    }

    // include in MST
    included[u] = true;
    countIncluded++;
}

Solution

  • See if the comments make it cleared:

          while (countIncluded != vertices.length) { 
    
                //u represents a previous i value 
                int u = -1; //value serves as flag for "first time use"  
    
                //the purpose of this loop is to iterate over included array, which presumably 
                //if of the same length as vertices.
                for (int i = 0; i < vertices.length; i++) { 
                    if (!included[i]) { //execute if the value of included[i] is false
                        /* execute if one of these apply:
                           u value is -1 : meaning that it is the first time 
                           included[i] is false (and there is not previous value to compare to).
                           OR C[u] > C[i] : previous vertex value  > current vertex value
                         */
                        if (u == -1 || C[u] > C[i])    
                                          u = i;     //keep i value, the index of the lowest vertex
                                                     //value so far 
                    }
                }
    
                //at the end of the for loop u is the index of the lowest C[u]
                included[u] = true;
                countIncluded++;
         }