-
Notifications
You must be signed in to change notification settings - Fork 0
/
Kruskal.cpp
115 lines (102 loc) · 2.43 KB
/
Kruskal.cpp
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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
// https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-using-stl-in-c/
// Kruskal algorithm input: connected undirected weight graph
typedef std::pair<int, int> edge; // {vertex_id, vertex_id}
// use 2 heuristics
// 1. path compression
// 2. union by rank
class DisjointSet {
public:
int* parent;
int* rank;
int num;
DisjointSet(int n) {
// {S0,S1, ..., Sn-1} are disjoint each other
num = n;
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; ++i) {
rank[i] = 0;
parent[i] = i;
}
}
int find(int u) {
if (u != parent[u])
parent[u] = find(parent[u]); // path compression
return parent[u];
}
void Union(int x, int y) {
// find each representative for the set that includes x and y
x = find(x);
y = find(y);
// union by rank
if (rank[x] > rank[y])
parent[y] = x;
else
parent[x] = y;
if (rank[x] == rank[y])
rank[y] = rank[y] + 1;
}
};
class Graph {
public:
int NumOfVertices;
int NumOfEdges;
vector<pair<int, edge>> edges; // {weight, edge}
Graph(int NumV, int NumE) {
NumOfVertices = NumV;
NumOfEdges = NumE;
}
void addEdge(int u, int v, int w) {
edges.push_back({ w,{u,v} });
//edges.push_back(make_pair(w,make_pair(u,v)));
}
int kruskal() {
int result = 0;
// https://www.geeksforgeeks.org/sorting-a-vector-in-c/
// #include<algorithm>
// sort by edges[*it].first(weight), auto it = edge.begin() ~ edge.end()
std::sort(edges.begin(), edges.end());
DisjointSet Ds(NumOfVertices);
for (auto it = edges.begin(); it != edges.end(); ++it) {
int u = it->second.first;
int v = it->second.second;
if (Ds.find(u) != Ds.find(v)) {
// print MST edge(greedy choice)
cout << u << "-" << v << endl;
// update the sum of MST weight
result = result + it->first;
Ds.Union(u, v);
}
}
return result;
}
};
int main() {
/* Let us create above shown weighted
and unidrected graph */
int V = 9, E = 14;
Graph g(V, E);
// making above shown graph
g.addEdge(0, 1, 4);
g.addEdge(0, 7, 8);
g.addEdge(1, 2, 8);
g.addEdge(1, 7, 11);
g.addEdge(2, 3, 7);
g.addEdge(2, 8, 2);
g.addEdge(2, 5, 4);
g.addEdge(3, 4, 9);
g.addEdge(3, 5, 14);
g.addEdge(4, 5, 10);
g.addEdge(5, 6, 2);
g.addEdge(6, 7, 1);
g.addEdge(6, 8, 6);
g.addEdge(7, 8, 7);
cout << "Edges of MST are \n";
int mst_wt = g.kruskal();
cout << "\nWeight of MST is " << mst_wt;
return 0;
}