Задать вопрос
kitkat1000
@kitkat1000
Это я

Проблема с реализацией алгоритма Прима C++. Как доработать код?

Здравствуйте, я составил код который реализует алгоритм Прима, но некорректно вычисляются следующие параметры:
1) Минимальное остовное дерево (Minimum spanning tree).
2) Минимальная стоимость (Minimum cost).
Помогите пожалуйста доработать код
#include <iostream>
#include <string>
#include <vector>
#include <random>
#include <queue>
#include <conio.h>

using Vec = std::vector<int>;
using Matrix = std::vector<Vec>;

int a, b, u, v, n, i, j;
int ne = 1;
int visited[10] = {0};
int min;
int mincost = 0;
int cost[10][10];

struct Edge
{
    int i;
    int j;
};

Matrix get_random_graph(int n)
{
    std::mt19937 engine { std::random_device()() } ;
    std::uniform_int_distribution<int> uid(1, 10);
    Matrix cost(n, Vec(n));
    for (int i = 0; i < n; ++i)
    {
        for (int j = i + 1; j < n; ++j)
        {
            cost[i][j] = cost[j][i] = uid(engine);
        }
    }
    return cost;
}

void print(const Matrix& m, const std::string& title)
{
    std::cout << title << "\n";
    for (const auto& row : m)
    {
        for (const auto item : row)
        {
            std::cout << item << "\t";
        }
        std::cout << "\n";
     }
}

int main()
{
	int path[100] = {0}; //В этот массив будут записываться вершины, по которым составиться путь
	int path_index = 0;

	std::cout << "Enter the number of vertices: "; //Введи количество вершин:
	std::cin >> n;
	Matrix adj = get_random_graph(n);
    print(adj, "Graph");

	visited[1] = 1;
	std::cout << "\n";
 
	while(ne < n)
	{
		for(i = 1, min = 999; i <= n; i++)
		for(j = 1; j <= n; j++)
		if(cost[i][j] < min)
		if(visited[i] != 0)
		{
			min = cost[i][j];
			a = u = i;
			b = v = j;
		}
		if(visited[u] == 0 || visited[v] == 0)
		{
			path[path_index] = b;
			path_index++;
			//cout<<"\n "<<ne++<<"  "<<a<<"  "<<b<<min; //Можно вывести так
			ne++; //если строчку выше раскомментировать - эту закомментировать
			mincost += min;
			visited[b] = 1;
 
		}
		cost[a][b] = cost[b][a] = 999;
	}

	std::cout << "Minimum spanning tree\n"; //Минимальное остовное дерево
	std::cout << 1 << " --> ";
	for(int i = 0; i < n-1; i++)
	{
		std::cout << path[i];
		if(i < n-2)
		{
			std::cout<<" --> ";
		}
	}
	std::cout << "\nMinimum cost " << mincost; //Минимальная стоимость
	std::cin.get();
}
  • Вопрос задан
  • 164 просмотра
Подписаться 1 Простой Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы