Алгоритм Прима с матрицами
Я пытаюсь реализовать алгоритм Прима с помощью C ++ и матриц.
Вот моя проблема:
int node[] = {11, 11, 0, 11, 11, 11, 11, 11};
int nodeCon[8];
void generatePrims() {
int cNode = 3;
for (int i = 1; i <= 8; i++) {
if (graph[cNode][i] != 0){
if (node[i] > graph[cNode][i]) {
node[i] = graph[cNode][i];
nodeCon[i] = cNode;
}
}
}
};
cNode — начальный узел.
graph[][] это 2d матрицы, которые содержат связи.
nodeCon[] это массив, который будет содержать соединения для MST (какой узел связан с другим)
node[]= содержит значение стоимости для nodeCon.
Мой вопрос, как я собираюсь перейти к следующему прыжку? Допустим, я нашел минимальное соединение и установлю значение cNode= minConnection как будет выглядеть петля? Откуда я знаю, что мне пришлось исследовать все узлы?
заранее спасибо
Решение
Что-то вроде этого:
int node[]={11,11,0,11,11,11,11,11};
int used[]={0,0,0,0,0,0,0,0,0,0};
int nodeCon[8];
void generatePrims(){
int cNode = 3;
int next, min_now;
for(int i=0; i<8; ++i) {
used[cNode] = 1;
min_now = MAX_INT;
for(int i=1;i<=8;i++){
if(!used[i]){
if(node[i] > graph[cNode][i]){
node[i] = graph[cNode][i];
nodeCon[i]= cNode;
}
if(node[i] < min_now) {
min_now = node[i];
next = i;
}
}
}
cNode = next;
}
};
Также стоит отметить: это будет быстрее, если вместо «используемого» массива вы будете использовать список неиспользуемых вершин.
Другие решения
В настоящее время я не могу комментировать предыдущий ответ (так как у меня недостаточно репутации), поэтому я сделаю это через другой ответ. Решение Петра почти правильное, однако я считаю, что алгоритм Прима учитывает не только текущий узел. Пример можно увидеть здесь Алгоритм Прима. По сути это означает, что вам нужно проверить путь от посещенных вами узлов, а не только к самому последнему узлу.
Это означает, что вам нужно будет хранить вектор, содержащий узлы, которые вы посетили, и «для каждого» через них, а не просто проверять пути от последнего узла, который вы посетили.
Следующий сайт имеет дополненный алгоритм и тестовый класс junit. Так и должно быть то, что вы ищете. Конечно, у класса юнит-теста есть фактическая матрица. И класс реализации имеет код.