SDIZO2/PrimAlgorithm.cpp at main · rodakrafal/SDIZO2 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include "PrimAlgorithm.h"
#include <iostream>
#include <queue>
#include <vector>
#include <limits>

using namespace std;

PrimAlgorithm::PrimAlgorithm(){

}

PrimAlgorithm::~PrimAlgorithm(){

}

void PrimAlgorithm::primMatrix(Graph &graph) {

    amountVertices = graph.getVertices();
    if(amountVertices <=1){
        return;
    }

    firstVertice = graph.getFirstVertice();
    int weight = 0;
    bool * MST_Array = new bool [amountVertices];
    for (int i = 0; i<amountVertices;i++){
        MST_Array[i]=false;
    }
    MST_Array[firstVertice]= true;

    priority_queue<Edge, vector<Edge>, Compare> Q;
    int temp = firstVertice;
    int current = firstVertice;

    int count = amountVertices-1;
    temp = current;
    for(int i = 0; i<count;i++){
        Edge edge;
        for (int x = 0; x < amountVertices; x++){
            if(numeric_limits<int>::max() != graph.getTableValue(current, x) && !MST_Array[x]){
                edge.from = current;
                edge.to = x;
                edge.weight = graph.getTableValue(current, x);
                Q.push(edge);
            }
        }
        MST_Array[current] = true;
        edge = Q.top();

        temp = edge.from;
        current = edge.to;
        weight +=  edge.weight;
        cout << "(" << temp << ", "<< current << ")   " << edge.weight<< endl;
        Q.pop();
    }
    cout << "\nMST = " << weight << endl;
    delete [ ]MST_Array;

}

void PrimAlgorithm::primList(Graph &graph){

    amountVertices = graph.getVertices();
    if(amountVertices <=1){
        return;
    }

    firstVertice = graph.getFirstVertice();
    int weight = 0;
    bool * MST_Array = new bool [amountVertices];
    for (int i = 0; i<amountVertices;i++){
        MST_Array[i]=false;
    }
    MST_Array[firstVertice]= true;

    priority_queue<Edge, vector<Edge>, Compare> Q;
    int temp = firstVertice;
    int current = firstVertice;

    int count = amountVertices-1;
    temp = current;
    for(int i = 0; i<count;i++){
        Edge edge;
        Node *x;
        for (x = graph.tableList[current]; x!=NULL; x = x->next){
            if(!MST_Array[x->index]){
                edge.from = current;
                edge.to = x->index;
                edge.weight = x->weight;
                Q.push(edge);
            }
        }
        MST_Array[current] = true;
        edge = Q.top();

        temp = edge.from;
        current = edge.to;
        weight +=  edge.weight;
        cout << "(" << temp << ", "<< current << ")   " << edge.weight<< endl;
        Q.pop();
    }
    cout << "\nMST = " << weight << endl;
    delete [] MST_Array;
}