Алгоритм Прима не работает на неполных графах - C#

Узнай цену своей работы

Формулировка задачи:

Доброго времени суток! Помогите, пожалуйста, с реализацией алгоритма Прима (алгоритм построения остова минимального веса). В данном примере вес остова должен получится 15, а получается 20. Суть Алгоритма Прима: Алгоритм состоит из N-1 итерации, на каждой из которой к дереву добавляется ровно одно ребро, не нарушающее свойства дерева (т.е. один конец добавляемого ребра принадлежит дереву, а другой - не принадлежит). Ключевой момент - из всех таких рёбер каждый раз выбирается ребро с минимальным весом. На полных графах данный алгоритм работает корректно, а вот на не полных нет. Не могу найти ошибку.
Листинг программы 
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5.  
  6. namespace ConsoleApplication3
  7. {
  8.     class Program
  9.     {
  10.         static void Main(string[] args)
  11.         {
  12.             int n = 4;//количество вершин
  13.             float[,] a, a1;//матрицы весов графа и его остова
  14.             float[] used = new float[n]; //Массив использованных вершин
  15.             short i, j;
  16.             int count = 0;
  17.             float s1 = 0;//вес остова
  18.  
  19.             a = new float[n, n];
  20.             a1 = new float[n, n];
  21.  
  22.             a[0, 0] = 0;
  23.             a[0, 1] = 11;
  24.             a[0, 2] = 2;
  25.             a[0, 3] = 0;
  26.             a[1, 0] = 11;
  27.             a[1, 1] = 0;
  28.             a[1, 2] = 6;
  29.             a[1, 3] = 0;
  30.             a[2, 0] = 2;
  31.             a[2, 1] = 6;
  32.             a[2, 2] = 0;
  33.             a[2, 3] = 7;
  34.             a[3, 0] = 0;
  35.             a[3, 1] = 6;
  36.             a[3, 2] = 7;
  37.             a[3, 3] = 0;
  38.  
  39.             for (i = 0; i < n; i++)
  40.             {
  41.                 used[i] = 0;
  42.                 for (j = 0; j < n; j++)
  43.                     a1[i, j] = 0;
  44.             }
  45.  
  46.             used[0] = 1;
  47.  
  48.             while (count < n - 1)
  49.             {
  50.                 float min = 100000;
  51.                 for (i = 0; i < n; i++)
  52.                 {
  53.                     if (used[i] != 0)
  54.                     {
  55.                         for (j = 0; j < n; j++)
  56.                         {
  57.                             if ((a[i, j] < min) & (a[i, j] != 0) & (used[j]) == 0)
  58.                             
  59.                                 min = a[i, j];
  60.                                
  61.                         }
  62.  
  63.                     }
  64.  
  65.                     for (int k = 0; k < n; k++)
  66.                     {
  67.                         
  68.                         for (j = 0; j < n; j++)
  69.                         {
  70.   
  71.                             if ((a[k, j] == min) & (used[j] == 0))
  72.                             {
  73.                                 used[j] = 1;
  74.                                 a1[k, j] = a1[j, k] = min;
  75.                                 s1 = s1 + a1[j, k];
  76.                                 k = n;
  77.                                 count = count + 1;
  78.                                 break;
  79.                             }
  80.                         }
  81.                     }
  82.                 }  
  83.           }
  84.             for (i = 0; i < n; i++)
  85.             {
  86.                 Console.WriteLine(" \n");
  87.                 for (j = 0; j < n; j++)
  88.                     Console.WriteLine(a[i, j]);
  89.             }
  90.             Console.WriteLine("Вес остова ="+s1); 
  91.         }
  92.  
  93.     }
  94. }

Решение задачи: «Алгоритм Прима не работает на неполных графах»

textual
Листинг программы 
  1.  
  2.             for (i = 0; i < n; i++)
  3.             {
  4.                 used[i] = 0;
  5.                 for (j = 0; j < n; j++)
  6.                     a1[i, j] = 0;
  7.             }
  8.  
  9.             used[0] = 1;
  10.  
  11.             while (count < n - 1)
  12.             {
  13.                 float min = 100000;
  14.                 for (i = 0; i < n; i++)
  15.                 {
  16.                     if (used[i] != 0)
  17.                     {
  18.                         for (j = 0; j < n; j++)
  19.                         {
  20.                             if ((a[i, j] < min) & (a[i, j] != 0) & (used[j]) == 0)
  21.                             
  22.                                 min = a[i, j];
  23.                                
  24.                         }
  25.  
  26.                     }
  27.                 } //не хватало этой скобки

ИИ поможет Вам:

  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

9   голосов , оценка 3.778 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы