Алгоритм Прима не работает на неполных графах - C#
Формулировка задачи:
Доброго времени суток!
Помогите, пожалуйста, с реализацией алгоритма Прима (алгоритм построения остова минимального веса).
В данном примере вес остова должен получится 15, а получается 20.
Суть Алгоритма Прима: Алгоритм состоит из N-1 итерации, на каждой из которой к дереву добавляется ровно одно ребро, не нарушающее свойства дерева (т.е. один конец добавляемого ребра принадлежит дереву, а другой - не принадлежит). Ключевой момент - из всех таких рёбер каждый раз выбирается ребро с минимальным весом.
На полных графах данный алгоритм работает корректно, а вот на не полных нет. Не могу найти ошибку.
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication3 { class Program { static void Main(string[] args) { int n = 4;//количество вершин float[,] a, a1;//матрицы весов графа и его остова float[] used = new float[n]; //Массив использованных вершин short i, j; int count = 0; float s1 = 0;//вес остова a = new float[n, n]; a1 = new float[n, n]; a[0, 0] = 0; a[0, 1] = 11; a[0, 2] = 2; a[0, 3] = 0; a[1, 0] = 11; a[1, 1] = 0; a[1, 2] = 6; a[1, 3] = 0; a[2, 0] = 2; a[2, 1] = 6; a[2, 2] = 0; a[2, 3] = 7; a[3, 0] = 0; a[3, 1] = 6; a[3, 2] = 7; a[3, 3] = 0; for (i = 0; i < n; i++) { used[i] = 0; for (j = 0; j < n; j++) a1[i, j] = 0; } used[0] = 1; while (count < n - 1) { float min = 100000; for (i = 0; i < n; i++) { if (used[i] != 0) { for (j = 0; j < n; j++) { if ((a[i, j] < min) & (a[i, j] != 0) & (used[j]) == 0) min = a[i, j]; } } for (int k = 0; k < n; k++) { for (j = 0; j < n; j++) { if ((a[k, j] == min) & (used[j] == 0)) { used[j] = 1; a1[k, j] = a1[j, k] = min; s1 = s1 + a1[j, k]; k = n; count = count + 1; break; } } } } } for (i = 0; i < n; i++) { Console.WriteLine(" \n"); for (j = 0; j < n; j++) Console.WriteLine(a[i, j]); } Console.WriteLine("Вес остова ="+s1); } } }
Решение задачи: «Алгоритм Прима не работает на неполных графах»
textual
Листинг программы
for (i = 0; i < n; i++) { used[i] = 0; for (j = 0; j < n; j++) a1[i, j] = 0; } used[0] = 1; while (count < n - 1) { float min = 100000; for (i = 0; i < n; i++) { if (used[i] != 0) { for (j = 0; j < n; j++) { if ((a[i, j] < min) & (a[i, j] != 0) & (used[j]) == 0) min = a[i, j]; } } } //не хватало этой скобки
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д