SDIZO2/KruskalAlgorithm.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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include "KruskalAlgorithm.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

KruskalAlgorithm::KruskalAlgorithm(){}

KruskalAlgorithm::~KruskalAlgorithm(){}

DSNode::DSNode(){}

DSNode::~DSNode(){}


void KruskalAlgorithm::UnionSets (Edge edge)
{
  int ru, rv;

  ru = FindSet (edge.from) ;
  rv = FindSet (edge.to);

  if( ru != rv )
  {
    if( ds[ru].rank > ds[rv].rank )
        ds[rv].parent = ru;
    else
    {
        ds[ru].parent = rv;
      if( ds[ru].rank == ds[rv].rank ) ds[rv].rank++;
    }
  }
}

int KruskalAlgorithm::FindSet(int v ){

    if(ds[v].parent == v) return v;
    else {
        ds[v].parent = FindSet (ds[v].parent);
        return ds[v].parent;
    }
}

bool comparator(Edge a,Edge b)
{
	return a.weight > b.weight;
}

void KruskalAlgorithm::kruskalMatrix(Graph &graph){

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

    amountVertices = graph.getVertices();
    amoutOfEdges = graph.getVertices() - 1;

    ds.resize(amountVertices);
    for (int i = 0; i < amountVertices; i++){
        ds[i].parent = i ;
        ds[i].rank = 0;
    }
    // priority_queue<Edge, vector<Edge>, Compare> Q;

    Edge edge;
    vector<Edge> list;
    for(int i = 0;i <amountVertices;i++){
        for (int j = 0;j<amountVertices;j++){
            if(numeric_limits<int>::max() != graph.tableMatrix[i][j]){
                edge.from = i;
                edge.to = j;
                edge.weight = graph.tableMatrix[i][j];
                // Q.push(edge);
                list.push_back(edge);
            }
        }
    }
    sort(list.begin(), list.end(), comparator);

    int from,to, weight = 0;
    for( int i = 0; i < amoutOfEdges; i++ ){
        do{
            // edge = Q.top();
            // Q.pop();
            edge = list.back();
            list.pop_back();
            from = FindSet (edge.from);
            to = FindSet (edge.to);
        } while( from == to);
            weight += edge.weight;
            cout << "(" << edge.from << ", " << edge.to << ")   "<<edge.weight<<endl;
            UnionSets (edge);
  }

  cout << "\nMST = " << weight << endl;
}

void KruskalAlgorithm::kruskalList(Graph &graph){
    if(graph.getVertices() <=1){
        return;
    }

    amountVertices = graph.getVertices();
    amoutOfEdges = graph.getVertices() - 1;

    ds.resize(amountVertices);
    for (int i = 0; i < amountVertices; i++){
        ds[i].parent = i ;
        ds[i].rank = 0;
    }
    // priority_queue<Edge, vector<Edge>, Compare> Q;
    Edge edge;
    vector<Edge> list;
    Node *x;
    for(int i = 0;i <amountVertices;i++){
        for (x = graph.tableList[i]; x!=NULL; x = x->next){
                edge.from = i;
                edge.to = x->index;
                edge.weight = x->weight;
                // Q.push(edge);
                list.push_back(edge);
        }
    }
    sort(list.begin(), list.end(), comparator);

    int from,to, weight = 0;
    for( int i = 0; i < amoutOfEdges; i++ ){
        do{
            // edge = Q.top();
            // Q.pop();
            edge = list.back();
            list.pop_back();
            from = FindSet (edge.from);
            to = FindSet (edge.to);
        } while( from == to);
            weight += edge.weight;
            cout << "(" << edge.from << ", " << edge.to << ")   "<<edge.weight<<endl;
            UnionSets (edge);
  }

  cout << "\nMST = " << weight << endl;
}