Prims Algorithmus berechnet nicht

Question

Ich habe einen Prim-Algorithmus, aber wenn ich versuche, den Code zu verwenden, gibt es mir die gleiche Matrix zurück. Im Allgemeinen wird nicht minimiert. Kann jemand den Code überprüfen und lassen Sie mich wissen, warum ist es nicht meine Matrix

minimiert mich

#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; 
} 

Answer 1

korrigieren, wenn ich falsch bin, aber Ihr Code nach dem Lesen Sie nicht einmal jeder Wert von **matrix änderte sich in Ihre solve_mst_prim_matrix Funktion. So druckt es im Grunde das gleiche ..