forked from vipw007/KMP_Algo.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
kruskal_MST.cpp
107 lines (100 loc) · 2.24 KB
/
kruskal_MST.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
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> iPair;
struct Graph
{
int V, E;
vector< pair<int, iPair> > edges;
Graph(int V, int E)
{
this->V = V;
this->E = E;
}
void addEdge(int u, int v, int w)
{
edges.push_back({w, {u, v}});
}
int kruskalMST();
};
struct DisjointSets
{
int *parent, *rnk;
int n;
DisjointSets(int n)
{
this->n = n;
parent = new int[n+1];
rnk = new int[n+1];
for (int i=0;i<=n;++i)
{
rnk[i] = 0;
parent[i] = i;
}
}
int find(int u)
{
if (u != parent[u])
parent[u] = find(parent[u]);
return parent[u];
}
void merge(int x, int y)
{
x = find(x), y = find(y);
if (rnk[x] > rnk[y])
parent[y] = x;
else // If rnk[x] <= rnk[y]
parent[x] = y;
if (rnk[x] == rnk[y])
rnk[y]++;
}
};
int Graph::kruskalMST()
{
int mst_wt = 0;
sort(edges.begin(), edges.end());
DisjointSets ds(V);
vector< pair<int, iPair> >::iterator it;
for (it=edges.begin(); it!=edges.end(); it++)
{
int u = it->second.first;
int v = it->second.second;
int set_u = ds.find(u);
int set_v = ds.find(v);
if (set_u != set_v)
{
cout << u << " - " << v << endl;
mst_wt += it->first;
ds.merge(set_u, set_v);
}
}
return mst_wt;
}
int main()
{
/*int V = 6, E = 8;
Graph g(V, E);
g.addEdge(0,1,6);
g.addEdge(0,4,5);
g.addEdge(0,5,4);
g.addEdge(1,2,3);
g.addEdge(1,4,1);
g.addEdge(2,3,2);
g.addEdge(3,4,4);
g.addEdge(4,5,2);*/
int V,E,s,d,w;
cout<<"Enter number of vertex:"<<endl;
cin>>V;
cout<<"Enter number of edges:"<<endl;
cin>>E;
Graph g(V,E);
cout<<"Enter edges along with weight (src,dest,wt):"<<endl;
for(int i=0;i<E;++i)
{
cin >> s >> d >> w;
g.addEdge(s,d,w);
}
cout << "Edges of MST are \n";
int mst_wt = g.kruskalMST();
cout << "\nWeight of MST is " << mst_wt;
return 0;
}