2016-04-24 8 views
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; 
} 

ответ

0

Поправьте меня, если я ошибаюсь, но после прочтения кода, вы даже не менять любого значения **matrix в ваш solve_mst_prim_matrix функция. Так что это в основном печатает то же самое.