0
Я сделал алгоритм примитива, но всякий раз, когда я пытаюсь использовать код, он дает мне ту же матрицу назад. В общем, это не сводится к минимуму. Может кто-нибудь проверить код и дайте мне знать, почему она не минимизируя мою матрицуАлгоритм Прима не вычисляется
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <list>
#include <cstdlib>
#include <iomanip>
#include <limits.h>
int minKey(int n,int key[], bool mst[])
{
// Initialize min value
int min = INT_MAX, min_index;
for (int i = 0; i < n; i++)
if (mst[i] == false && key[i] < min)
min = key[i], min_index = i;
return min_index;
}
void print(int n,int **matrix)
{
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++) // print the matrix
{
cout << setw(2) << matrix[i][j] << " ";
}
cout << endl;
}
}
int **gen_random_graph(int n)
{
srand(time(0));
int **adj_matrix = new int*[n];
for(int i = 0; i < n; i++)
{
for (int j = i; j < n; j++) //generating a N x N matrix based on the # of vertex input
{
adj_matrix[i] = new int[n];
}
}
for(int u = 0; u < n; u++)
{
for (int v = u; v < n; v++) //decide whether it has an edge or not
{
bool edgeOrNot = rand() % 2;
adj_matrix[u][v] = adj_matrix[v][u] = edgeOrNot;
cout << u << " " << v << " " << adj_matrix[u][v] << endl;
if(adj_matrix[u][v] == true)
{
adj_matrix[v][u] = true;
if(u == v) //We can't have i = j in an undirected graph
{
adj_matrix[u][v] = -1;
}
cout << u << " " << v << " " << adj_matrix[u][v] << endl;
}
else
{
adj_matrix[v][u] = adj_matrix[u][v] = -1;
cout << u << " " << v << " " << adj_matrix[u][v] << "else" << endl;
}
}
}
for(int i = 0; i < n; i++)
{
for(int j = i; j < n; j++) //create the N x N with edges and sets the weight between the edge randomly
{
if(adj_matrix[i][j] == true)
{
int weight = rand() % 10 + 1;
adj_matrix[i][j] = adj_matrix[j][i] = weight;
cout << " (" << i << "," << j << ") " << "weight: " << adj_matrix[i][j] << endl;
}
}
}
print(n,adj_matrix);
return (adj_matrix);
}
void solve_mst_prim_matrix(int n, int **matrix)
{
int parent[n]; // Array to store constructed MST
int key[n]; // Key values used to pick minimum weight edge in cut
bool mstSet[n]; // To represent set of vertices not yet included in MST
// Initialize all keys as INFINITE
for (int i = 0; i < n; i++)
{
key[i] = INT_MAX, mstSet[i] = false;
}
// Always include first 1st vertex in MST.
key[0] = 0; // Make key 0 so that this vertex is picked as first vertex
parent[0] = -1; // First node is always root of MST
// The MST will have n vertices
for (int count = 0; count < n-1; count++)
{
// Pick the minimum key vertex from the set of vertices
// not yet included in MST
int u = minKey(n,key, mstSet);
// Add the picked vertex to the MST Set
mstSet[u] = true;
// Update key value and parent index of the adjacent vertices of
// the picked vertex. Consider only those vertices which are not yet
// included in MST
for (int v = 0; v < n; v++)
// matrix[u][v] is non zero only for adjacent vertices of m
// mstSet[v] is false for vertices not yet included in MST
// Update the key only if matrix[u][v] is smaller than key[v]
if (matrix[u][v] && mstSet[v] == false && matrix[u][v] < key[v])
parent[v] = u, key[v] = matrix[u][v];
}
cout << endl;
print(n,matrix);
}
int main()
{
int N;
cout << "Enter number of vertices" << endl;
cin >> N;
int **matrix = gen_random_graph(N);
solve_mst_prim_matrix(N, matrix);
return 0;
}