Алгоритм Прима не работает на неполных графах - 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];
                               
                        }
 
                    }
                } //не хватало этой скобки

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


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

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

9   голосов , оценка 3.778 из 5
Похожие ответы