Prim算法，请解释

Question

谁能给我解释一下这个循环中目前发生了什么？这是我在 Prim 算法上的作业代码的一部分。

我得到了：虽然 countIcluded 不是 vertices.length，部分。我需要了解下面发生的事情。值得一提的是 included 是一个布尔数组。

希望我是新手，因为我是新手，请尽可能简单地解释（如果可能），以便我能理解基础知识。

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

Answer 1

所以基本上这个算法所做的是遍历一个顶点列表，并根据从一个顶点到另一个顶点的成本创建一条路径。成本只是一个术语，用来解释从一个顶点到另一个顶点的难度，通常只是距离。让我们进入代码。

while (countIncluded != vertices.length) {

我知道你说你明白这意味着什么，但我还是会复习一遍。此 while 循环将确保您运行遍历数组中的每个顶点，以便每个顶点都至少连接到另一个顶点。

int u = -1;
for (int i = 0; i < vertices.length; i++) {

我将这两行结合起来，因为第一行的作用不大。变量 u 是当前相关顶点的索引。它最初设置为 -1，因为那不是数组中的有效位置。下一行 for 循环只是遍历给定数组中的每个顶点。

if (!included[i]) {
    if (u == -1 || C[u] > C[i])
        u = i;

第一行简单地检查 i 的当前值或当前顶点是否已经包含在树中。如果是，我们就不用再检查了，继续下一个。下一行首先检查 u 是否等于 -1。如上所述，-1 只是一个临时占位符值，此检查可确保它始终指向有效顶点。第二个检查是检查 u 的成本是否大于 i 的成本。这就是实际执行算法的过程。它基本上做的是获取 u 或临时顶点的成本。然后根据 i 的成本检查它。如果 i 的成本小于 u 的成本，则将 u 设置为 i。在这样做的过程中，它会找到成本最低的顶点，因为它会在整个过程中记住 u 的值。

included[u] = true;
countIncluded++;

第一行将数组中 u 的索引设置为 true。这将确保不会在您的算法中再次检查它，以防止每次迭代都检查相同顶点的无限循环。之后，countIncluded 递增以跟踪当前添加的顶点数。

希望对您有所帮助！不要犹豫，让我澄清任何事情！

Answer 2

看看评论是否清楚：

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

Prim算法，请解释

Prim's Algorithem, please explain

java

arrays

algorithm

boolean

prims-algorithm