Здравствуйте, я составил код который реализует алгоритм Прима, но некорректно вычисляются следующие параметры:
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();
}