java - Prim算法，请解释

Question

有人可以向我解释一下这个循环中目前正在发生什么吗？ 这是我在 Prim 算法上的作业代码的一部分。

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

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

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 递增以跟踪当前添加的顶点数。

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