Прим Алгоритхем, пожалуйста, объясните

Question

Может кто-нибудь объяснить мне, что в настоящее время происходит в этом цикле?Это часть кода для моего назначения по алгоритму Прима.

Я получаю: while countIcluded не является vertices.length, part.Мне нужно понять, что происходит ниже.Стоит отметить, что 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++;
     }