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++;
}
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++;
}