-
Notifications
You must be signed in to change notification settings - Fork 0
/
KruskalAlgorithm.cpp
79 lines (69 loc) · 1.75 KB
/
KruskalAlgorithm.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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 부모 노드를 찾는 함수
int getParent(int parent[], int x) {
if(parent[x] == x) return x;
return parent[x] = getParent(parent, parent[x]);
}
// 두 부모 노드를 합치는 함수
int unionParent(int parent[], int a, int b) {
a = getParent(parent, a);
b = getParent(parent, b);
if(a < b) parent[b] = a;
else parent[a] =b;
}
// 같은 부모를 가지는지 확인
int findParent(int parent[], int a, int b) {
a = getParent(parent, a);
b = getParent(parent, b);
if(a == b) return 1;
return 0;
}
// 간선 클래스 선언
class Edge {
public:
int node[2];
int distance;
Edge(int a, int b, int distance) {
this -> node[0] = a;
this -> node[1] = b;
this -> distance = distance;
}
bool operator < (Edge &edge) {
return this -> distance < edge.distance;
}
};
int main(void) {
int n = 7;
int m = 11;
vector<Edge> v;
v.push_back(Edge(1, 7, 12));
v.push_back(Edge(1, 4, 28));
v.push_back(Edge(1, 2, 67));
v.push_back(Edge(1, 5, 17));
v.push_back(Edge(2, 4, 24));
v.push_back(Edge(2, 5, 62));
v.push_back(Edge(3, 5, 20));
v.push_back(Edge(3, 6, 37));
v.push_back(Edge(4, 7, 13));
v.push_back(Edge(5, 6, 45));
v.push_back(Edge(5, 7, 73));
// 간선의 비용을 기준으로 오름차순 정렬
sort(v.begin(), v.end());
// 각 정점이 포함된 그래프가 어디인지 저장
int parent[n];
for(int i = 0; i < n; i++) {
parent[i] = i;
}
int sum = 0;
for(int i = 0; i < v.size(); i++) {
// 사이클이 발생하지 않는 경우 그래프에 포함
if(!findParent(parent, v[i].node[0] - 1, v[i].node[1] - 1 )) {
sum += v[i].distance;
unionParent(parent, v[i].node[0] - 1, v[i].node[1] - 1);
}
}
printf("%d\n", sum);
}